Задача
NT-B1-M02-P021 Общая формула для \(a^m-1\)
#21
★★★★☆ Уровень 4 из 5
Докажите, что для целого \(a>1\) и положительных \(m,n\)
\[\gcd(a^m-1,a^n-1)=a^{\gcd(m,n)}-1.\]
Повторите алгоритм Евклида на показателях: если \(m=qn+r\), то \(a^m-1\) по модулю \(a^n-1\) связано с \(a^r-1\).
Пусть \(m\ge n\) и \(m=qn+r\). Так как \(a^n\equiv1\pmod{a^n-1}\), имеем \(a^m=a^{qn+r}\equiv a^r\pmod{a^n-1}\). Поэтому \(\gcd(a^m-1,a^n-1)=\gcd(a^r-1,a^n-1)\). Это ровно шаг алгоритма Евклида для пары показателей \((m,n)\). Повторяя, приходим к \(d=\gcd(m,n)\). Тогда НОД равен \(a^d-1\).
Это ключевая формула модуля и мост к более сильной теории чисел.