Question

AB互质,为什么不定方程AX+BY=1一定有整数解?

Answer 1

首先,这个是数论中的“费蜀(Bezout)定理”,很经典很实用的数论基础定理.

其次,证明的主要思想是欧几里德辗转相除法,列出一系列相同除数的除式使余数递减,最终达到1.其中AB互质的条件确定了余数1的可达到性和必达到性.之后开始倒推,把前面列出的式子按倒序把每个式子的余数用下一个式子代换,最终推出X和Y的解.(这个比较抽象,实在不方便描述,参考这个网址吧.)

最后,关于辗转相除法,如果不了解的话同样推荐你去这个地址看看.