2つの整数の最大公約数（gcd）を見つける方法

コンテンツ

ステップ
2の方法1/2：除算アルゴリズム
方法2/2：素因数
チップ

2つの整数の最大公約数（GCD）は、これらの各数値を除算する最大の整数です。たとえば、20と16のgcdは4です（16と20の両方に大きな除数がありますが、一般的ではありません。たとえば、8は16の約数ですが、20の約数ではありません）。「ユークリッドの互除法」と呼ばれる、GCDを見つけるための簡単で体系的な方法があります。この記事では、2つの整数の最大公約数を見つける方法を説明します。

ステップ

2の方法1/2：除算アルゴリズム

1 マイナス記号は省略してください。
2 用語を学ぶ： 32を5で割るとき。
- 32-配当
- 5-除数
- 6-プライベート
- 2-残り
3 大きい方の数値を決定します。 割り切れ、小さい方が除数になります。
4 次のアルゴリズムを書き留めます。 （配当）=（除数） *（商）+（剰余）
5 被除数の代わりに大きな数を置き、除数の代わりに小さな数を置きます。
6 大きい数を小さい数で割った回数を求め、商の代わりに結果を書き込みます。
7 余りを見つけて、アルゴリズムの適切な位置に書き込みます。
8 アルゴリズムを再度記述しますが、（A）前の除数を新しい被除数として書き込み、（B）前の剰余を新しい除数として記述します。
9 余りが0になるまで、前の手順を繰り返します。
10 最後の除数は最大公約数（GCD）になります。
11 たとえば、108と30のGCDを見つけましょう。
12 最初の行の30と18の数字が2番目の行をどのように形成しているかに注目してください。 次に、18と12が3番目の行を形成し、12と6が4番目の行を形成します。 3、1、1、および2の倍数は使用されません。これらは、被除数が除数で割り切れる回数を表し、したがって各行に固有です。

方法2/2：素因数

1 マイナス記号は省略してください。
2 数の素因数を見つけます。 写真のように提示してください。
- たとえば、24と18の場合：
  - 24- 2 x 2 x 2 x 3
  - 18- 2 x 3 x 3
- たとえば、50と35の場合：
  - 50- 2 x 5 x 5
  - 35- 5 x 7
3 一般的な素因数を見つけます。
- たとえば、24と18の場合：
  - 24- 2 x 2 x 2 x 3
  - 18- 2 NS 3 x 3
- たとえば、50と35の場合：
  - 50-2 x 5 x 5
  - 35- 5 x 7
4 一般的な素因数を乗算します。
- 24と18の場合、乗算します 2 と 3 取得します 6..。 6は24と18の最大公約数です。
- 50と35を掛けるものは何もありません。 5 唯一の一般的な素因数であり、それはGCDです。
5 製！

チップ

これを書く1つの方法は次のとおりです。被除数> mod除算器> =剰余; mod b = 0の場合はGCD（a、b）= b、それ以外の場合はgcd（a、b）= gcd（b、mod b）。
例として、GCD（-77.91）を見つけましょう。まず、-77の代わりに77を使用します。GCD（-77.91）はGCD（77.91）に変換されます。 77は91未満なので、交換する必要がありますが、交換しない場合はアルゴリズムがどのように機能するかを検討してください。 77 mod 91を計算すると、77（77 = 91 x 0 + 77）が得られます。これはゼロではないので、状況（b、mod b）、つまりGCD（77.91）= GCD（91.77）を考慮します。 91 mod 77 = 14（14が残りです）。ゼロではないため、GCD（91.77）はGCD（77.14）になります。 77 mod 14 = 7。これはゼロではないため、GCD（77.14）はGCD（14.7）になります。 14 mod 7 = 0（14/7 = 2で余りがないため）。回答：GCD（-77.91）= 7。
説明した方法は、分数を単純化するのに非常に役立ちます。上記の例では、-77 / 91 = -11/13です。これは、7が-77と91の最大公約数であるためです。
aとbがゼロに等しい場合、ゼロ以外の数は除数であるため、この場合はGCDはありません（数学者は、0と0の最大公約数は0であると単純に信じています）。