Задача
NT-B1-M11-P020 НОД степенных чисел
#20
★★★☆☆ Уровень 3 из 5
Докажите, что \(\gcd(2^m-1,2^n-1)=2^{\gcd(m,n)}-1\).
Повторите алгоритм Евклида на показателях.
Если \(m\ge n\), то \(2^m-1=(2^{m-n})(2^n-1)+(2^{m-n}-1)\). Поэтому НОД не меняется при замене пары \((m,n)\) на \((m-n,n)\). Повторяя алгоритм Евклида для показателей, приходим к \((d,d)\), где \(d=\gcd(m,n)\). Тогда НОД равен \(2^d-1\).
Важная формула, но в книге 1 даётся через понятный Евклид.