点个关注吧谢谢！！
前一章里面我们已经证明了对任意的整数
a
,
b
a,b
a,b，存在整数
x
,
y
x,y
x,y，使得其满足
g
c
d
(
a
,
b
)
=
a
x
+
b
y
gcd(a,b)=ax+by
gcd(a,b)=ax+by
从这一条们们可以扩展得到:
设
a
,
b
a,b
a,b是不全为0的整数，
g
c
d
(
a
,
b
)
=
1
gcd(a,b)=1
gcd(a,b)=1当且仅当存在整数
x
,
y
x,y
x,y使得
a
x
+
b
y
=
1
ax+by=1
ax+by=1。
必要性：
g
c
d
(
a
,
b
)
=
a
x
+
b
y
gcd(a,b)=ax+by
gcd(a,b)=ax+by的特例
充分性：当存在整数
x
,
y
x,y
x,y使得
a
x
+
b
y
=
1
ax+by=1
ax+by=1时，根据整除性质知道
g
c
d
(
a
,
b
)
∣
a
x
+
b
y
→
g
c
d
(
a
,
b
)
∣
1
gcd(a,b)|ax+by\rightarrow gcd(a,b)|1
gcd(a,b)∣ax+by→gcd(a,b)∣1，所以
g
c
d
(
a
,
b
)
=
1
gcd(a,b)=1
gcd(a,b)=1
( g c d ( a , b ) ∣ a x + b y : a = g c d ( a , b ) r , b = g c d ( a , b ) y ; a x + b y = g c d ( a , b ) ( r x + k y ) → g c d ( a , b ) ∣ a x + b y gcd(a,b)|ax+by:a=gcd(a,b)r,b=gcd(a,b)y;ax+by=gcd(a,b)(rx+ky)\rightarrow gcd(a,b)|ax+by gcd(a,b)∣ax+by:a=gcd(a,b)r,b=gcd(a,b)y;ax+by=gcd(a,b)(rx+ky)→gcd(a,b)∣ax+by)
性质：对于不为0的数 a , b , c a,b,c a,b,c
1.若
c
∣
a
b
,
g
c
d
(
a
,
c
)
=
1
c|ab,gcd(a,c)=1
c∣ab,gcd(a,c)=1，那么
c
∣
b
c|b
c∣b
证：因为
g
c
d
(
a
,
c
)
=
1
gcd(a,c)=1
gcd(a,c)=1，所以存在关系
a
x
+
c
y
=
1
ax+cy=1
ax+cy=1，两边乘以
b
b
b得到
a
b
x
+
c
b
y
=
b
→
c
∣
(
a
b
x
+
c
b
y
)
abx+cby=b\rightarrow c|(abx+cby)
abx+cby=b→c∣(abx+cby)，所以
c
∣
b
c|b
c∣b
2.若
a
∣
c
,
b
∣
c
,
g
c
d
(
a
,
b
)
=
1
a|c,b|c,gcd(a,b)=1
a∣c,b∣c,gcd(a,b)=1，则
a
b
∣
c
ab|c
ab∣c
证：同理
a
x
+
b
y
=
1
→
a
c
x
+
b
c
y
=
c
ax+by=1\rightarrow acx+bcy=c
ax+by=1→acx+bcy=c，由于
a
∣
c
a|c
a∣c，所以
a
b
∣
b
c
y
ab|bcy
ab∣bcy;
b
∣
c
b|c
b∣c，所以
a
b
∣
a
c
x
ab|acx
ab∣acx。所以
a
b
∣
(
a
c
x
+
b
c
y
)
=
c
ab|(acx+bcy)=c
ab∣(acx+bcy)=c
3.若
g
c
d
(
a
,
c
)
=
1
,
g
c
d
(
b
,
c
)
=
1
gcd(a,c)=1,gcd(b,c)=1
gcd(a,c)=1,gcd(b,c)=1，那么
g
c
d
(
a
b
,
c
)
=
1
gcd(ab,c)=1
gcd(ab,c)=1
证：
a
x
+
c
y
=
1
;
b
r
+
c
k
=
1
ax+cy=1;br+ck=1
ax+cy=1;br+ck=1两个等式乘起来得到
t
a
b
+
q
c
=
1
tab+qc=1
tab+qc=1。系数
t
,
q
t,q
t,q我就不计算了，直接乘起来合并就得到了。
思考:
g
c
d
(
a
,
b
,
c
)
=
g
c
d
(
g
c
d
(
a
,
b
)
,
c
)
gcd(a,b,c)=gcd(gcd(a,b),c)
gcd(a,b,c)=gcd(gcd(a,b),c)
提示：分别证
g
c
d
(
a
,
b
,
c
)
∣
g
c
d
(
g
c
d
(
a
,
b
)
,
c
)
gcd(a,b,c)|gcd(gcd(a,b),c)
gcd(a,b,c)∣gcd(gcd(a,b),c)和
g
c
d
(
g
c
d
(
a
,
b
)
,
c
)
∣
g
c
d
(
a
,
b
,
c
)
gcd(gcd(a,b),c)|gcd(a,b,c)
gcd(gcd(a,b),c)∣gcd(a,b,c)
