辗转相除法是一种求两个数的最大公约数的方法。其原理是：对于两个正整数a,b（a≥b），将它们的模（余数）表示为r₁，r₂，r₃ …… rₙ，即：

a = q₁b + r₁

b = q₂r₁ + r₂

r₁ = q₃r₂ + r₃

……

rₙ₋ ₂ = qₙrₙ₋₁ + rₙ

其中，q₁、q₂、q₃ …… qₙ₋₁分别表示商，r₁、r₂、r₃ …… rₙ分别表示余数。

如果某一步的余数为0，则下一步的商就是a和b的最大公约数。通常，这个算法会一直持续到余数为0。