Задача
NT-B1-M07-P018 Обратный элемент через степень
#18
★★★☆☆ Уровень 3 из 5
Пусть \(p\) - простое число и \(p\nmid a\). Докажите, что \(a^{p-2}\) является обратным к \(a\) по модулю \(p\).
Умножьте \(a^{p-2}\) на \(a\).
По Ферма \(a^{p-1}\equiv1\pmod p\). Но \(a\cdot a^{p-2}=a^{p-1}\). Следовательно, \(a\cdot a^{p-2}\equiv1\pmod p\), то есть \(a^{p-2}\) - обратный элемент.
Это важная идея для дальнейших линейных сравнений.