证明一个命题：
if(a,b)=1
,
then ∀x∈N and x>ab−a−b
，都能表示成
x=pa+qb的形式(p,q∈N)
说真的感觉在哪里见过这个结论但是又想不起来了…… 我们来简单证明一下： 贝祖定理：
∵∃x,y∈Z,ax+by=1
∴ ∀n∈Z,∃p=nx,q=ny s.t. pa+qb=n
注意到，p可以用减掉一个b的代价使得q加上a。 注意到，p可以用加上一个b的代价使得q减去a。 则可设
p∈[0,b)
则有
n>ab−a−b
时，设
p∈[0,b)成立。
使用反证法：
若q<0
则有：
n=pa+qb<=a(b−1)+(−1)∗b
即
n<=ab−a−b.
矛盾。
∴n>ab−a−b时，原命题成立
转载请注明原文地址: https://ju.6miu.com/read-1300257.html
