euclidean演算法

① 用「輾轉相除方法」計算兩個數 x,y 的最大公約

輾轉相除法, 又名歐幾里德演算法（Euclidean algorithm）乃求兩個正整數之最大公因子的演算法。它是已知最古老的演算法, 其可追溯至3000年前。它首次出現於歐幾里德的《幾何原本》（第VII卷，命題i和ii）中，而在中國則可以追溯至東漢出現的《九章算術》。它並不需要把二數作質因子分解。只要可計算余數都可用輾轉相除法來求最大公因子。這包括多項式、復整數及所有歐幾里德定義域（Euclidean domain）。
簡單的想法
設兩數為a、b(b＜a)，求它們最大公約數(a、b)的步驟如下：用b除a，得a＝bq......r 1(0≤r)。若r1=0，則(a，b)＝b；若r1≠0，則再用r1除b，得b＝r1q......r2 (0≤r2).若r2＝0，則(a，b)＝r1，若r2≠0，則繼續用r2除r1,……如此下去，直到能整除為止。其最後一個非零餘數即為(a，b)。

本題中，要求x,y的最大公約數，不妨設x>y，是將上面的a,b換成x,y就得到計算的過程。

供參考！江蘇吳雲超祝你學習進步

② 迭代演算法是什麼

迭代法也稱輾轉法，是一種不斷用變數的舊值遞推新值的過程，跟迭代法相對應的是直接法，即一次性解決問題。迭代法又分為精確迭代和近似迭代。

「二分法」和「牛頓迭代法」屬於近似迭代法。迭代演算法是用計算機解決問題的一種基本方法。它利用計算機運算速度快、適合做重復性操作的特點，讓計算機對一組指令（或一定步驟）進行重復執行，在每次執行這組指令（或這些步驟）時，都從變數的原值推出它的一個新值。

迭代是數值分析中通過從一個初始估計出發尋找一系列近似解來解決問題（一般是解方程或者方程組）的過程，為實現這一過程所使用的方法統稱為迭代法（Iterative Method）。

輾轉相除法， 又名歐幾里德演算法（Euclidean algorithm），是求最大公約數的一種方法。它的具體做法是：用較大數除以較小數，再用出現的余數（第一餘數）去除除數，再用出現的余數（第二餘數）去除第一餘數，如此反復，直到最後余數是0為止。

如果是求兩個數的最大公約數，那麼最後的除數就是這兩個數的最大公約數。另一種求兩數的最大公約數的方法是更相減損法。

③ 輾轉相除法的原理

輾轉相除法， 又名歐幾里德演算法（Euclidean algorithm）乃求兩個正整數之最大公因子的演算法。它是已知最古老的演算法， 其可追溯至公元前300年前。輾轉相除法的原理：
設兩數為a、b(a>b)，用gcd(a,b)表示a，b的最大公約數，r=a (mod b) 為a除以b的余數，k為a除以b的商，即a÷b=k.......r。輾轉相除法即是要證明gcd(a,b)=gcd(b,r)。
第一步：令c=gcd(a,b)，則設a=mc，b=nc
第二步：根據前提可知r =a-kb=mc-knc=(m-kn)c
第三步：根據第二步結果可知c也是r的因數
第四步：可以斷定m-kn與n互質(假設m-kn=xd，n=yd (d>1)，則m=kn+xd=kyd+xd=(ky+x)d，則a=mc=(ky+x)cd，b=nc=ycd，則a與b的一個公約數cd>c，故c非a與b的最大公約數，與前面結論矛盾)，因此c也是b與r的最大公約數。
從而可知gcd(b,r)=c，繼而gcd(a,b)=gcd(b,r)。
證畢。
以上步驟的操作是建立在剛開始時r≠0的基礎之上的。即m與n亦互質。

④ 輾轉相除法為什麼能求出的就是最大公因數

輾轉相除法,
又名歐幾里得演算法（Euclidean
algorithm）乃求兩個正整數之最大公因數的演算法。
輾轉相除法是利用以下性質來確定兩個正整數
a
和
b
的最大公因數的：
若
r
是
a
÷
b
的余數,
則
gcd(a,b)
=
gcd(b,r)
a
和其倍數之最大公因數為
a。
另一種寫法是：
a
÷
b，令r為所得余數（0≤r＜b）
若
r
=
0，演算法結束；b
即為答案。
互換：置
a←b，b←r，並返回第一步。

⑤ 輾轉相除法怎麼做二元一次方程組

輾轉相除法, 又名歐幾里德演算法（Euclidean algorithm）乃求兩個正整數之最大公因子的演算法。

輾轉相除法可以求出不定方程的一組整數解。
設不定方程為a x+b y=c，其中a,b,c為整數且lcm(a,b)|c
a,b輾轉相除的算式為
b=q(1) a+r(2)
a=q(2) r(2)+r(3)
r(2)=q(3) r(3)+r(4)
...
r(n-2)=q(n-1)r(n-1)+r(n)
r(n-1)=q(n)r(n)
其中r(n)為lcm(a,b)，不妨令b=r(0)，a=r(1)，r(n+1)=0
第i個算式為
r(i-1)=q(i)r(i)+r(i+1)
所以r(i+1)=r(i-1)-q(i)(ri) (*)
用公式(*)可以得到r(n)=lcm(a,b)關於a,b的線性組合sa+tb=lcm(a,b)
所以不定方程a x+b y=c的一組特解為
x=sc/lcm(a,b) y=tc/lcm(a,b)
註：q(i)，r(i)，括弧中的是下標，lcm是求最大公約數

⑥ 若給定兩個正整數m和n，試寫出求他們的最大公因子（既能夠同時整除m和n的最大整數）的演算法——歐幾里德算

輾轉相除法
開放分類： 數學、最大公約數

輾轉相除法, 又名歐幾里德演算法（Euclidean algorithm）乃求兩個正整數之最大公因子的演算法。它是已知最古老的演算法, 其可追溯至前300年。它首次出現於歐幾里德的《幾何原本》（第VII卷，命題i和ii）中，而在中國則可以追溯至東漢出現的《九章算術》。它並不需要把二數作質因子分解。

證明：
設兩數為a、b(b＜a)，求它們最大公約數(a、b)的步驟如下：用b除a，得a＝bq�1＋r�1（0≤r�1＜b）。若r�1=0，則(a，b)＝b；若r�1≠0，則再用r�1除b，得b＝r�1q�2＋r�2（0≤r�2＜r�1）。若r�2＝0，則(a，b)＝r�1，若r�2≠0，則繼續用r�2除r�1，……如此下去，直到能整除為止。其最後一個非零餘數即為(a，b)。

[編輯] 演算法

輾轉相除法是利用以下性質來確定兩個正整數 a 和 b 的最大公因子的：

1. 若 r 是 a ÷ b 的余數, 則

gcd(a,b) = gcd(b,r)

2. a 和其倍數之最大公因子為 a。

另一種寫法是：

1. a ÷ b，令r為所得余數（0≤r＜b）

若 r = 0，演算法結束；b 即為答案。

2. 互換：置 a←b，b←r，並返回第一步。

[編輯] 虛擬碼

這個演算法可以用遞歸寫成如下:

function gcd(a, b) {
if a mod b<>0
return gcd(b, a mod b);
else
return a;
}

或純使用循環:

function gcd(a, b) {
define r as integer;
while b ≠ 0 {
r := a mod b;
a := b;
b := r;
}
return a;
}

其中「a mod b」是指取 a ÷ b 的余數。

例如，123456 和 7890 的最大公因子是 6, 這可由下列步驟看出：
a b a mod b
123456 7890 5106
7890 5106 2784
5106 2784 2322
2784 2322 462
2322 462 12
462 12 6
12 6 0

只要可計算余數都可用輾轉相除法來求最大公因子。這包括多項式、復整數及所有歐幾里德定義域（Euclidean domain）。

輾轉相除法的運算速度為 O(n2)，其中 n 為輸入數值的位數。

⑦ 歐幾里德演算法的簡單解釋

[編輯本段]歐幾里得演算法的概述 歐幾里德演算法又稱輾轉相除法，用於計算兩個整數a，b的最大公約數。其計算原理依賴於下面的定理： 定理：gcd(a,b) = gcd(b,a mod b) 證明：a可以表示成a = kb + r，則r = a mod b 假設d是a,b的一個公約數，則有 d|a, d|b，而r = a - kb，因此d|r 因此d是(b,a mod b)的公約數 假設d 是(b,a mod b)的公約數，則 d | b ， d |r ，但是a = kb +r 因此d也是(a,b)的公約數 因此(a,b)和(b,a mod b)的公約數是一樣的，其最大公約數也必然相等，得證 [編輯本段]歐幾里得演算法原理 Lemma 1.3.1 若 a, b 且 a = bh + r, 其中 h, r , 則 gcd(a, b) = gcd(b, r). 證明. 假設 d1 = gcd(a, b) 且 d2 = gcd(b, r). 我們證明 d1| d2 且 d2| d1, 因而可利用 Proposition 1.1.3(2) 以及 d1, d2 皆為正數得證 d1 = d2. 因 d1| a 且 d1| b 利用 Corollary 1.1.2 我們知 d1| a - bh = r. 因為 d1| b, d1| r 且 d2 = gcd(b, r) 故由 Proposition 1.2.5 知 d1| d2. 另一方面, 因為 d2| b 且 d2| r 故 d2| bh + r = a. 因此可得 d2| d1. Lemma 1.3.1 告訴我們當 a > b > 0 時, 要求 a, b 的最大公因數我們可以先將 a 除以 b 所得餘數若為 r, 則 a, b 的最大公因數等於 b 和 r 的最大公因數. 因為 0r < b < a, 所以當然把計算簡化了. 接著我們就來看看輾轉相除法. 由於 gcd(a, b) = gcd(- a, b) 所以我們只要考慮 a, b 都是正整數的情況. Theorem 1.3.2 (The Euclidean Algorithm) 假設 a, b 且 a > b. 由除法原理我們知存在 h0, r0 使得 a = bh0 + r0, 其中 0r0 < b. 若 r0 > 0, 則存在 h1, r1 使得 b = r0h1 + r1, 其中 0r1 < r0. 若 r1 > 0, 則存在 h2, r2 使得 r0 = r1h2 + r2, 其中 0r2 < r1. 如此繼續下去直到 rn = 0 為止. 若 n = 0 (即 r0 = 0), 則 gcd(a, b) = b. 若 n1, 則 gcd(a, b) = rn - 1. 證明. 首先注意若 r0 0, 由於 r0 > r1 > r2 > ... 是嚴格遞減的, 因為 r0 和 0 之間最多僅能插入 r0 - 1 個正整數, 所以我們知道一定會有 nr0 使得 rn = 0. 若 r0 = 0, 即 a = bh0, 故知 b 為 a 之因數, 得證 b 為 a, b 的最大公因數. 若 r0 > 0, 則由 Lemma 1.3.1 知 gcd(a, b) = gcd(b, r0) = gcd(r0, r1) = ... = gcd(rn - 1, rn) = gcd(rn - 1, 0) = rn - 1. 現在我們來看用輾轉相除法求最大公因數的例子 Example 1.3.3 我們求 a = 481 和 b = 221 的最大公因數. 首先由除法原理得 481 = 2 . 221 + 39, 知 r0 = 39. 因此再考慮 b = 221 除以 r0 = 39 得 221 = 5 . 39 + 26, 知 r1 = 26. 再以 r0 = 39 除以 r1 = 26 得 39 = 1 . 26 + 13, 知 r2 = 13. 最後因為 r2 = 13 整除 r1 = 26 知 r3 = 0, 故由 Theorem 1.3.2 知 gcd(481, 221) = r2 = 13. 在利用輾轉相除法求最大公因數時, 大家不必真的求到 rn = 0. 例如在上例中可看出 r0 = 39 和 r1 = 26 的最大公因數是 13, 利用 Lemma 1.3.1 馬上得知 gcd(a, b) = 13. 在上一節 Corollary 1.2.5 告訴我們若 gcd(a, b) = d, 則存在 m, n 使得 d = ma + nb. 當時我們沒有提到如何找到此 m, n. 現在我們利用輾轉相除法來介紹一個找到 m, n 的方法. 我們沿用 Theorem 1.3.2 的符號. 首先看 r0 = 0 的情形, 此時 d = gcd(a, b) = b 所以若令 m = 0, n = 1, 則我們有 d = b = ma + nb. 當 r0 0 但 r1 = 0 時, 我們知 d = gcd(a, b) = r0. 故利用 a = bh0 + r0 知, 若令 m = 1, n = - h0, 則 d = r0 = ma + nb. 同理若 r0 0, r1 0 但 r2 = 0, 則知 d = gcd(a, b) = r1. 故利用 a = bh0 + r0 以及 b = r0h1 + r1 知 r1 = b - r0h1 = b - (a - bh0)h1 = - h1a + (1 + h0h1)b. 因此若令 m = - h1 且 n = 1 + h0h1, 則 d = r1 = ma + nb. 依照此法, 當 r0, r1 和 r2 皆不為 0 時, 由於 d = gcd(a, b) = rn - 1 故由 rn - 3 = rn - 2hn - 1 + rn - 1 知 d = rn - 3 - hn - 1rn - 2. 利用前面推導方式我們知存在 m1, m2, n1, n2 使得 rn - 3 = m1a + n1b 且 rn - 2 = m2a + n2b 故代入得 d = (m1a + n1b) - hn - 1(m2a + n2b) = (m1 - hn - 1m2)a + (n1 - hn - 1n2)b. 因此若令 m = m1 - hn - 1m2 且 n = n1 - hn - 1n2, 則 d = ma + nb. 上面的說明看似好像當 r0 0 時對每一個 i {0, 1,..., n - 2} 要先將 ri 寫成 ri = mia + nib, 最後才可將 d = rn - 1 寫成 ma + nb 的形式. 其實這只是論證時的方便, 在實際操作時我們其實是將每個 ri 寫成 mi'ri - 2 + ni'ri - 1 的形式慢慢逆推回 d = ma + nb. 請看以下的例子. Example 1.3.4 我們試著利用 Example 1.3.3 所得結果找到 m, n 使得 13 = gcd(481, 221) = 481m + 221n. 首先我們有 13 = r2 = 39 - 26 = r0 - r1. 而 r1 = 221 - 5 . 39 = b - 5r0, 故得 13 = r0 - (b - 5r0) = 6r0 - b. 再由 r0 = 481 - 2 . 221 = a - 2b, 得知 13 = 6(a - 2b) - b = 6a - 13b. 故得 m = 6 且 n = - 13 會滿足 13 = 481m + 221n. 要注意這里找到的 m, n 並不會是唯一滿足 d = ma + nb 的一組解. 雖然上面的推演過程好像會只有一組解, 不過只能說是用上面的方法會得到一組解, 並不能擔保可找到所有的解. 比方說若令 m' = m + b, n' = n - a, 則 m'a + n'b = (m + b)a + (n - a)b = ma + nb = d. 所以 m', n' 也會是另一組解. 所以以後當要探討唯一性時, 若沒有充分的理由千萬不能說由前面的推導過程看出是唯一的就斷言是唯一. 一般的作法是假設你有兩組解, 再利用這兩組解所共同滿足的式子找到兩者之間的關系. 我們看看以下的作法. Proposition 1.3.5 假設 a, b 且 d = gcd(a, b). 若 x = m0, y = n0 是 d = ax + by 的一組整數解, 則對任意 t , x = m0 + bt/d, y = n0 - at/d 皆為 d = ax + by 的一組整數解, 而且 d = ax + by 的所有整數解必為 x = m0 + bt/d, y = n0 - at/d 其中 t 這樣的形式. 證明. 假設 x = m, y = n 是 d = ax + by 的一組解. 由於已假設 x = m0, y = n0 也是一組解, 故得 am + bn = am0 + bn0. 也就是說 a(m - m0) = b(n0 - n). 由於 d = gcd(a, b), 我們可以假設 a = a'd, b = b'd 其中 a', b' 且 gcd(a', b') = 1 (參見 Corollary 1.2.3). 因此得 a'(m - m0) = b'(n0 - n). 利用 b'| a'(m - m0), gcd(a', b') = 1 以及 Proposition 1.2.7(1) 得 b'| m - m0. 也就是說存在 t 使得 m - m0 = b't. 故知 m = m0 + b't = m0 + bt/d. 將 m = m0 + bt/d 代回 am + bn = am0 + bn0 可得 n = n0 - at/d, 因此得證 d = ax + by 的整數解都是 x = m0 + bt/d, y = n0 - at/d 其中 t 這樣的形式. 最後我們僅要確認對任意 t , x = m0 + bt/d, y = n0 - at/d 皆為 d = ax + by 的一組整數解. 然而將 x = m0 + bt/d, y = n0 - at/d 代入 ax + by 得 a(m0 + bt/d )+ b(n0 - at/d )= am0 + bn0 = d, 故得證本定理. 利用 Proposition 1.3.5 我們就可利用 Example 1.3.4 找到 13 = 481x + 221y 的一組整數解 x = 6, y = - 13 得到 x = 6 + 17t, y = - 13 - 37t 其中 t 是 13 = 481x + 221y 所有的整數解

希望採納

⑧ 展轉相除法

輾轉相除法, 又名「歐幾里德演算法」（Euclidean algorithm）乃求兩數之最大公因數演算法。它是已知最古老的演算法, 其可追溯至前300年。它首次出現於歐幾里德的《幾何原本》中，而在中國則可以追溯至東漢出現的《九章算術》。它並不需要把二數作質因數分解。輾轉相除法是利用以下性質來確定最大公因數的：

若 r 是 b ÷ a 的余數, 則
<math>\gcd(a, b) = \gcd(b, r)</math></div>
a 和其倍數之最大公因數為 a。
於是, 這個演算法便可以用遞歸寫成如下:

function gcd(a, b) {
if (a 不整除 b)
return gcd(b, a mod b);
else
return a;
}
或純使用循環:

function gcd(a, b) {
define r as integer;
while b ≠ 0 {
r := a mod b;
a := b;
b := r;
}
return a;
}
其中「a mod b」是指取 a ÷ b 的余數。

例如，123456 和 7890 的最大公因數是 6, 這可由下列步驟看出：

a b a mod b
123456 7890 5106
7890 5106 2784
5106 2784 2322
2784 2322 462
2322 462 12
462 12 6
12 6 0

只要可計算餘數都可用輾轉相除法來求最大公因數。這包括多項式、復整數及所有歐幾里德定義域（Euclidean domain）。

輾轉相除法的運算速度為 <math>O(n^2)</math>，其中 n 為輸入數值的位數。bg:Алгоритъм на Евклид cs:Euklidův algoritmus de:Euklidischer Algorithmus en:Euclidean algorithm es:Algoritmo de Euclides fr:Algorithme d'Euclide hu:Euklidészi algoritmus ja:ユークリッドの互除法 nl:Algoritme van Euclides pl:Algorytm Euklidesa pt:Algoritmo de Euclides ru:Алгоритм Евклида

取自"http://wiki.keyin.cn/index.php/%E8%BE%97%E8%BD%AC%E7%9B%B8%E9%99%A4%E6%B3%95"

⑨ 高中數學的輾轉相除法問題

輾轉相除法 網路名片 歐幾里德輾轉相除法, 又名歐幾里德演算法（Euclidean algorithm）乃求兩個正整數之最大公因子的演算法。它是已知最古老的演算法, 其可追溯至3000年前。簡單的想法 設兩數為a、b(b＜a)，求它們最大公約數(a、b)的步驟如下：用b除a，得a＝bq......r 1(0≤r)。若r1=0，則(a，b)＝b；若r1≠0，則再用r1除b，得b＝r1q......r2 (0≤r2).若r2＝0，則(a，b)＝r1，若r2≠0，則繼續用r2除r1,……如此下去，直到能整除為止。其最後一個非零餘數即為(a，b)。 原理及其詳細證明 在介紹這個方法之前，先說明整除性的一些特點（下文的所有數都是正整數，不再重覆），我們可以這樣給出整除性的定義： 對於二個自然數a和b，若存在正整數q，使a=bq，則a能被b整除，b為a的因子，a為b的倍數。 如果a能被c整除，並且b也能被c整除，則c為a、b的公因數（公有因數）。 由此我們可以得出以下推論： 推論1、如果a能被b整除（a=qb），若k為正整數，則ka也能被b整除（ka=kqb） 推論2、如果a能被c整除（a=hc），b也能被c整除（b=tc），則(a±b)也能被c整除 因為：將二式相加：a+b=hc+tc=(h+t)c 同理二式相減：a－b=hc－tc=(h－t)c 所以：(a±b)也能被c整除 推論3、如果a能被b整除（a=qb），b也能被a整除（b=ta），則a=b 因為：a=qbb=taa=qta qt=1 因為q、t均為正整數，所以t=q=1 所以：a=b 輾轉相除法是用來計算兩個數的最大公因數，在數值很大時尤其有用，而且應用在電腦程式上也十分簡單。其理論如下: 如果 q 和 r 是 m 除以 n 的商及余數，即 m=nq+r，則 gcd(m,n)=gcd(n,r)。 證明是這樣的: 設 a=gcd(m,n)，b=gcd(n,r) 證明： ∵a為m,n的最大公約數， ∴m能被a整除，且n也能被a整除， ∴由推論1得：qn也能被a整除， ∴ 由推論2得：m-qn也能被a整除， 又 ∵m-qn=r， ∴r也能被a整除，即a為n和r的公約數（注意：還不是最大公約數） ∵b為n和r的最大公約數，a為n和r的公約數 ∴a≤b， 同理 ∵b為n, r的最大公約數， ∴n能被b整除，且r也能被b整除， ∴由推論1得：qn也能被b整除， ∴由推論2得：qn+r也能被b整除， 又∵m=qn+r， ∴m也能被b整除，即b為m和n的公約數，（注意：還不是最大公約數） ∵a為m,n的最大公約數，b為m和n的公約數， ∴b≤a， 由以上可知： a≤b與b≤a同時成立， 故可得 a=b， 證畢。 例如計算 gcd(546, 429) gcd(546, 429) 546=1*429+117 =gcd(429, 117) 429=3*117+78 =gcd(117, 78) 117=1*78+39 =gcd(78, 39) 78=2*39 =39 [編輯本段]計算機演算法自然語言描述 輾轉相除法是利用以下性質來確定兩個正整數 a 和 b 的最大公因子的： 1. 若 r 是 a ÷ b 的余數, 則 gcd(a,b) = gcd(b,r) 2. a 和其倍數之最大公因子為 a。 另一種寫法是： 1. a ÷ b，令r為所得余數（0≤r＜b） 若 r = 0，演算法結束；b 即為答案。 2. 互換：置 a←b，b←r，並返回第一步。 流程圖 流程圖(當型) 偽代碼 這個演算法可以用遞歸寫成如下: function gcd(a, b) { if b<>0 return gcd(b, a mod b); else return a; } c語言實現 /* 輾轉相除法（遞歸）*/ #include <stdio.h> int Gcd(int a,int b); int main(void ) { int m,n,t; printf("Enter the two figures:"); scanf("%d %d",&m,&n); printf("Gcd:%d\n",Gcd(m,n)); return 0; } int Gcd(int m,int n)//最大公約數 { int t; if(m<n) {t = n,n = m,m = t;} if(n == 0) return m; else return Gcd(n,m%n); } pascal實現 function gcd(a,b:integer):integer; begin if b=0 then gcd:=a else gcd:=gcd (b,a mod b); end ; 數據舉例 其中「a mod b」是指取 a ÷ b 的余數。 例如，123456 和 7890 的最大公因子是 6, 這可由下列步驟看出： a b a mod b 123456 7890 5106 7890 5106 2784 5106 2784 2322 2784 2322 462 2322 462 12 462 12 6 12 6 0 時間復雜度 輾轉相除法的運算速度為 O(n2)，其中 n 為輸入數值的位數。 輾轉相除法求不定方程的特解 輾轉相除法可以求出不定方程的一組整數解。 設不定方程為a x+b y=c，其中a,b,c為整數且lcm(a,b)|c a,b輾轉相除的算式為 b=q(1) a+r(2) a=q(2) r(2)+r(3) r(2)=q(3) r(3)+r(4) ... r(n-2)=q(n-1)r(n-1)+r(n) r(n-1)=q(n)r(n) 其中r(n)為lcm(a,b)，不妨令b=r(0)，a=r(1)，r(n+1)=0 第i個算式為 r(i-1)=q(i)r(i)+r(i+1) 所以r(i+1)=r(i-1)-q(i)(ri) (*) 用公式(*)可以得到r(n)=lcm(a,b)關於a,b的線性組合sa+tb=lcm(a,b) 所以不定方程a x+b y=c的一組特解為 x=sc/lcm(a,b) y=tc/lcm(a,b) 例如： 不定方程為326x+78y=4 求(163,39)的算式為 326=4*78+14 14=326-4*78 78=5*14+8 8=78-5*14 14=1*8+6 6=14-1*8 8=1*6+2 2=8-1*6 6=3*2 所以 2 =8-6=8-(14-8) =2*8-14=2*(78-5*14)-14 =2*78-11*14=2*78-11*(326-4*78) =46*78-11*326 即2=(-11)*326+46*78 所以4=(-22)*326+72*78 所以x=-22,y=72是不定方程326x+78y=4的一組特解 註：q(i)，r(i)，括弧中的是下標，lcm是求最大公約數按此方法 6497 3869 2628 3869 2628 1241 2628 1241 1387 1387 1241 146 1241 146 1095 1241 1095 146 1095 146 949 949 146 803 803 146 657 657 146 511 511 146 365~~~~~~~~~~~~146 73 73最大公約數為73 3869=73*53 6497=89*73最小公倍數 73*53*89=344341

⑩ 輾轉相除法求最大公約數c語言代碼

輾轉相除法是在在維基網路中的意思是：
在數學中，輾轉相除法，又稱歐幾里得演算法（英語：Euclidean algorithm），是求最大公約數的演算法。輾轉相除法首次出現於歐幾里得的《幾何原本》（第VII卷，命題i和ii）中，而在中國則可以追溯至東漢出現的《九章算術》。

兩個整數的最大公約數是能夠同時整除它們的最大的正整數。輾轉相除法基於如下原理：兩個整數的最大公約數等於其中較小的數和兩數的差的最大公約數。例如，252和105的最大公約數是21（ {\displaystyle 252=21\times 12;105=21\times 5} {\displaystyle 252=21\times 12;105=21\times 5}）；因為 252 − 105 = 21 × (12 − 5) = 147 ，所以147和105的最大公約數也是21。在這個過程中，較大的數縮小了，所以繼續進行同樣的計算可以不斷縮小這兩個數直至其中一個變成零。這時，所剩下的還沒有變成零的數就是兩數的最大公約數。由輾轉相除法也可以推出，兩數的最大公約數可以用兩數的整數倍相加來表示，如 21 = 5 × 105 + (−2) × 252 。這個重要的結論叫做裴蜀定理。
在現代密碼學方面，它是RSA演算法（一種在電子商務中廣泛使用的公鑰加密演算法）的重要部分

簡單的來說輾轉相除法的原理就是：

先比較兩個數使第一個數為最大數a，第二個數為最小數b
使最大數%最小數得到余數a%b=temp
後將余數賦值給最小數a=temp再去除最大數b即b%a
一直往復直到余數不為0