最大公約数 (GCD) の概念の定義に進む前に、一般的に公約数とは何かを理解する必要があります。
整数は複数の約数を持つことができることが知られています。 私たちは、複数の整数によるそれらへの同時アクセスに興味があります。 複数の整数の公約数は、指定された系列の各数値の約数として機能する数値であると考えられます。
たとえば、数字 8 と 12 には、1 と 4 の公約数があります。これは、次の数式を書くことで簡単に検証できます。8 = 4 ⋅ 2; 12 = 3 ⋅ 4。
各数値には最初に少なくとも 2 つの公約数があることに注意してください。どの数値も、余りを持たずにそれ自体で割り切れ、1 でも割り切れます。
最大公約数の決定
2 つの自然数の最大公約数 (GCD) は、2 つの数を割ることができる自然数の中で最大のものです。 2 つの自然数の最大公約数の値が 1 の場合、これらの数は互いに素であると呼びます。
2 つの数値 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 です。
同様に、3 つ以上の整数の 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.
証明された最大約数プロパティを使用して、2 つの数値の一方が他方で割り切れる場合の 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
式 gcd(ma, mb) = m ⋅ gcd(a, b) は、m が任意の自然数であれば true です。
プロパティ 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
任意の 2 つの数値には少なくとも 1 つの公約数があります。これが数値 1 です。
普通の分数を扱うには、GCD 概念の理論的基礎に関する知識と、その定義に関する実践的なスキルが必要です。 さらに、GCD は別の数学単位である最小公倍数と密接に関連しています。 どちらの定義も通常、標準的な学校カリキュラムの一部として学習されます。
