モジュラ逆数
拡張ユークリッド互除法の代わりにオイラーの定理をモジュラ逆数の計算に利用することもできる。
オイラーの定理によれば、a が m と互いに素ならば、オイラー函数 φ(m) に対して
a φ ( m ) ≡ 1 ( mod m ) {\displaystyle a^{\varphi (m)}\equiv 1{\pmod {m}}}
が成り立つ。これは a が法 m に関する既約合同類群 ( Z / m Z ) × {\displaystyle (\mathbb {Z} /m\mathbb {Z} )^{\times }} に入るための必要十分条件が a が m と互いに素であることから従う。従って、モジュラ逆数が直接的に
a φ ( m ) − 1 ≡ a − 1 ( mod m ) {\displaystyle a^{\varphi (m)-1}\equiv a^{-1}{\pmod {m}}}
と求まる。これから、m が素数である特別の場合には、φ(m) = m − 1 ゆえ