Задача:
Докажите, что если $%m$% и $%n$% различные натуральные числа, то числа $%{2^{{2^m}}}+1$% и $%{2^{{2^n}}}+1$% не имеют общих делителей больших единицы.
Как я пытался решить:

  1. Я пробовал доказать от противного , то есть пусть есть такой k-общий делитель, причем k натуральный.
  2. Задача сводится к тому чтобы доказать, что k не натуральный
  3. Если данные числа кратны k, то их можно представить как $%kp={2^{{2^m}}}+1$% и $%kq={2^{{2^n}}}+1$%, где k и p также натуральны
  4. Затем переношу единицу влевую часть равенства и логарифмирую оба выражения по основанию 2, затем делю их друг на друга и получаю: $$2^{m-n}=log _{kq-1} (kp-1)$$ (забыл написать, пусть $%m>n$%, тогда $%p>q$%)

Вопрос к вам что дальше делать? Правильно ли я решаю?

задан 21 Фев '13 19:42

изменен 21 Фев '13 20:45

Deleted's gravatar image


126

10|600 символов нужно символов осталось
2

$%m$% и $%n$% в этой задаче заменимы друг на друга и не равны, так что пусть $%m\gt n$%.
$$2^{2^m}+1=2+2^{2^m}-1=2+\sum_{i=0}^{2^{m-n-1}-1}\left(2^{2^{n+1}i}\left(2^{2^{n+1}}-1\right)\right)=2+\left(2^{2^n}+1\right)\left(2^{2^n}-1\right)\sum_{i=0}^{2^{m-n-1}-1}2^{2^{n+1}i}$$ Следовательно, $%НОД\left(2^{2^m}+1;2^{2^n}+1\right)=НОД\left(2^{2^n}+1;2\right)=1$%, ч.т.д.
Остается только добавить, что $%m\gt n\Rightarrow m-n-1\ge0\Rightarrow2^{m-n-1}-1\ge0$%, а значит мы вправе были ставить значок суммы.

ссылка

отвечен 21 Фев '13 21:27

честно говоря не понял как вы перешли к третьему равенству, можете поподробнее объяснить , если не сложно . 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
10|600 символов нужно символов осталось
3

Хочу прокомментировать доказательство, данное @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

изменен 22 Фев '13 14:27

спасибо! так более понятно!

(22 Фев '13 7:34) SenjuHashirama
10|600 символов нужно символов осталось
1

Нет, логарифмирования не надо, это выводит нас из области целых чисел. Можно, например, вычесть два числа друг из друга или сложить (с какими-нибудь коэффициентами). Результат снова будет делиться на k.

ссылка

отвечен 21 Фев '13 21:16

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×2,395
×652

задан
21 Фев '13 19:42

показан
1240 раз

обновлен
22 Фев '13 14:27

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru