求以下一对整数的最大公约数（HCF），并将其表示为这两个整数的线性组合
963 和 657

已知：963 和 657

要求：这里我们需要找到给定这对整数的最大公约数，并将其表示为线性组合。

解答

使用欧几里得除法算法求最大公约数:

使用欧几里得引理得到： 

  • $963\ =\ 657\ \times\ 1\ +\ 306$   ...(i)

现在，考虑除数 657 和余数 306，并应用除法引理得到

  • $657\ =\ 306\ \times\ 2\ +\ 45$   ...(ii)

现在，考虑除数 306 和余数 45，并应用除法引理得到

  • $306\ =\ 45\ \times\ 6\ +\ 36$   ...(iii)

现在，考虑除数 45 和余数 36，并应用除法引理得到

  • $45\ =\ 36\ \times\ 1\ +\ 9$   ...(iv)

现在，考虑除数 36 和余数 9，并应用除法引理得到

  • $36\ =\ 9\ \times\ 4\ +\ 0$   ...(v)

余数已变为零，我们无法继续进行。 

因此，963 和 657 的最大公约数是此时阶段的除数，即9。

将最大公约数表示为 963 和 657 的线性组合:

$9\ =\ 45\ –\ 36\ \times\ 1$   {来自等式 (iv)}

$9\ =\ 45\ –\ [306\ –\ 45\ \times\ 6]\ \times\ 1$   {来自等式 (iii)}

$9\ =\ 45\ –\ 306\ +\ 45\ \times\ 6$

$9\ =\ 45\ \times\ 7\ –\ 306$

$9\ =\ [657\ –\ 306\ \times\ 2]\ \times\ 7\ –\ 306$   {来自等式 (ii)}

$9\ =\ 657\ \times\ 7\ –\ 306\ \times\ 14\ –\ 306$

$9\ =\ 657\ \times\ 7\ –\ 306\ \times\ 15$

$9\ =\ 657\ \times\ 7\ –\ [963\ –\ 657\ \times\ 1]\ \times\ 15$   {来自等式 (i)}

$9\ =\ 657\ \times\ 7\ –\ 963\ \times\ 15\ +\ 657\ \times\ 15$

$\mathbf{9\ =\ 657\ \times\ 22\ –\ 963\ \times\ 15}$

因此，963 和 657 的最大公约数是 9，并且可以表示为 $9\ =\ 657\ \times\ 22\ –\ 963\ \times\ 15$。

更新于： 2022年10月10日

2K+ 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告