证明自然数互质一法——介绍辗转相除法

证明两个自然数互质,通常是用反证法,本文介绍另一种重要方法——辗转相除法。下面通过几个例子说明。例1,求证:相邻两个自然数必定互质。证明:设相邻的两自然数为n、n+1, 用n除n+1得余数r1=1,再用1除n得余数r2=0,∴（n,n+1）=r1=1故相邻故相邻两个自然数必定互质。例2,求证:相邻两个自然数的平方和与这两个数的和互质(杭州大学编。