Дискуссионный математический форумМатематический форум
Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
новый онлайн-сервис
число, сумма и дата прописью

Часовой пояс: UTC + 3 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 8 ] 
Автор Сообщение
 Заголовок сообщения: Как найти нод у 2^100 - 1 и 2^120 - 1
СообщениеДобавлено: 02 дек 2019, 18:24 
Не в сети
Начинающий
Аватара пользователя
Зарегистрирован:
02 дек 2019, 18:21
Сообщений: 17
Cпасибо сказано: 8
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Как можно найти нод у таких больших чисел, пробовал считать - не получилось, так как числа довольно большие. Как быть?

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Как найти нод у 2^100 - 1 и 2^120 - 1
СообщениеДобавлено: 02 дек 2019, 19:35 
Не в сети
Beautiful Mind
Аватара пользователя
Зарегистрирован:
10 дек 2014, 20:21
Сообщений: 1204
Cпасибо сказано: 288
Спасибо получено:
679 раз в 545 сообщениях
Очков репутации: 148

Добавить очки репутацииУменьшить очки репутации
Один общий множитель напрашивается [math]2^{20}-1[/math].
Для доказательства того, что других множителей нет рассмотрите множители разности чисел.

Вернуться к началу
 Профиль  
Cпасибо сказано 
За это сообщение пользователю Li6-D "Спасибо" сказали:
TOOFACK
 Заголовок сообщения: Re: Как найти нод у 2^100 - 1 и 2^120 - 1
СообщениеДобавлено: 02 дек 2019, 20:17 
Не в сети
Light & Truth
Зарегистрирован:
02 дек 2016, 22:55
Сообщений: 5207
Cпасибо сказано: 340
Спасибо получено:
923 раз в 872 сообщениях
Очков репутации: 131

Добавить очки репутацииУменьшить очки репутации
Ещё вариант: алгоритм Евклида, но числа представить в двоичной системе. Сразу видно, что остаток от деления 120 подряд написанных единиц на 100 подряд написанных единиц равен 20 подряд написанным единицам. :)
А [math]2^{100}-1[/math] делится на [math]2^{20}-1[/math] (20 подряд написанных единиц) нацело (делим банально уголком). Т.е. ответ ... ну, его уже Li6-D привёл.

Вернуться к началу
 Профиль  
Cпасибо сказано 
За это сообщение пользователю Booker48 "Спасибо" сказали:
TOOFACK
 Заголовок сообщения: Re: Как найти нод у 2^100 - 1 и 2^120 - 1
СообщениеДобавлено: 02 дек 2019, 21:47 
Не в сети
Последняя инстанция
Зарегистрирован:
06 дек 2014, 09:11
Сообщений: 7070
Cпасибо сказано: 115
Спасибо получено:
1662 раз в 1508 сообщениях
Очков репутации: 283

Добавить очки репутацииУменьшить очки репутации
Докажите, что [math]\gcd(2^m-1, 2^n-1)=2^{\gcd(m, n)}-1[/math]
Алгоритмом Евклида

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Как найти нод у 2^100 - 1 и 2^120 - 1
СообщениеДобавлено: 02 дек 2019, 22:02 
Не в сети
Начинающий
Зарегистрирован:
30 ноя 2019, 08:51
Сообщений: 42
Cпасибо сказано: 0
Спасибо получено:
3 раз в 3 сообщениях
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
[math]2^{20} - 1 = (2^{10} + 1)(2^{10} - 1)=1025\cdot 1023 = 3\cdot 5^2\cdot 11\cdot 31\cdot 41[/math]

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Как найти нод у 2^100 - 1 и 2^120 - 1
СообщениеДобавлено: 24 мар 2023, 22:02 
Не в сети
Начинающий
Зарегистрирован:
24 мар 2023, 21:42
Сообщений: 1
Cпасибо сказано: 0
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Ответ - 2[math]^{20}[/math] - 1. Не уверен в рациональности но вот мое решение:

Для нахождения НОД можно воспользоваться алгоритмом Евклида. Сначала рассмотрим два числа, НОД которых нужно найти. Это 2[math]^{120}[/math]-1 и 2[math]^{100}[/math]-1. НОД этих двух чисел равен НОДу меньшего из них и остатку от деления меньшего на большее.




Поделим 2[math]^{120}[/math] - 1 на 2[math]^{100}[/math] - 1. Мы берем 2[math]^{20}[/math] раз, так как при умножении степени складываются. При делении уголком получаем, что остаток равен 2[math]^{120}[/math]-1 - 2[math]^{120}[/math]+2[math]^{20}[/math]. (+2[math]^{20}[/math], а не -2[math]^{20}[/math], т.к. мы вычитаем 2[math]^{120}[/math]-1 и все знаки меняются на противоположные). Теперь из выражения НОД(2[math]^{100}[/math]-1; 2[math]^{120}[/math]-1) мы получили НОД(2[math]^{100}[/math]-1; 2[math]^{20}[/math]-1). Теперь проделываем тоже самое, и получаем:

НОД(2[math]^{100}[/math]-1; 2[math]^{120}[/math]-1) = НОД(2[math]^{100}[/math]-1; 2[math]^{20}[/math]-1) = НОД(2[math]^{20}[/math]-1; 2[math]^{80}[/math]-1) = НОД(2[math]^{20}[/math]-1; 2[math]^{60}[/math]-1) = НОД(2[math]^{20}[/math]-1; 2[math]^{40}[/math]-1) = НОД(2[math]^{20}[/math]-1; 2[math]^{20}[/math]-1). Очевидно, что НОД(a; a) = a [math]\Rightarrow[/math] НОД(2[math]^{20}[/math]-1; 2[math]^{20}[/math]-1) = 2[math]^{20}[/math] - 1

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Как найти нод у 2^100 - 1 и 2^120 - 1
СообщениеДобавлено: 01 июн 2023, 11:46 
Не в сети
Beautiful Mind
Зарегистрирован:
17 апр 2019, 04:57
Сообщений: 1208
Откуда: Грузия
Cпасибо сказано: 99
Спасибо получено:
41 раз в 41 сообщениях
Очков репутации: 3

Добавить очки репутацииУменьшить очки репутации
Можно и так

[math]2^{100} - 1 \pmod{ 99 }[/math] [math]= 33[/math]
[math]2^{120} - 1 \pmod{ 99 }[/math] [math]= 0[/math]

[math]2^{100} - 1 \pmod{ 990 }[/math] [math]= 495[/math]
[math]2^{120} - 1 \pmod{ 990 }[/math] [math]= 825[/math]

т.е 3-5-11 гарантированно общий делитель ,
тогда остальные общие делители
2^(n)-1=(3*5*11*k)
2^(n)-1=(3*5*11*(-1/165 + 2^n/165))

[math]2^{20}[/math] [math]- 1[/math]=[math]165 \pmod{ 990 }[/math]

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Как найти нод у 2^100 - 1 и 2^120 - 1
СообщениеДобавлено: 01 июн 2023, 12:16 
Не в сети
Beautiful Mind
Аватара пользователя
Зарегистрирован:
21 дек 2021, 01:39
Сообщений: 1753
Cпасибо сказано: 81
Спасибо получено:
329 раз в 315 сообщениях
Очков репутации: 70

Добавить очки репутацииУменьшить очки репутации
[math]2^{120}-1=(2^{60}-1)(2^{60}+1)=(2^{30}-1)(2^{30}+1)(2^{60}+1)=(2^{15}-1)(2^{15}+1)(2^{30}+1)(2^{60}+1)[/math]

[math]2^{15}-1=32767=7 \cdot 31 \cdot 151;[/math] наименьший делитель [math]7.[/math]
[math]2^{15}+1=32769=3 \cdot 3 \cdot 11 \cdot 331;[/math] наименьший общий делитель [math]3.[/math]

Вернуться к началу
 Профиль  
Cпасибо сказано 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему      Страница 1 из 1 [ Сообщений: 8 ]

 Похожие темы   Автор   Ответы   Просмотры   Последнее сообщение 
Найти площадь треугольника ABC и найти величину угла C

в форуме Аналитическая геометрия и Векторная алгебра

tory_999

1

743

08 апр 2014, 14:59

Найти производную. Найти наименее удаленную точку

в форуме Дифференциальное исчисление

351w

1

404

14 апр 2018, 22:36

Найти производную f от x с помощью определителя, найти эл

в форуме Пределы числовых последовательностей и функций, Исследования функций

qvernaut

1

633

01 июн 2015, 20:28

Найти изображение функции. Найти оригинал

в форуме Комплексный анализ и Операционное исчисление

351w

0

354

18 дек 2017, 18:20

Найти изображение. Найти оригинал

в форуме Комплексный анализ и Операционное исчисление

351w

1

139

06 дек 2019, 06:00

Найти df/dt

в форуме Дифференциальное исчисление

pro100bantik

2

885

20 май 2014, 13:23

Найти x

в форуме Алгебра

ognit

5

187

25 дек 2017, 18:21

Найти

в форуме Начала анализа и Другие разделы школьной математики

Marilyn123164

1

265

07 сен 2014, 17:59

Найти Y

в форуме Алгебра

Bycufal

3

194

09 мар 2017, 14:27

Найти a,b,c и d

в форуме Тригонометрия

Renfri

1

304

03 дек 2014, 09:21


Часовой пояс: UTC + 3 часа [ Летнее время ]



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

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


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

Найти:
Перейти:  

Яндекс.Метрика

Copyright © 2010-2023 MathHelpPlanet.com. All rights reserved