求以下一對整數的最大公約數 (HCF)，並將其表示為它們的線性組合
592 和 252

已知： 592 和 252

求解： 我們需要找到這對整數的最大公約數 (HCF)，並將其表示為線性組合。


解

使用歐幾里得除法演算法求 HCF:

使用歐幾里得引理得到：
  • $592\ =\ 252\ \times\ 2\ +\ 88$   ...(I)

現在，考慮除數 252 和餘數 88，並應用除法引理得到
  • $252\ =\ 88\ \times\ 2\ +\ 76$   ...(ii)

現在，考慮除數 88 和餘數 76，並應用除法引理得到

  • $88\ =\ 76\ \times\ 1\ +\ 12$   ...(iii)

現在，考慮除數 76 和餘數 12，並應用除法引理得到
  • $76\ =\ 12\ \times\ 6\ +\ 4$   ...(iv)

現在，考慮除數 12 和餘數 4，並應用除法引理得到
  • $12\ =\ 4\ \times\ 3\ +\ 0$   ...(v)

餘數變為零，我們無法繼續進行。

因此，592 和 252 的 HCF 是此時此刻的除數，即4。


將 HCF 表示為 592 和 252 的線性組合:

$4\ =\ 76\ –\ 12\ \times\ 6$   {來自等式 (iv)}

$4\ =\ 76\ –\ [88\ –\ 76\ \times\ 1]\ \times\ 6$   {來自等式 (iii)}

$4\ =\ 76\ –\ 88\ \times\ 6 +\ 76\ \times\ 6$

$4\ =\ 76\ \times\ 7\ –\ 88\ \times\ 6$

$4\ =\ [252\ –\ 88\ \times\ 2]\ \times\ 7\ –\ 88\ \times\ 6$   {來自等式 (ii)}

$4\ =\ 252\ \times\ 7\ –\ 88\ \times\ 14\ –\ 88\ \times\ 6$

$4\ =\ 252\ \times\ 7\ –\ 88\ \times\ 20$

$4\ =\ 252\ \times\ 7\ –\ [592\ –\ 252\ \times\ 2]\ \times\ 20$   {來自等式 (i)}

$4\ =\ 252\ \times\ 7\ –\ 592\ \times\ 20\ +\ 252\ \times\ 40$

$\mathbf{4\ =\ 252\ \times\ 47\ –\ 592\ \times\ 20}$


因此，592 和 252 的最大公約數 (HCF) 是 4，它可以表示為 $4\ =\ 252\ \times\ 47\ –\ 592\ \times\ 20$。

更新於： 2022年10月10日

瀏覽量 1000+

啟動您的職業生涯

完成課程獲得認證

開始學習
廣告