Задача
NT-B2-M03-P007 НОД показателей
#7
★★★☆☆ Уровень 3 из 5
Пусть \( \gcd(a,m)=1 \), \(a^r\equiv1\pmod m\) и \(a^s\equiv1\pmod m\). Докажите, что \(a^{\gcd(r,s)}\equiv1\pmod m\).
Пусть \(d=\operatorname{ord}_m(a)\).
Если \(d=\operatorname{ord}_m(a)\), то из \(a^r\equiv1\) и \(a^s\equiv1\) следует \(d\mid r\) и \(d\mid s\). Поэтому \(d\mid\gcd(r,s)\), а значит \(a^{\gcd(r,s)}\equiv1\pmod m\).
Альтернатива - использовать тождество Безу, но порядок короче.