辗转相除法求最大公约数,辗转相减法求最大公约数原理

假设有两个正整数a和b，其中a>b。首先，用a除以b，得到商q和余数r1，即a=bq+r1。

然后，用b除以r1，得到商q1和余数r2，即b=r1q1+r2。如此反复进行，直到余数为零。此时，最后一个非零余数r即为a和b的最大公约数。