如何证明用除法求公约数的正确性？

已知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)。