Задача
NT-B2-M04-P015 Обратный через степень
#15
★★★★☆ Уровень 4 из 5
Пусть \(\gcd(a,n)=1\). Докажите, что \(a^{\varphi(n)-1}\) является обратным к \(a\) по модулю \(n\).
Умножьте на \(a\) и примените Эйлера.
По теореме Эйлера \(a^{\varphi(n)}\equiv1\pmod n\). Но \(a\cdot a^{\varphi(n)-1}=a^{\varphi(n)}\). Значит, \(a^{\varphi(n)-1}\) действительно является обратным элементом.
Связывает Эйлера с обратными элементами для составного модуля.