|
Задача:
Вопрос к вам что дальше делать? Правильно ли я решаю? задан 21 Фев '13 19:42 
SenjuHashirama |
|
$%m$% и $%n$% в этой задаче заменимы друг на друга и не равны, так что пусть $%m\gt n$%. отвечен 21 Фев '13 21:27 
chameleon честно говоря не понял как вы перешли к третьему равенству, можете поподробнее объяснить , если не сложно . P.S. задача за 10-ый класс
(21 Фев '13 21:30)
SenjuHashirama
По формуле НОД(x;y)=НОД(x-ky;y)
(21 Фев '13 21:40)
chameleon
Большинство стандартных задач на НОД и делимость так и решаются: используется то, что НОД двух чисел x, y равен НОДу любой линейной комбинации этих чисел.
(21 Фев '13 21:43)
chameleon
|
|
Хочу прокомментировать доказательство, данное @chameleon. Положим $%f_n=2^{2^n}+1$%. Пусть $%m>n$%; запишем $%m=n+k$%. Достаточно показать, что $%f_{n+k}-2$% делится на $%f_n$%. Тогда, если $%d$% есть НОД чисел $%f_n$% и $%f_{n+k}$%, то $%f_{n+k}-2$% делится на $%d$%, откуда $%2$% делится на $%d$%. Ввиду нечётности чисел Ферма, имеем $%d=1$%. Утверждение о делимости основано вот на каком соображении. Ясно, что $%x+1$% делит $%x^2-1$%, что в свою очередь делит $%x^4-1$%, делящее $%x^8-1$% и так далее, вплоть до $%x^{2^k}-1$%. Положим $%x=2^{2^n}$%. Ясно, что $%x+1=f_n$%, а также $$x^{2^k}-1=\left(2^{2^n}\right)^{2^k}-1=2^{2^{n+k}}-1=f_{n+k}-2,$$ откуда всё следует. отвечен 22 Фев '13 3:14 
falcao спасибо! так более понятно!
(22 Фев '13 7:34)
SenjuHashirama
|
