裴蜀定理

1 内容:

2 设 a,b 是不全为零的整数,则存在整数 x,y, 使得 ax+by=gcd(a,b).

2.1 证明:

设取 x0, y0 时,ax+by 的最小整数是 s.即 ax0+by0 = s

gcd(a,b)|ax0gcd(a,b)|ay0

所以 gcd(a,b)|s .........(1)

a=qs+r(0rs)

r=aqs=aq(ax0+by0)=a(1qx0)+b(qy0)=ax+by

因为 s 是最小整数,r=0

所以 s|a,同理 s|b

s|gcd(a,b) ..........(2)

(1)(2) 可得 s=gcd(a,b).

证毕。

3 逆定理:

a,b 是不全为零的整数,若 d>0a,b 的公因数,且存在整数x,y, 使得 ax+by=d,则 d=gcd(a,b)

特殊地,设 a,b 是不全为零的整数,若存在整数 x,y, 使得 ax+by=1,则 a,b 互质。

4 进一步结论:

对自然数 ab 和整数 nab 互素,考察不定方程:
ax+by=n
其中 xy 为自然数。如果方程有解,称 n 可以被 ab 表示。

C=abab。由 ab 互素,C 必然为奇数。则有结论:

对任意的整数 nnCn中有且仅有一个可以被表示。

即:可表示的数与不可表示的数在区间 [0,C] 对称(关于 C 的一半对称)。0 可被表示,C 不可被表示;负数不可被表示,大于 C 的数可被表示。

例如在 luoguP3951 就只是为了求 abab 的值