证明欧几里得定理（这是一位刚学数论的初三生发明的方法）

欧几里得定理： gcd ( a , b ) = gcd ( b , a % b ) \text{gcd}(a,b)=\text{gcd}(b,a\%b) gcd(a,b)=gcd(b,a%b)

证明如下：

设： g = gcd ( a , b ) g=\text{gcd}(a,b) g=gcd(a,b)， a = k 1 × g a=k_1 \times g a=k1​×g， b = k 2 × g b=k_2 \times g b=k2​×g

其中 k 1 , k 2 k_1,k_2 k1​,k2​ 满足条件 gcd ( k 1 , k 2 ) = 1 \text{gcd}(k_1,k_2)=1 gcd(k1​,k2​)=1

则问题转化为证明：

gcd ( k 2 × g , ( k 1 − t × k 2 ) × g ) = g \text{gcd}(k_2 \times g,(k_1-t \times k_2) \times g)=g gcd(k2​×g,(k1​−t×k2​)×g)=g，其中 t = ⌊ k 1 / k 2 ⌋ t=\lfloor k1 / k2 \rfloor t=⌊k1/k2⌋

g × gcd ( k 2 , k 1 − t × k 2 ) = g g \times \text{gcd}(k_2,k_1-t \times k_2)=g g×gcd(k2​,k1​−t×k2​)=g

gcd ( k 2 , k 1 − t × k 2 ) = 1 \text{gcd}(k_2,k_1-t \times k_2)=1 gcd(k2​,k1​−t×k2​)=1

则问题转化为证明：

gcd ( k 2 , k 1 − t × k 2 ) = 1 \text{gcd}(k_2,k_1-t \times k_2)=1 gcd(k2​,k1​−t×k2​)=1

运用 我今天刚学的 反证法：

设 gcd ( k 2 , k 1 − t × k 2 ) = v \text{gcd}(k_2,k_1-t \times k_2)=v gcd(k2​,k1​−t×k2​)=v，其中 v ≠ 1 v \neq 1 v=1

设 k 2 = p 1 × v k_2=p_1 \times v k2​=p1​×v， ( k 1 − t × k 2 ) = p 2 × v (k_1-t \times k_2)=p_2 \times v (k1​−t×k2​)=p2​×v

k 1 = p 2 × v + t × p 1 × v k_1=p_2 \times v + t \times p1 \times v k1​=p2​×v+t×p1×v

k 1 = v × ( p 2 + t × p 1 ) k_1=v \times (p_2+t \times p_1) k1​=v×(p2​+t×p1​)

所以 k 1 k_1 k1​， k 2 k_2 k2​ 有共同因子 v v v，与 gcd ( k 1 , k 2 ) = 1 \text{gcd}(k_1,k_2)=1 gcd(k1​,k2​)=1 矛盾。

所以 gcd ( k 2 , k 1 − t × k 2 ) = 1 \text{gcd}(k_2,k_1-t \times k_2)=1 gcd(k2​,k1​−t×k2​)=1。

所以 g × gcd ( k 2 , k 1 − t × k 2 ) = g g \times \text{gcd}(k_2,k_1-t \times k_2)=g g×gcd(k2​,k1​−t×k2​)=g

所以 gcd ( k 2 × g , ( k 1 − t × k 2 ) × g ) = g \text{gcd}(k_2 \times g,(k_1-t \times k_2) \times g)=g gcd(k2​×g,(k1​−t×k2​)×g)=g

所以 gcd ( a , b ) = gcd ( b , a % b ) \text{gcd}(a,b)=\text{gcd}(b,a\%b) gcd(a,b)=gcd(b,a%b)

证毕。

欢迎在评论区找bug，我会尽快回复。