求以下兩整數的最大公約數（HCF），並將其表示為這兩個整數的線性組合
506 和 1155

已知：506 和 1155

要求：我們需要找到給定兩整數的最大公約數（HCF），並將其表示為一個線性組合。


解答

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

使用歐幾里得引理得到： 
  • $1155\ =\ 506\ \times\ 2\ +\ 143$   ...(i)

現在，考慮除數 506 和餘數 143，並應用除法引理得到
  • $506\ =\ 143\ \times\ 3\ +\ 77$   ...(ii)

現在，考慮除數 143 和餘數 77，並應用除法引理得到
  • $143\ =\ 77\ \times\ 1\ +\ 66$   ...(iii)

現在，考慮除數 77 和餘數 66，並應用除法引理得到
  • $77\ =\ 66\ \times\ 1\ +\ 11$   ...(iv)

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

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

因此，506 和 1155 的最大公約數（HCF）是此時此刻的除數，即11。


將 HCF 表示為 506 和 1155 的線性組合:

$11\ =\ 77\ –\ 66\ \times\ 1$   {來自公式 (iv)}

$11\ =\ 77\ –\ [143\ –\ 77\ \times\ 1]\ \times\ 1$   {來自公式 (iii)}

$11\ =\ 77\ –\ 143\ +\ 77\ \times\ 1$

$11\ =\ 77\ \times\ 2\ –\ 143$

$11\ =\ [506\ –\ 143\ \times\ 3]\ \times\ 2\ –\ 143$   {來自公式 (ii)}

$11\ =\ 506\ \times\ 2\ –\ 143\ \times\ 6\ –\ 143$

$11\ =\ 506\ \times\ 2\ –\ 143\ \times\ 7$

$11\ =\ 506\ \times\ 2\ –\ [1155\ –\ 506\ \times\ 2]\ \times\ 7$   {來自公式 (i)}

$11\ =\ 506\ \times\ 2\ –\ 1155\ \times\ 7\ +\ 506\ \times\ 14$

$\mathbf{11\ =\ 506\ \times\ 16\ –\ 1155\ \times\ 7}$


所以，506 和 1155 的最大公約數（HCF）是 11，它可以表示為 $11\ =\ 506\ \times\ 16\ –\ 1155\ \times\ 7$。

更新於： 2022年10月10日

1K+ 瀏覽量

開啟你的 職業生涯

透過完成課程獲得認證

立即開始
廣告