怎麽證明輾轉相除法求公約數的正確性?

已知m=qn+p,其中,m≥n,n>p.我們下面證明m和n的最大公約數等於n和p的最大公約數.使用(m,n)表示m和n的最大公約數；(n,p)表示n和p的最大公約數.用m|n表示m整除n.

對於任意m和n的公因數r,有r|m並且r|n;根據等式m=qn+p,所以r|p；所以r是n和p的公因數.

也就是說,m和n的公因數都是n和p的公因數.所以(m,n)是n和p的公因數.所以(m,n)|(n,p)

同樣,可以證明,任意n和p的公因數r,也是m和n的公因數.所以(n,p)|(m,n).

兩個大於零數,能夠互相整除,只能相等.所以(m,n)=(n,p).