2014 dxdy logo

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

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




На страницу 1, 2  След.
 
 НОД хитрых чисел
Сообщение09.08.2015, 01:40 
Здравствуйте! Помогите, пожалуйста, разобраться с задачей!

Найти НОД чисел: 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$? Если да, то пока что не получилось найти

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

 
 
 
 Re: НОД хитрых чисел
Сообщение09.08.2015, 08:28 
Аватара пользователя
1 задача. Пользуясь
Andrey A в сообщении #1043580 писал(а):
$a\mid b\Rightarrow 2^a-1\mid 2^b-1.$
,найдите остаток от деления большего из них на меньшее
2 задача.Считая, что числа разные, от большего отнимите 2 и поделите на меньшее

 
 
 
 Re: НОД хитрых чисел
Сообщение14.08.2015, 01:10 
А как я найду остаток? В каком виде его нужно искать. Пока не очень понимаю вопрос. Малая теорема ферма здесь не пройдет, потому как степени не обязаны быть простыми, насколько я понимаю

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

 
 
 
 Re: НОД хитрых чисел
Сообщение14.08.2015, 08:34 
Аватара пользователя
Может быть сразу трудно.
Тогда для начала найдите какой-нибудь общий делитель, не обязательно наибольший. Пусть $d $ делит как $m $, так и $n $, тогда...

 
 
 
 Re: НОД хитрых чисел
Сообщение14.08.2015, 09:00 
iancaple в сообщении #1045181 писал(а):
Задача 1.

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

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

 
 
 
 Re: НОД хитрых чисел
Сообщение16.08.2015, 20:03 
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})$

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

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

 
 
 
 Re: НОД хитрых чисел
Сообщение16.08.2015, 22:08 
Аватара пользователя
karandash_oleg в сообщении #1045695 писал(а):
Пока что дальше не вижу.
Добавьте и вычтите $2^r $ в числителе.

 
 
 
 Re: НОД хитрых чисел
Сообщение16.08.2015, 22:35 
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}$

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

 
 
 
 Re: НОД хитрых чисел
Сообщение16.08.2015, 22:58 
Аватара пользователя
Правильно будет собрать все книги бы, да сжечь. В них много букв, а буквы запутывают. Вот и у Вас теперь тоже много букв, а толку? Вы сокращаете дробь. Зачем Вы сокращаете дробь? Нас разве просили сократить дробь? А что нас просили?

 
 
 
 Re: НОД хитрых чисел
Сообщение17.08.2015, 09:16 
Аватара пользователя
Ну вот, остаток Вы нашли. А дальше есть такая вещь как алгоритм Евклида.

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

 
 
 
 Re: НОД хитрых чисел
Сообщение24.08.2015, 23:00 
Аватара пользователя
Да, так. Что даёт - ничего, если Вы уже забыли, что такое $r$. Я, например, забыл. Времени-то вон сколько прошло.

 
 
 [ Сообщений: 17 ]  На страницу 1, 2  След.


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