Ответ: НОД$2^{1}00-1,2^{5}0-1$ = 2^50 − 1 = 1 125 899 906 842 623.

Почему:

Общий факт: для целого a > 1 и целых m,n верно gcd$a^m-1,a^n-1$ = a^{gcd$m,n$} − 1. Частный и простой случай: если m кратно n, то a^n − 1 делит a^m − 1.Здесь 50 | 100, значит 2^50 − 1 делит 2^100 − 1 $ведь2^{1}00-1=(2^{5}0{)}^2-1=(2^{5}0-1)(2^{5}0+1)$. Следовательно НОД равен 2^50 − 1.

Короткое доказательство общего факта:

Пусть d = gcd$m,n$. Тогда a^d − 1 делит оба числа $еслиd|m,n$. Обратно, пусть g = gcd$a^m-1,a^n-1$. Тогда a^m ≡ 1 $modg$ и a^n ≡ 1 $modg$, поэтому порядок a по модулю g делит и m, и n, значит делит d, следовательно a^d ≡ 1 $modg$ и g | $a^d-1$. Имеем равенство.

Какие алгоритмы применять и почему:

Лучший подход здесь — использовать алгебраическое свойство степеней $делимостьa^m-1приm|n$. Это даёт ответ мгновенно и без вычисления огромных чисел.Алгоритм Евклида формально тоже подошёл бы: при делении 2^100 − 1 на 2^50 − 1 остаток равен 0 $из-заделимости$, так что Евклид завершился бы за один шаг. Но чтобы увидеть это на практике, выгоднее пользоваться факторизацией по степеням, как выше.Бинарный алгоритм $Stein$ для НОД хорош для общих больших целых чисел в битовой реализации, но здесь он избыточен: структура степеней даёт простое решение.Полная факторизация чисел $разложениенапростыемножители$ — это тяжёлая задача и ненужная в данном случае, поскольку НОД получаем без факторизации.

Итого: применяем свойство степеней $делимостьприm|n$ — это самый быстрый и логичный путь.