专栏文章

gcd更相减损术的证明

zzjpwwc
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mipor40b
此快照首次捕获于
2025/12/03 15:28
3 个月前
此快照最后确认于
2025/12/03 15:28
3 个月前
查看原文
试证明：gcd(a,b)=gcd(b−a,b)gcd(a,b)=gcd(b-a,b)
证明如下：
设 gcd(a,b)=dgcd(a,b)=d，a=k1da=k_1d，b=k2db=k_2d
则 gcd(k1,k2)=1gcd(k_1,k_2)=1
∴gcd(b−a,b)=gcd((k2−k1)d,k1d)gcd(b-a,b)=gcd((k_2-k_1)d,k_1d)
=d∗gcd(k2−k1,k1)=d*gcd(k_2-k_1,k_1)
发现若 gcd(k2−k1,k1)=1gcd(k_2-k_1,k_1)=1，则得证
假设gcd(k2−k1,k1)=ggcd(k_2-k_1,k_1)=g
设 k2−k1=t1gk_2-k_1=t_1g，k1=t2gk_1=t_2g
{k2−k1=t1g①k1=t2g②\begin{cases} k_2-k_1=t_1g &①\\ k_1=t_2g &②\\ \end{cases}
由②式，g∣k1g|k_1
由①式+②式，k2=(t1+t2)gk_2=(t_1+t_2)g
∴g∣k2g|k_2
∴g∣k1g|k_1 并且 g∣k2g|k_2
∵gcd(k1,k2)=1gcd(k_1,k_2)=1
∴ g=1g=1
∴gcd(k2−k1,k1)=1gcd(k_2-k_1,k_1)=1
∴gcd(a,b)=gcd(b−a,b)gcd(a,b)=gcd(b-a,b)
证毕。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...