题目

数论证明整数a,b的最大公约数可以写成gcd(a,b)=sa+tb的形式,s,t为整数,不要辗转相除的逆推次生品,那个我也会,要一种更形式化的证明

提问时间：2021-03-31

答案

不妨设a,b的最大公约数就是c
则存在m,n都是整数,使得a=mc,b=nc,且（m,n）=1
方程c=sa+tb等价于方程1=ms+nt
因为（m,n）=1,
如果m不等于n,则必然有一个大于1,不妨设n>1
所以m,2m,3m,……,(n-1)m这n-1个数两两模n互质,它们都不整除n从而其中必然存在一个数 i,使得im除以n的余数是1
也就是存在整数t,使得im=nt+1
所以im+（-t）n=1
所以此时方程1=ms+nt存在整数解
如果m,n相等,那么m=n=1,则原来方程等价于s+t=1,显然有整数解
所以综上：整数a,b的最大公约数可以写成gcd(a,b)=sa+tb的形式,其中s,t为整数