∀a,b∈Z\forall a,b\in \mathbb{Z}∀a,b∈Z，不失一般性，设 a>ba>ba>b，则 gcd⁡(a,b)=gcd⁡(b,a mod b)\gcd(a, b) = \gcd(b, a\tmod b)gcd(a,b)=gcd(b,a mod b)，不断迭代至其中较小的一项等于 000 为止，此时的非 000 项就是答案。

如果 a mod b=ra\tmod b = ra mod b=r，也可写作 gcd⁡(a,b)=gcd⁡(b,r)\gcd(a,b)=\gcd(b,r)gcd(a,b)=gcd(b,r)。

令 a=kb+ra=kb+ra=kb+r，我们需要证明 gcd⁡(a,b)=gcd⁡(b,r)\gcd(a,b)=\gcd(b,r)gcd(a,b)=gcd(b,r)。

从 gcd⁡(a,b)\gcd(a,b)gcd(a,b) 出发，我们有：

gcd⁡(a,b)∣a∧gcd⁡(a,b)∣b  ⟹  gcd⁡(a,b)∣(a−kb)  ⟹  gcd⁡(a,b)∣r  ⟹  gcd⁡(a,b)≤gcd⁡(b,r) \begin{aligned} &\gcd(a,b)|a \land \gcd(a,b)|b \\\mathllap{\implies} & \gcd(a,b) | (a-kb) \\\mathllap{\implies} & \gcd(a,b) | r \\\mathllap{\implies} & \gcd(a,b)\le\gcd(b,r) \end{aligned} ​​​gcd(a,b)∣a∧gcd(a,b)∣bgcd(a,b)∣(a−kb)gcd(a,b)∣rgcd(a,b)≤gcd(b,r)​

关于 3→43\to43→4 的提示：考虑任意因子 q∣b,q∣rq|b, q|rq∣b,q∣r，易得 q≤gcd⁡(b,r)q\le\gcd(b,r)q≤gcd(b,r)。第三步我们证明了 gcd⁡(a,b)∣r\gcd(a,b)|rgcd(a,b)∣r，而我们自然有 gcd⁡(a,b)∣b\gcd(a,b)|bgcd(a,b)∣b，则 gcd⁡(a,b)≤gcd⁡(b,r)\gcd(a,b)\le\gcd(b,r)gcd(a,b)≤gcd(b,r)，即为第四步。

从 gcd⁡(b,r)\gcd(b,r)gcd(b,r) 出发，我们有：

gcd⁡(b,r)∣b∧gcd⁡(b,r)∣r  ⟹  gcd⁡(b,r)∣(kb+r)  ⟹  gcd⁡(b,r)∣a  ⟹  gcd⁡(b,r)≤gcd⁡(a,b) \begin{aligned} &\gcd(b,r)|b \land \gcd(b,r)|r \\\mathllap{\implies} & \gcd(b,r) | (kb+r) \\\mathllap{\implies} & \gcd(b,r) | a \\\mathllap{\implies} & \gcd(b,r)\le\gcd(a,b) \end{aligned} ​​​gcd(b,r)∣b∧gcd(b,r)∣rgcd(b,r)∣(kb+r)gcd(b,r)∣agcd(b,r)≤gcd(a,b)​

综合两式立即可得 gcd⁡(a,b)=gcd⁡(b,r)\gcd(a,b)=\gcd(b,r)gcd(a,b)=gcd(b,r)。

而易知 ∣r∣<∣b∣|r|<|b|∣r∣<∣b∣，我们总可在有限步后得到 b mod r=0b\tmod r=0b mod r=0，此时算法退出，我们得到的 rrr 就是答案，得证。◼

考虑 a,b,c,n∈Za,b,c,n\in\mathbb{Z}a,b,c,n∈Z，如果 ccc 和 nnn 互质，那么：

ca≡cb(modn)  ⟹  a≡b(modn) \smod{ca}{cb}{n}\implies\smod{a}{b}{n} ca≡cb(modn)⟹a≡b(modn)

• 封闭性：∀a,b∈(Z/nZ)×,gcd⁡(a,n)=1,gcd⁡(b,n)=1  ⟹  gcd⁡(ab,n)=1\forall a,b\in \Z{n}, \gcd(a,n) = 1, \gcd(b,n)=1\implies\gcd(ab,n)=1∀a,b∈(Z/nZ)×,gcd(a,n)=1,gcd(b,n)=1⟹gcd(ab,n)=1。由于 (Z/nZ)×\Z{n}(Z/nZ)× 包含了所有模 nnn 且与 nnn 互质的数，则 ab∈(Z/nZ)×ab\in\Z{n}ab∈(Z/nZ)×，得证。
• 交换律：由取余运算保持乘法运算律立即可证。
• 单位元：选择 e=1∈(Z/nZ)×e=1\in\Z{n}e=1∈(Z/nZ)×，易得 ∀a∈(Z/nZ)×,1⋅a≡a⋅1≡a(modn)\forall a\in\Z{n}, 1\cdot a\equiv a\cdot1\equiv a\pmod n∀a∈(Z/nZ)×,1⋅a≡a⋅1≡a(modn)，得证。
• 逆元：任选 a∈(Z/nZ)×a\in\Z{n}a∈(Z/nZ)×，我们有 gcd⁡(a,n)=1\gcd(a,n)=1gcd(a,n)=1，则根据裴蜀定理知 ax+yn=1ax+yn=1ax+yn=1 有解，则可得 1 mod n=ax  ⟹  ax≡1(modn)1\tmod n=ax\implies\smod{ax}{1}{n}1 mod n=ax⟹ax≡1(modn)；而 ax+yn=1ax+yn=1ax+yn=1 可以得出 gcd⁡(x,n)=1\gcd(x,n)=1gcd(x,n)=1，则 x∈(Z/nZ)×x\in\Z{n}x∈(Z/nZ)×。所以 xxx 为 aaa 的一个逆元。

则整数模 nnn 乘法构成一个群，得证。◼

对于互质整数 a,na, na,n，下面同余式恒成立：

aϕ(n)≡1(modn) \smod{a^{\phi(n)}}{1}{n} aϕ(n)≡1(modn)

如 nnn 为一个质数 ppp，有：

ap−1≡1(modp) \smod{a^{p-1}}{1}{p} ap−1≡1(modp)

上式即为费马小定理，可以看出来是欧拉定理的一个特殊形式。

考虑 (Z/nZ)×={p1,⋯ ,pϕ(n)}\Z{n}=\{p_1,\cdots,p_{\phi(n)}\}(Z/nZ)×={p1​,⋯,pϕ(n)​}，我们先证明 a(Z/nZ)×={ap1,⋯ ,apϕ(n)}a\Z{n}=\{ap_1,\cdots,ap_{\phi(n)}\}a(Z/nZ)×={ap1​,⋯,apϕ(n)​} 在模 nnn 意义下等于 (Z/nZ)×\Z{n}(Z/nZ)×。

• 元素是唯一的：假设存在 api≡apj(modn)\smod{ap_i}{ap_j}{n}api​≡apj​(modn)，那么自然有 n∣a(pi−pj)n|a(p_i-p_j)n∣a(pi​−pj​)，由于 aaa 以及 pi−pjp_i-p_jpi​−pj​ 均和 nnn 互质，产生矛盾，即不存在 api≡apj(modn)\smod{ap_i}{ap_j}{n}api​≡apj​(modn)，得证。
• 元素均在 (Z/nZ)×\Z{n}(Z/nZ)× 内：由于 aaa 和 nnn 互质，a∈(Z/nZ)×a\in\Z{n}a∈(Z/nZ)×，又由于 (Z/nZ)×\Z{n}(Z/nZ)× 是阿贝尔群，关于乘法运算封闭，则 ∀p∈(Z/nZ)×,ap∈(Z/nZ)×\forall p\in\Z{n},ap\in\Z{n}∀p∈(Z/nZ)×,ap∈(Z/nZ)×。

那立即可得 ∣a(Z/nZ)×∣=ϕ(n)|a\Z{n}|=\phi(n)∣a(Z/nZ)×∣=ϕ(n)，且元素两两不同，两个集合相等即证。

由于 (Z/nZ)×=a(Z/nZ)×\Z{n}=a\Z{n}(Z/nZ)×=a(Z/nZ)×，我们把两个集合的元素各求一个积，易得：

∏i=1ϕ(n)pi≡∏i=1ϕ(n)api(modn)∏i=1ϕ(n)pi≡aϕ(i)∏i=1ϕ(n)pi(modn) \begin{aligned} \prod_{i=1}^{\phi(n)}p_i&\equiv\prod_{i=1}^{\phi(n)}ap_i\pmod n \\\prod_{i=1}^{\phi(n)}p_i&\equiv a^{\phi(i)}\prod_{i=1}^{\phi(n)}p_i\pmod n \\\end{aligned} i=1∏ϕ(n)​pi​i=1∏ϕ(n)​pi​​≡i=1∏ϕ(n)​api​(modn)≡aϕ(i)i=1∏ϕ(n)​pi​(modn)​

由于 pip_ipi​ 均和 nnn 互质，可知 ∏i=1ϕ(n)pi\prod_{i=1}^{\phi(n)}p_i∏i=1ϕ(n)​pi​ 也与 nnn 互质。应用同余除法第一原理，立即可得 aϕ(i)≡1(modn)\smod{a^{\phi(i)}}{1}{n}aϕ(i)≡1(modn)，得证。◼

• 密钥对产生
  1. 任选两个足够大的质数 ppp 和 qqq，计算 n=pqn=pqn=pq。
  2. 计算 ϕ(n)=ϕ(p)×ϕ(q)=(p−1)(q−1)\phi(n)=\phi(p)\times\phi(q)=(p-1)(q-1)ϕ(n)=ϕ(p)×ϕ(q)=(p−1)(q−1)。丢弃 ppp 和 qqq。
  3. 选择一个 eee 满足 1<e<ϕ(n)1<e<\phi(n)1<e<ϕ(n) 且 gcd⁡(e,ϕ(n))=1\gcd(e,\phi(n))=1gcd(e,ϕ(n))=1，将 (n,e)(n, e)(n,e) 作为公钥。
  4. 选择一个 eee 的逆元 ddd 满足 ed≡1(modϕ(n))\smod{ed}{1}{\phi(n)}ed≡1(modϕ(n))，将 (n,d)(n, d)(n,d) 作为私钥。
• 加密：将信息编码为 mmm，其中 0<m<n0<m<n0<m<n。 计算 c=me mod nc=m^e\tmod nc=me mod n，ccc 即为加密后的信息。
• 解密：计算 m=cd mod nm=c^d\tmod nm=cd mod n, mmm 被还原。

关于加解密的正确性我们需要证明 med≡m(modn)\smod{m^{ed}}{m}{n}med≡m(modn)。

• mmm 和 nnn 互质

  由于 ed≡1(modϕ(n))\smod{ed}{1}{\phi(n)}ed≡1(modϕ(n))，则 ed=kϕ(n)+1ed=k\phi(n)+1ed=kϕ(n)+1，那么 med=mkϕ(n)+1=mkϕ(n)⋅mm^{ed}=m^{k\phi(n)+1}=m^{k\phi(n)}\cdot mmed=mkϕ(n)+1=mkϕ(n)⋅m。由欧拉定理可知 mϕ(n)≡1(modn)\smod{m^{\phi(n)}}{1}{n}mϕ(n)≡1(modn)，那么有 mkϕ(n)⋅m≡m(modn)\smod{m^{k\phi(n)}\cdot m}{m}{n}mkϕ(n)⋅m≡m(modn)，得证。

• mmm 和 nnn 不互质

  考察 med≡m(modn)\smod{m^{ed}}{m}{n}med≡m(modn)，对 nnn 分解因子有 med≡m(modp)\smod{m^{ed}}{m}{p}med≡m(modp) 和 med≡m(modq)\smod{m^{ed}}{m}{q}med≡m(modq)。我们现在要证明这两个式子。

  由于 p,qp, qp,q 均为质数，而 mmm 和 nnn 不互质，则 mmm 必为其中的一个整数倍。不失一般性，令 m=kpm=kpm=kp，则第一个式子立即得证。由于 m=kp<n=pqm=kp<n=pqm=kp<n=pq，则 k<pk<pk<p，可知 k∈(Z/pZ)×k\in\Z{p}k∈(Z/pZ)×，那么立即有 gcd⁡(kp,q)=1\gcd(kp, q)=1gcd(kp,q)=1。

  现在我们来证明第二个式子。由于 kpkpkp 和 qqq 一定互质，又有 ed≡1(modϕ(n))  ⟹  ed=h(p−1)(q−1)+1\smod{ed}{1}{\phi(n)}\implies ed=h(p-1)(q-1)+1ed≡1(modϕ(n))⟹ed=h(p−1)(q−1)+1，则：

  med≡mh(p−1)(q−1)+1(modq)≡(mq−1)h(p−1)⋅m(modq)≡(mϕ(q))h(p−1)⋅m(modq)≡m(modq) \begin{aligned} m^{ed}&\equiv m^{h(p-1)(q-1)+1}\pmod q \\&\equiv (m^{q-1})^{h(p-1)}\cdot m\pmod q \\&\equiv (m^{\phi(q)})^{h(p-1)}\cdot m\pmod q \\&\equiv m\pmod q \end{aligned} med​≡mh(p−1)(q−1)+1(modq)≡(mq−1)h(p−1)⋅m(modq)≡(mϕ(q))h(p−1)⋅m(modq)≡m(modq)​

  则原式得证。

所以 med≡m(modn)\smod{m^{ed}}{m}{n}med≡m(modn) 恒成立，正确性得证。◼