黄博士网: 在线数学手册计算器软件,电化学虚拟实验室,虚拟电化学工作站,电化学软件 关于 | 科学 | 数学 | 手册 | 软件 | 计算器 | 电化学 | 虚拟实验室 | 帮助 | 论坛 | 联系 | English

辗转相除法

每一个整数a可以唯一地通过正整数b表为 \[ a = bq + r,0 \le r < b \]

式中q称为ab除所得的不完全商,r称为ab除所得的余数.辗转相除法是指下列一串有限个等式: \[ \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.




参阅


Copyright 2000-2017 DrHuang.com