最大公因數計算機
在繼續定義最大公約數 (GCD) 的概念之前,有必要了解一般公約數是什麼。
眾所周知,一個整數可以有多個約數。 我們感興趣的是通過幾個整數同時訪問它們。 我們將幾個整數的公約數視為可以作為指定係列中每個數字的約數的數字。
例如,數字 8 和 12 有以下公約數:1 和 4。這可以很容易地通過編寫數學表達式來驗證:8 = 4 ⋅ 2; 12 = 3 ⋅ 4.
需要注意的是,每個數最初至少有兩個公約數:任何數都可以被其本身無餘數整除,也可以被1整除。
確定最大公約數
兩個自然數的最大公約數 (GCD) 是我們可以除以兩個數字的最大自然數。 如果兩個自然數的最大公約數的值為 1,則稱這兩個自然數互質。
對於兩個數 a 和 b,最大公約數是 a 和 b 可以除以無餘數的數。 這個表達式寫成:gcd(a, b) = c。
GCD的另一種寫法:(a, b) = c。 但是,在大多數情況下,會使用第一個選項。
因此,例如,數字 4 和 16 的最大公約數等於 4。讓我們寫成:gcd (4, 16) = 4。
讓我們描述一下我們是如何得出這個結果的:
- 我們寫出了數字 4 的所有除數。我們得到:4、2、1。
- 接下來,我們繪製了 16 的所有除數。我們得到:16、8、4、2、1。
- 我們選擇了 4 和 16 的共同除數。我們得到:4、2、1。
- 從生成的公約數中,選擇最大的公約數。 這是 4。
- 我們得到答案:對於數字 4 和 16,GCD 為 4。
同樣,您可以找到三個或更多整數的 GCD。 在這種情況下,它將是最大的整數,您可以將建議的系列中的所有數字除以該整數。
因此,例如,整數 6、12、18、42 的最大約數將是數字 6,即 gcd (6, 12, 18, 42) = 6。答案是使用算法得出的與上面描述的類似 - 對於系列中的數字,所有除數按順序寫出,然後選擇其中最大的。
GCD 屬性
最大公約數具有許多與除數大於零的正整數的 GCD 相關的屬性。
屬性 1
從數字換位來看,GCD的最終值是不會改變的。 你可以這樣寫這個語句:
- gcd(a, b) = gcd(b, a)。
屬性 2
如果 a 可以被 b 整除,則 a 和 b 的公約數集合與 b 的公約數集合相同。 寫成這樣:
- gcd(a, b) = b.
已證明的最大除數屬性可用於找到兩個數字中的一個可以被另一個整除的 gcd。 在這種情況下,GCD 等於這些數字中的一個,另一個數字可以被它整除。
例如:
- gcd(12, 4) = 4。
類似的:
- gcd(10, 1) = 1。
屬性 3
如果 a = bq + c,其中 a、b、c 和 q 是整數,則 a 和 b 的公約數集合與 b 和 c 的公約數集合相同。
等式 gcd (a, b) = gcd (b, c) 成立。
屬性 4
如果 m 是任何自然數,則表達式 gcd(ma, mb) = m ⋅ gcd(a, b) 為真。
屬性 5
假設 p 是 a 和 b 的公約數。
然後:
- gcd(a / p, b / p) = gcd(a, b) / p。
如果 p = gcd(a, b),我們得到:
- gcd (a / gcd (a, b), b / gcd (a, b)) = 1,
因此,數字 a / gcd (a, b) 和 b / gcd (a, b) 互質。
屬性 6
任何兩個數字至少有一個公約數 - 這就是數字 1。
要使用普通分數,必須了解 GCD 概念的理論基礎及其定義的實踐技能。 此外,GCD與另一個數學單位——最小公約數密切相關。 這兩個定義通常作為標準學校課程的一部分進行研究。