概述
gcd(a,b)=gcd(b,a%b) g c d ( a , b ) = g c d ( b , a % b ) .
证明：
设
r=gcd(a,b)
r
=
g
c
d
(
a
,
b
)
那么存在
r|a,r|b
r
|
a
,
r
|
b
.
又因为
a%b=a−a/b∗b=a−k∗b
a
%
b
=
a
−
a
/
b
∗
b
=
a
−
k
∗
b
.
a−k∗b
a
−
k
∗
b
是
a
a
和的一个线性组合，因此
r|(a%b)
r
|
(
a
%
b
)
。
所以
a
a
和的公约数同样是
b
b
和的公约数，那么他们的最大公约数当然也是相同的。
扩展欧几里得
求解
ax+by=gcd(a,b)
a
x
+
b
y
=
g
c
d
(
a
,
b
)
的任意解。
令
ax1+by1=gcd(a,b)
a
x
1
+
b
y
1
=
g
c
d
(
a
,
b
)
bx2+(a%b)y2
b
x
2
+
(
a
%
b
)
y
2
=bx2+(a−⌊ab⌋∗b)y2
=
b
x
2
+
(
a
−
⌊
a
b
⌋
∗
b
)
y
2
=b(x2−⌊ab⌋y2)+ay2
=
b
(
x
2
−
⌊
a
b
⌋
y
2
)
+
a
y
2
=ax1+by1
=
a
x
1
+
b
y
1
所以得到等式
y1=x2−⌊ab⌋y2
y
1
=
x
2
−
⌊
a
b
⌋
y
2
x1=y2
x
1
=
y
2
当
b=0
b
=
0
时，返回
x=1,y=0
x
=
1
,
y
=
0
.
以上我们可以得到一组特解，对于通解， 我们只要考虑
当
x
x
发生变化时，需要改变多少才是有效解。
x=x0+b/Gcd(a,b)∗t
x
=
x
0
+
b
/
G
c
d
(
a
,
b
)
∗
t
y=y0−a/Gcd(a,b)∗t(其中t为任意整数)
y
=
y
0
−
a
/
G
c
d
(
a
,
b
)
∗
t
(
其
中
t
为
任
意
整
数
)
先到这里了，拜拜=v=
最后
以上就是高贵火龙果为你收集整理的朝花夕拾之欧几里得的全部内容，希望文章能够帮你解决朝花夕拾之欧几里得所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
![[朝花夕拾C语言]：排序函数qsort详细讲解前言一、整型的冒泡（bubble）排序二、排序函数qsort的快捷使用三、sizeof（）和strlen（）的异同点 总结](/uploads/reation/bcimg5.png)
![[朝花夕拾C语言]c语言：矩阵交换](/uploads/reation/bcimg7.png)
![[C语言朝花夕拾] C语言中的命令行输入参数判断](/uploads/reation/bcimg9.png)
![[朝花夕拾C语言]c语言：杨辉三角形](/uploads/reation/bcimg10.png)
发表评论 取消回复