2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Сравнение. Ищу второе решение
Сообщение12.08.2013, 19:37 
Здравствуйте! Вот задача. Доказать, что если $p$ и $q$ неравные между собой простые числа, то $p^{q-1}+q^{p-1}\equiv
  1(mod\,pq)$. Первое решение ясно: т.к. $(p, q)=1$, то по теореме Ферма $q^{p-1}\equiv1(mod\,p) $ и похожее сравнение для модуля $q$. после переноса единиц в левую сторону и перемножения сравнений, получим требуемое. Но, с другой стороны, напрашивается второе решение: в этом случае $\varphi (pq)=(p-1)(q-1)$ и нужно подобрать число, которое после возведения в эту степень было бы сравнимо с левой частью доказываемого сравнения. Ничего не приходит на ум. А может, это вообще тупиковый путь? Я не усложняю задачу, а просто хочу с разных сторон подойти.

 
 
 
 Re: Ишу второе решение
Сообщение12.08.2013, 19:53 
Sinoid в сообщении #754205 писал(а):
и нужно подобрать число, которое после возведения в эту степень было бы сравнимо с левой частью доказываемого сравнения.
А как Вы планируете доказывать эту сравнимость? Самое естественное --- это рассмотреть отдельно по модулю $p$ и по модулю $q$. Но это фактически то же самое, что и первое решение. Стоит ли овчинка выделки? Всё-таки первое решение самое естественное (да и очевидное тоже).

 
 
 
 Re: Ищу второе решение
Сообщение13.08.2013, 01:39 
Да, хотя простые решения считаются более предпочтительными, они иногда тормозят поиски других, более общих, методов. Например, банальная задача о двух трубах: первая наполняет бассейн за $a$ часов, вторая-за $b$. За сколько часов они наполнят вместе? Можно, конечно, объем бассейна принять за 1. Тогда первая в час наполняет $\frac{1}{a}$ часть бассейна, вторая- $\frac{1}{b}$. И ответ будет $\frac{1}{\frac{1}{\frac{1}{a}+\frac{1}{b}}}$. Решение просто и все довольны, все смеются, только не видно путей для обобщения. А вот если бы обозначить производительность первой трубы через $x$литров/ч, второй- $y$ л/ч, объем бассейна через $V$тогда сразу бы получили систему $\frac{V}{x}=a$, $\frac{V}{y}=b$, из которой несложно получить $\frac{V}{x+y}$. Я вот поехал на олимпиаду и первый метод я знал, а второй метод не смог придумать, растерялся, и потому не решил задачу про Петю и Васю, как они огород вскапывали, а дома-то дошло. Так что не всегда простые решения полезны, хотя, они желательнее.

 
 
 [ Сообщений: 3 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group