Problem
NT-B2-M03-P007 GCD of Exponents
#7
★★★☆☆ Level 3 of 5
Let \( \gcd(a,m)=1 \), \(a^r\equiv1\pmod m\), and \(a^s\equiv1\pmod m\). Prove that \(a^{\gcd(r,s)}\equiv1\pmod m\).
Let \(d=\operatorname{ord}_m(a)\).
If \(d=\operatorname{ord}_m(a)\), then \(a^r\equiv1\) and \(a^s\equiv1\) imply \(d\mid r\) and \(d\mid s\). Therefore \(d\mid\gcd(r,s)\), hence \(a^{\gcd(r,s)}\equiv1\pmod m\).
An alternative is Bezout's identity, but order is shorter.