使用欧几里得除法算法求最大公约数
(i) 135 和 225。
(ii) 196 和 38220。
(iii) 867 和 255。
已知:
(i) 135 和 225。
(ii) 196 和 38220。
(iii) 867 和 255。
求解:
我们需要求出给定数字的最大公约数。
解答
使用欧几里得除法算法求最大公约数
(i) 使用欧几里得引理得到:
- 225 = 135 × 1 + 90
现在,考虑除数 135 和余数 90,并应用除法引理得到
- 135 = 90 × 1 + 45
现在,考虑除数 90 和余数 45,并应用除法引理得到
- 90 = 45 × 2 + 0
余数已变为零,我们无法继续进行。
因此,225 和 135 的最大公约数是此时除数,即 45。
所以,135 和 225 的最大公约数是 45。
(ii) 使用欧几里得引理得到:
- 38220 = 196 × 195 + 0
余数已变为零,我们无法继续进行。
因此,38220 和 196 的最大公约数是此时除数,即 196。
所以,196 和 38220 的最大公约数是 196。
(iii) 使用欧几里得引理得到:
- 867 = 255 × 3 + 102
现在,考虑除数 255 和余数 102,并应用除法引理得到
- 255 = 102 × 2 + 51
现在,考虑除数 102 和余数 51,并应用除法引理得到
- 102 = 51 × 2 + 0
余数已变为零,我们无法继续进行。
因此,867 和 255 的最大公约数是此时除数,即 51。
所以,867 和 255 的最大公约数是 51。
广告