模反元素

设${\displaystyle \mathrm {exgcd} (a,n)}$為扩展欧几里得算法的函数，則可得到${\displaystyle ax+ny=g}$，${\displaystyle g}$是${\displaystyle a}$, ${\displaystyle n}$的最大公因数。

则该模反元素存在，根據結果${\displaystyle ax+ny=1}$

在${\displaystyle {\bmod {n}}}$之下，${\displaystyle ax+ny\equiv ax\equiv 1}$，根據模反元素的定義${\displaystyle a\cdot a^{-1}\equiv 1}$，此時${\displaystyle x}$即為${\displaystyle a}$关于模${\displaystyle n}$的其中一個模反元素。

事實上，${\displaystyle x+kn(k\in \mathbb {Z} )}$ 都是${\displaystyle a}$关于模${\displaystyle n}$的模反元素，這裡我們取最小的正整數解${\displaystyle x\mod n}$（${\displaystyle x<n}$）。

则该模反元素不存在。

因為根據結果${\displaystyle ax+ny\neq 1}$，在${\displaystyle {\bmod {n}}}$ 之下，${\displaystyle ax\equiv g(g<n)}$不會同餘於${\displaystyle 1}$，因此滿足${\displaystyle a\cdot a^{-1}\equiv 1}$的${\displaystyle a^{-1}}$不存在。

歐拉定理證明當${\displaystyle a,n}$為兩個互質的正整數時，則有${\displaystyle a^{\varphi (n)}\equiv 1{\pmod {n}}}$，其中${\displaystyle \varphi (n)}$為歐拉函數（小於${\displaystyle n}$且與${\displaystyle n}$互質的正整數個數）。

上述結果可分解為${\displaystyle a^{\varphi (n)}=a\cdot a^{\varphi (n)-1}\equiv 1{\pmod {n}}}$，其中${\displaystyle a^{\varphi (n)-1}}$即為${\displaystyle a}$關於模${\displaystyle n}$之模反元素。