2014 dxdy logo

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

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


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 НОД хитрых чисел
Сообщение09.08.2015, 01:40 


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

Найти НОД чисел: 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 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: НОД хитрых чисел
Сообщение09.08.2015, 08:28 
Аватара пользователя


29/06/15
277
[0,\infty )
1 задача. Пользуясь
Andrey A в сообщении #1043580 писал(а):
$a\mid b\Rightarrow 2^a-1\mid 2^b-1.$
,найдите остаток от деления большего из них на меньшее
2 задача.Считая, что числа разные, от большего отнимите 2 и поделите на меньшее

 Профиль  
                  
 
 Re: НОД хитрых чисел
Сообщение14.08.2015, 01:10 


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

 Профиль  
                  
 
 Re: НОД хитрых чисел
Сообщение14.08.2015, 08:23 
Аватара пользователя


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

 Профиль  
                  
 
 Re: НОД хитрых чисел
Сообщение14.08.2015, 08:34 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: НОД хитрых чисел
Сообщение14.08.2015, 09:00 


20/01/12
194
iancaple в сообщении #1045181 писал(а):
Задача 1.

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

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

 Профиль  
                  
 
 Re: НОД хитрых чисел
Сообщение16.08.2015, 20:03 


04/06/13
203
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 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: НОД хитрых чисел
Сообщение16.08.2015, 22:08 
Заслуженный участник
Аватара пользователя


24/02/12
1842
Москва
karandash_oleg в сообщении #1045695 писал(а):
Пока что дальше не вижу.
Добавьте и вычтите $2^r $ в числителе.

 Профиль  
                  
 
 Re: НОД хитрых чисел
Сообщение16.08.2015, 22:35 


04/06/13
203
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 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: НОД хитрых чисел
Сообщение17.08.2015, 09:16 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: НОД хитрых чисел
Сообщение24.08.2015, 22:57 


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

 Профиль  
                  
 
 Re: НОД хитрых чисел
Сообщение24.08.2015, 23:00 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 17 ]  На страницу 1, 2  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group