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

2 つの数の最大公約数は、最大公約数または最高公約数とも呼ばれ、2 つの整数を割り切れる最大の数です。たとえば、20 と 16 の最大公約数は 4 です (20 と 16 はどちらもより大きな因数を持ちますが、共通因数ではありません。たとえば、8 は 16 の因数ですが、20 の因数ではありません)。学校の先生の多くは、最大公約数を見つけるために「推測して検証する」方法を教えていますが、実際には、最大公約数を正確に見つけるより簡単で体系的な方法があります。この方法は「ユークリッドの互除法」と呼ばれます。 2つの数字が「a」と「b」であるとする

方法1方法1/2:

除数アルゴリズムの使用

1マイナス記号を削除します。
{"smallUrl":"https:\/\/www.wikihow.com\/images_en\/thumb\/7\/75\/Find-the-Greatest-Common-Divisor-of-Two-Integers-Step-2-Version-2.jpg\/v4-460px-Find-the-Greatest-Common-Divisor-of-Two-Integers-Step-2-Version-2.jpg","bigUrl":"https:\/\/www.wikihow.com\/i mages\/thumb\/7\/75\/Find-the-Greatest-Common-Divisor-of-Two-Integers-Step-2-Version-2.jpg\/v4-728px-Find-the-Greatest-Common-Divisor-of-Two-Integers-Step-2-Version-2.jpg","smallWidth":460,"smallHeight":345,"bigWidth":728,"bigHeight":546,"licensing":"<div class=\"mw-parser-output\"><\/div>"} 2関連する語彙を理解する（32 ÷ 5）：
- - 32は被除数です
  - 5は除数である
  - 6はビジネス
  - 2は剰余（剰余）です
3 2 つの数値のうち大きい方を被除数として求めます。小さい方の数が除数として使用されます。
4式を書きます: (被除数) = (除数) * (商) + (余り)
5大きい数が被除数、小さい数が除数です。
6 は商を取得します。
7余りを取得して式を記述します。
8式をもう一度書きますが、ここでは被除数の代わりに上記の除数を使用し、上記の余りを除数として使用します。
9余りがゼロになるまで手順を繰り返します。
10最後の除数は最大公約数です。
11この例では、108 と 30 の最大公約数を見つけます。
12最初の行の 30 と 18 が 2 行目にあり、除数が被除数になり、余りが除数になる、というように続くことに注意してください。各路線の業務は他の路線の業務と異なり、この路線にのみ属し、他の路線には役に立たない。広告する

方法2方法2/2:

素因数の使用

1マイナス記号を削除します。
{"smallUrl":"https:\/\/www.wikihow.com\/images_en\/thumb\/4\/42\/Find-the-Greatest-Common-Divisor-of-Two-Integers-Step-14-Version-2.jpg\/v4-460px-Find-the-Greatest-Common-Divisor-of-Two-Integers-Step-14-Version-2.jpg","bigUrl":"https:\/\/www.wikihow.com\/i mages\/thumb\/4\/42\/Find-the-Greatest-Common-Divisor-of-Two-Integers-Step-14-Version-2.jpg\/v4-728px-Find-the-Greatest-Common-Divisor-of-Two-Integers-Step-14-Version-2.jpg","smallWidth":460,"smallHeight":345,"bigWidth":728,"bigHeight":546,"licensing":"<div class=\"mw-parser-output\"><\/div>"} 2 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
{"smallUrl":"https:\/\/www.wikihow.com\/images_en\/thumb\/4\/45\/Find-the-Greatest-Common-Divisor-of-Two-Integers-Step-15-Version-2.jpg\/v4-460px-Find-the-Greatest-Common-Divisor-of-Two-Integers-Step-15-Version-2.jpg","bigUrl":"https:\/\/www.wikihow.com\/i mages\/thumb\/4\/45\/Find-the-Greatest-Common-Divisor-of-Two-Integers-Step-15-Version-2.jpg\/v4-728px-Find-the-Greatest-Common-Divisor-of-Two-Integers-Step-15-Version-2.jpg","smallWidth":460,"smallHeight":345,"bigWidth":728,"bigHeight":546,"licensing":"<div class=\"mw-parser-output\"><\/div>"} 3共通の素因数を見つける
- 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
{"smallUrl":"https:\/\/www.wikihow.com\/images_en\/thumb\/2\/23\/Find-the-Greatest-Common-Divisor-of-Two-Integers-Step-16.jpg\/v4-460px-Find-the-Greatest-Common-Divisor-of-Two-Integers-Step-16.jpg","bigUrl":"https:\/\/www.wikihow.com\/i mages\/thumb\/2\/23\/Find-the-Greatest-Common-Divisor-of-Two-Integers-Step-16.jpg\/v4-728px-Find-the-Greatest-Common-Divisor-of-Two-Integers-Step-16.jpg","smallWidth":460,"smallHeight":345,"bigWidth":728,"bigHeight":546,"licensing":"<div class=\"mw-parser-output\"><\/div>"} 4 つの素因数を掛け合わせて最大公約数を求めます。
- 24 と 18 の例では、2 を 3 倍すると 6 となり、これが最大公約数となります。
- 50 と 35 の例では、5 が唯一の共通の素因数であり、最大公約数とも呼ばれます。
5が完了しました。広告する

ヒント

別の書き方は、被除数 mod 除数 = 剰余です。余りが 0 の場合、GCD (最大公約数) (a,b) = b です。それ以外の場合、GCD (a,b) = GCD (b, a mod b)
たとえば、GCD(-77,91) を見つけます。まず-77を77に置き換えます。GCD(-77,91)はGCD(77,91)になります。 77 は 91 より小さいので、位置を入れ替えます。数式を使用して計算できるかどうかを確認してください。次に、77 mod 91 は 77 (77 = 91 x 0 + 77) なので、最大公約数として 0 は不要です。そのため、(a, b) は (b, a mod b) に変換され、GCD(77,91) = GCD(91,77) となります。 91 mod 77 は 14 です (つまり、14 が余りです)。0 ではないので、GCD(91,77) を GCD(77,14) に置き換えます。 77 mod 14 は 7 であり、これも 0 ではありません。したがって、GCD(77,14) を GCD(14,7) に置き換えることができます。 14 mod 7 は 0 です。 14 = 7 * 2には余りがないので、最大公約数はGCD(-77,91) = 7です。
「a」と「b」が両方とも 0 の場合、ゼロ以外の任意の数がそれらの共通の因数となるため、最大公約数は存在しません。数学者は一般的に、最大公約数は 0 であると言いますが、この例の方法を使用すると、それが得られます。
この方法を使用すると、分数を非常に効果的に簡略化できます。たとえば、上記の例では、-77/91 は -11/13 に簡略化されます。これは、7 が -77 と 91 の最大公約数であるためです。

広告する

<<: ふわふわのお団子の作り方

>>: カクテルの作り方