定理
裴蜀定理(贝祖定理)是一个关于最大公约数的定理。...裴蜀定理说明了对任何整数a,b和它们的最大公约数d,关于未知数x和y的线性不定方程:若a,b是整数,且gcd(a,b)=d,那么对于任意的整数x,y,ax+by都一定是d的倍数,特别的,一定存在整数x,...证明
设d=gcd(a,b),则d∣a,d∣b。由整除性质可得,
图片
设s为ax+by的最小正值⋯⋯(1)
图片
同理可证s∣b
图片
证毕。...求不定方程的解
设d=gcd(a,b)
根据裴蜀定理可得到等式(贝祖等式):ax+by=d
图片
图片
即可发现x,y更新规律。