Problem
NT-B2-M04-P015 Inverse Through a Power
#15
★★★★☆ Level 4 of 5
Let \(\gcd(a,n)=1\). Prove that \(a^{\varphi(n)-1}\) is the inverse of \(a\) modulo \(n\).
Multiply by \(a\) and apply Euler.
Euler's theorem gives \(a^{\varphi(n)}\equiv1\pmod n\). But \(a\cdot a^{\varphi(n)-1}=a^{\varphi(n)}\). Hence \(a^{\varphi(n)-1}\) is indeed the inverse.
Connects Euler with inverses modulo a composite number.