資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究求以下一對整數的最大公約數（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$。
2K+ 次瀏覽
