Математический форум Math Help Planet
Обсуждение и решение задач по математике, физике, химии, экономике Теоретический раздел |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
новый онлайн-сервис число, сумма и дата прописью |
|
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Страница 1 из 1 |
[ Сообщений: 8 ] |
|
Автор | Сообщение | |
---|---|---|
TOOFACK |
|
|
|
||
Вернуться к началу | ||
Li6-D |
|
|
Один общий множитель напрашивается [math]2^{20}-1[/math].
Для доказательства того, что других множителей нет рассмотрите множители разности чисел. |
||
Вернуться к началу | ||
За это сообщение пользователю Li6-D "Спасибо" сказали: TOOFACK |
||
Booker48 |
|
|
Ещё вариант: алгоритм Евклида, но числа представить в двоичной системе. Сразу видно, что остаток от деления 120 подряд написанных единиц на 100 подряд написанных единиц равен 20 подряд написанным единицам.
А [math]2^{100}-1[/math] делится на [math]2^{20}-1[/math] (20 подряд написанных единиц) нацело (делим банально уголком). Т.е. ответ ... ну, его уже Li6-D привёл. |
||
Вернуться к началу | ||
За это сообщение пользователю Booker48 "Спасибо" сказали: TOOFACK |
||
swan |
|
|
Докажите, что [math]\gcd(2^m-1, 2^n-1)=2^{\gcd(m, n)}-1[/math]
Алгоритмом Евклида |
||
Вернуться к началу | ||
cetrin |
|
|
[math]2^{20} - 1 = (2^{10} + 1)(2^{10} - 1)=1025\cdot 1023 = 3\cdot 5^2\cdot 11\cdot 31\cdot 41[/math]
|
||
Вернуться к началу | ||
Snaiver |
|
|
Ответ - 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 |
||
Вернуться к началу | ||
ammo77 |
|
|
Можно и так
[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] |
||
Вернуться к началу | ||
Exzellenz |
|
|
[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] |
||
Вернуться к началу | ||
[ Сообщений: 8 ] |
Похожие темы | Автор | Ответы | Просмотры | Последнее сообщение |
---|---|---|---|---|
Найти площадь треугольника ABC и найти величину угла C | 1 |
743 |
08 апр 2014, 14:59 |
|
Найти производную. Найти наименее удаленную точку
в форуме Дифференциальное исчисление |
1 |
404 |
14 апр 2018, 22:36 |
|
Найти производную f от x с помощью определителя, найти эл
в форуме Пределы числовых последовательностей и функций, Исследования функций |
1 |
633 |
01 июн 2015, 20:28 |
|
Найти изображение функции. Найти оригинал | 0 |
354 |
18 дек 2017, 18:20 |
|
Найти изображение. Найти оригинал | 1 |
139 |
06 дек 2019, 06:00 |
|
Найти df/dt
в форуме Дифференциальное исчисление |
2 |
885 |
20 май 2014, 13:23 |
|
Найти x
в форуме Алгебра |
5 |
187 |
25 дек 2017, 18:21 |
|
Найти
в форуме Начала анализа и Другие разделы школьной математики |
1 |
265 |
07 сен 2014, 17:59 |
|
Найти Y
в форуме Алгебра |
3 |
194 |
09 мар 2017, 14:27 |
|
Найти a,b,c и d
в форуме Тригонометрия |
1 |
304 |
03 дек 2014, 09:21 |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Кто сейчас на конференции |
Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 9 |
Вы не можете начинать темы Вы не можете отвечать на сообщения Вы не можете редактировать свои сообщения Вы не можете удалять свои сообщения Вы не можете добавлять вложения |