Как найти нод у 2^100 - 1 и 2^120 - 1

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

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

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

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

Ответ - 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