每一个整数a可以唯一地通过正整数b表为 \[ a = bq + r,0 \le r < b \]
式中q称为a被b除所得的不完全商,r称为a被b除所得的余数.辗转相除法是指下列一串有限个等式: \[ \left\{ {\begin{array}{*{20}c} {a = ba_0 + r_1 ,} & {0 < r_1 < b} \\ {b = r_1 a_1 + r_2 ,} & {0 < r_2 < r_1 } \\ {r_1 = r_2 a_2 + r_3 ,} & {0 < r_3 < r_2 } \\ \cdots & \cdots \\ {r_{N - 2} = r_{N - 1} a_{N - 1} + r_N } & {0 < r_N < r_{N - 1} } \\ {r_{N - 1} = r_N a_N } & {} \\ \end{array}} \right. \]
例如:设a=525,b=231,根据(1)式可列出下面的算式 \[ \begin{array}{*{20}c} {525 = 231 \times 2 + 63} \\ {231 = 63 \times 3 + 42} \\ {63 = 42 \times 1 + 21} \\ {42 = 21 \times 2} \\ \end{array} \] 由此求得525和231的最大公约数21.