初等数论--欧几里得算法

1. 定义

u 0   u 1 ∈ Z , u 1 ≠ 0 , u 1 ∤ u 0 u_0\ u_1\in Z,u_1 \ne0,u_1 \nmid u_0 u0​ u1​∈Z,u1​=0,u1​∤u0​

根据带余除法可得下面一系列等式 u 0 = q 0 u 1 + u 2 0 < u 2 < ∣ u 1 ∣ u 1 = q 0 u 2 + u 3 0 < u 3 < u 2 ⋯ u k − 1 = q k − 1 u k + u k + 1 0 < u k < u k u k = q k u k + 1 \begin{align*} u_0 &=q_0u_1+u_2\quad 0 < u_2 <\lvert u_1\rvert\\ u_1 &=q_0u_2+u_3\quad 0 < u_3 < u_2\\ \cdots \\ u_{k-1} &=q_{k-1}u_k + u_{k+1}\quad 0 < u_k <u_{k}\\ u_k &=q_ku_{k+1} \end{align*} u0​u1​⋯uk−1​uk​​=q0​u1​+u2​0<u2​<∣u1​∣=q0​u2​+u3​0<u3​<u2​=qk−1​uk​+uk+1​0<uk​<uk​=qk​uk+1​​

我们可以得到 0 < u k + 1 < u k < ⋯ < u 2 < ∣ u 1 ∣ 0 <u_{k+1} <u_k <\cdots<u_2 < \lvert u_1\rvert 0<uk+1​<uk​<⋯<u2​<∣u1​∣ 由于小于 ∣ u 1 ∣ |u_1| ∣u1​∣的正整数只有有限个，所以上面的过

程必定有限。

也就是要么 1 ≠ u k + 1 ∣ u k 1 \ne u_{k+1}\mid u_k 1=uk+1​∣uk​, 要么 1 = u k + 1 ∣ u k 1 = u_{k+1} \mid u_k 1=uk+1​∣uk​。

2. 结论 2.1 最大公因数

u k + 1 u_{k+1} uk+1​为 u 0   u 1 u_0\ u_1 u0​ u1​的最大公因数。

引理1 ∀ a , b ∈ Z ⇒ ∀ x ∈ Z , gcd ⁡ ( a , b ) = gcd ⁡ ( a , b + a x ) \forall a,b \in Z \Rightarrow\\ \forall x \in Z,\gcd(a,b)=\gcd(a,b+ax) ∀a,b∈Z⇒∀x∈Z,gcd(a,b)=gcd(a,b+ax)

运用该引理我们可以得到 gcd ⁡ ( u 0 , u 1 ) = gcd ⁡ ( u 1 , u 2 ) = ⋯ = gcd ⁡ ( u k , u k + 1 ) = u k + 1 \gcd(u_0,u_1)=\gcd(u_1,u_2)=\cdots=\\\gcd (u_k,u_{k+1})=u_{k+1} gcd(u0​,u1​)=gcd(u1​,u2​)=⋯=gcd(uk​,uk+1​)=uk+1​

2.2 裴祖系数的存在性

∃ x 0 , x 1 ∈ Z , s . t . x 0 u 0 + x 1 u 1 = gcd ⁡ ( u 0 , u 1 ) = u k + 1 \exists x_0,x_1 \in Z, s.t. \quad \\x_0u_0+x_1u_1=\gcd(u_0,u_1)=u_{k+1} ∃x0​,x1​∈Z,s.t.x0​u0​+x1​u1​=gcd(u0​,u1​)=uk+1​ 根据辗转相除法的等式，我们可以从直觉上看出 u 0 , u 1 u_0,u_1 u0​,u1​的线性组合可以表示 u k + 1 u_{k+1} uk+1​。

我们可以观察到下面的递推式：

[ u t + 1 u t ] = [ − q t − 1 1 1 0 ] [ u t u t − 1 ] \begin{bmatrix} u_{t+1}\\u_{t} \end{bmatrix}= \begin{bmatrix} -q_{t-1} & 1 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} u_{t}\\u_{t-1} \end{bmatrix} [ut+1​ut​​]=[−qt−1​1​10​][ut​ut−1​​]

因此容易得到 [ u k + 1 u k ] = [ − q k − 1 1 1 0 ] ⋯ [ − q 0 1 1 0 ] [ u 1 u 0 ] \begin{bmatrix} u_{k+1}\\u_{k} \end{bmatrix}=\\ \begin{bmatrix} -q_{k-1} & 1 \\ 1 & 0 \end{bmatrix} \cdots \begin{bmatrix} -q_{0} & 1 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} u_{1}\\u_{0} \end{bmatrix} [uk+1​uk​​]=[−qk−1​1​10​]⋯[−q0​1​10​][u1​u0​​]

2.2 引理1证明

首先 g c d ( a , b ) = g c d ( − a , b ) = g c d ( a , − b ) = g c d ( ∣ a ∣ , ∣ b ∣ ) gcd(a,b) =gcd(-a,b)=gcd(a,-b)=gcd(|a|,|b|) gcd(a,b)=gcd(−a,b)=gcd(a,−b)=gcd(∣a∣,∣b∣)。

因此我们只需要考虑 a , b > 0 a,b>0 a,b>0的情况。

容易得到 g c d ( a , b ) < min ⁡ ( a , b ) gcd(a,b)< \min(a,b) gcd(a,b)<min(a,b)，

又 g c d ( a x , a ) = a gcd(ax,a)=a gcd(ax,a)=a，即 ∀ d ∣ a ⇒ d ∣ a x \forall d \mid a \Rightarrow d \mid ax ∀d∣a⇒d∣ax.

因此 ∀ d ∣ a , d ∣ b + a x ⇔ ∀ d ∣ a , d ∣ b \forall d \mid a,d \mid b+ax \Leftrightarrow \forall d \mid a,d \mid b ∀d∣a,d∣b+ax⇔∀d∣a,d∣b

即 g c d ( a , b ) = g c d ( a , b + a x ) gcd(a,b) = gcd(a,b+ax) gcd(a,b)=gcd(a,b+ax)

3. 实现 递归 int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); } 迭代 int gcd_fast(int a, int b) { while (b) { int tmp = b; b = a % b; if (2 * b > tmp) b = tmp - b; a = tmp; } return a; } 参考

初等数论