黄博士网: 在线数学手册计算器软件,电化学虚拟实验室,虚拟电化学工作站,电化学软件 首页 | 目录 | 世界 | 学科 | 理科 | 数学 | 物理 | 化学 | 计算机 | 医学 | 书单 | 索引 | 帮助

辗转相除法

每一个整数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.


参阅
  1. 数学 - 数学符号 - 数学索引
  2. 手册 - 数学手册 - 实用数学手册
  3. 初等数学 = 中学数学 = 初中数学 + 高中数学
  4. 高等数学 = 代数 + 几何 + 分析
  5. 公式 - 图表 - 动画 - 立体图
  6. 书单 = 数学 + 物理 + 化学 + 计算机 + 医学 + 英语 - QQ群 614057790 下截书
  7. 数学软件 - 数学手册计算器 = 数学 + 手册 + 计算器
  8. 例题:

首页 | 目录 | 论坛 | 联系 | 版权 | 书单 | 关于 | 索引 | 帮助 | English