Задача
NT-B2-M01-P015 Два основания
#15
★★★★☆ Уровень 4 из 5
Пусть \(a>b>0\), \( \gcd(a,b)=1 \). Докажите, что \( \gcd(a^m-b^m,a^n-b^n)=a^{\gcd(m,n)}-b^{\gcd(m,n)} \).
Общий делитель взаимно прост с \(b\), значит можно работать с \(ab^{-1}\) по модулю этого делителя.
Пусть \(g=\gcd(m,n)\). Число \(a^g-b^g\) делит оба выражения. Обратно, пусть \(d\) делит оба. Так как \( \gcd(b,d)=1 \), существует обратный элемент \(b^{-1}\pmod d\). Из \(a^m\equiv b^m\) и \(a^n\equiv b^n\) получаем \((ab^{-1})^m\equiv1\) и \((ab^{-1})^n\equiv1\pmod d\). По алгоритму Евклида для показателей \((ab^{-1})^g\equiv1\pmod d\). Значит, \(a^g\equiv b^g\pmod d\), то есть \(d\mid a^g-b^g\).
Это ключевой шаблон для дальнейших задач на порядок по модулю.