НОД хитрых чисел

[karandash_oleg]

Здравствуйте! Помогите, пожалуйста, разобраться с задачей!

Найти НОД чисел: 1) $(2^m-1,2^n-1)$ 2) $(2^{2^m}+1,2^{2^m}+1)$

1) Если рассмотреть при $m=2$, $n=3$, то $NOD=1$.

Видимо тут нужно зависимость НОД от $n$ и $m$? Если да, то как? Нужно пытаться искать закономерности для маленьких $n,m$? Если да, то пока что не получилось найти

[Andrey A]

Повод для размышлений: $a\mid b\Rightarrow 2^a-1\mid 2^b-1.$ Поскольку суммы степенного ряда.
А второй случай действительно хитрый (если там все-таки разные показатели степени). Ферма думал, что НОД $=1$.

[iancaple]

1 задача. Пользуясь

Andrey A в сообщении #1043580 писал(а):

$a\mid b\Rightarrow 2^a-1\mid 2^b-1.$

,найдите остаток от деления большего из них на меньшее
2 задача.Считая, что числа разные, от большего отнимите 2 и поделите на меньшее

[karandash_oleg]

А как я найду остаток? В каком виде его нужно искать. Пока не очень понимаю вопрос. Малая теорема ферма здесь не пройдет, потому как степени не обязаны быть простыми, насколько я понимаю

[iancaple]

Задача 1.
В каком виде его нужно искать - это хороший вопрос. А в каком виде нужно искать ответ? Видимо, в виде функции от $m,n$. Но тогда $NOD(2^m-1,2^n-1)$ -чем не функция. В задаче утверждается, что существует более простая функция. Обозначьте пока $m=kn+r,\;0\leq r<n$

[ex-math]

Может быть сразу трудно.
Тогда для начала найдите какой-нибудь общий делитель, не обязательно наибольший. Пусть $d $ делит как $m $, так и $n $, тогда...

[=SSN=]

iancaple в сообщении #1045181 писал(а):

Задача 1.

Wiki:

Цитата:

Числа Мерсе́нна — числа вида $M = 2^n - 1.
Если M является простым, то число n также простое.

Простые числа Мерсенна.
Числа Мерсенна получили известность в связи с эффективным тестом простоты Люка — Лемера, благодаря которому простые числа Мерсенна давно удерживают лидерство как самые больши́е известные простые числа.

[karandash_oleg]

iancaple в сообщении #1045181 писал(а):

Задача 1.
В каком виде его нужно искать - это хороший вопрос. А в каком виде нужно искать ответ? Видимо, в виде функции от $m,n$. Но тогда $NOD(2^m-1,2^n-1)$ -чем не функция. В задаче утверждается, что существует более простая функция. Обозначьте пока $m=kn+r,\;0\leq r<n$

$\dfrac{(2^n)^k2^r-1}{2^n-1}$
Пока что дальше не вижу.

ex-math в сообщении #1045182 писал(а):

Может быть сразу трудно.
Тогда для начала найдите какой-нибудь общий делитель, не обязательно наибольший. Пусть $d $ делит как $m $, так и $n $, тогда...

А тут ясно, что тогда и $\dfrac{2^m-1}{2^n-1}$ целое. Это просто доказывается через формулу

$a^n-b^n=(a-b)(a^{n-1}+a^{n-2}b+a^{n-3}b^2+...+a^2b^{n-3}+ab^{n-2}+b^{n-1})$

Но как это обобщить -- не очевидно. Стоит ли расписывать док-во через эту формулу?

[ИСН]

Да, стоит. В процессе запишите полностью, буквами, все утверждения, которые собираетесь сделать, и посмотрите на них. Посмотрите на них, на смысл их. Разве $2^3-1$ делится на $2^2-1$, например? Зачем Вы говорите, что это так?

[ex-math]

karandash_oleg в сообщении #1045695 писал(а):

Пока что дальше не вижу.

Добавьте и вычтите $2^r $ в числителе.

[karandash_oleg]

ex-math в сообщении #1045736 писал(а):

karandash_oleg в сообщении #1045695 писал(а):

Пока что дальше не вижу.

Добавьте и вычтите $2^r $ в числителе.

Спасибо.

$\dfrac{(2^n)^k2^r-1}{2^n-1}=\dfrac{(2^n)^k2^r-2^r+2^r-1}{2^n-1}=2^r\cdot \dfrac{(2^n)^k-1}{2^{n}-1}+\dfrac{2^r-1}{2^n-1}=$

$=2^r\cdot (2^{n(k-1)}+2^{n(k-2)}+...+1)+\dfrac{2^r-1}{2^n-1}$

Правильно?

-- 16.08.2015, 22:42 --

ИСН в сообщении #1045713 писал(а):

Да, стоит. В процессе запишите полностью, буквами, все утверждения, которые собираетесь сделать, и посмотрите на них. Посмотрите на них, на смысл их. Разве $2^3-1$ делится на $2^2-1$, например? Зачем Вы говорите, что это так?

Да, действительно, это было неверно.

Пусть $d $ делит как $m $, так и $n $, тогда $m=d\cdot k$, $n=d\cdot s$

Теперь попытаюсь сократить дробь, пользуясь формулой для разности энных степеней.

А тут ясно, что тогда и $\dfrac{2^m-1}{2^n-1}=dfrac{2^{dk}-1}{2^{ds}-1}= $

$= \dfrac{2^{k(d-1)}+2^{k(d-2)}+...+1}{2^{n(d-1)}+2^{n(d-2)}+...+1}$

Правильно теперь?

[ИСН]

Правильно будет собрать все книги бы, да сжечь. В них много букв, а буквы запутывают. Вот и у Вас теперь тоже много букв, а толку? Вы сокращаете дробь. Зачем Вы сокращаете дробь? Нас разве просили сократить дробь? А что нас просили?

[ex-math]

Ну вот, остаток Вы нашли. А дальше есть такая вещь как алгоритм Евклида.

[karandash_oleg]

Имеется ввиду так $NOD(2^m-1,2^n-1)=NOD(2^r-1,2^n-1)$? А что это дает? В случае конкретных чисел запросто бы расписал алгоритм Евклида для них, тут же мне не очевидно...

[ИСН]

Да, так. Что даёт - ничего, если Вы уже забыли, что такое $r$. Я, например, забыл. Времени-то вон сколько прошло.