最大公約数と最小公倍数

本日の指導は最大公約数と最小公倍数について、でした。最大公約数と最小公倍数の意味を取り違えてしまう人も多いので、まずは言葉の意味から。

最大公約数の「公」とは「共通」という意味です。
つまり、最大公約数とは最大共通約数。
これは、共通する約数のうち最大の数という意味になります。

ここで、40と48の最大公約数を求めてみます。
40と48の約数をそれぞれ列挙してみます。

40の約数・・・1, 2, 4, 5, 8, 10, 20, 40
48の約数・・・1, 2, 3, 4, 6, 8, 12, 16, 24, 48

となります。
共通する約数は、1, 2, 4, 8 ですね。
したがって、共通する約数のうち最大の数は 8 となります。
よって、40と48の最大公約数は 8 となります。・・・(答)

最大公約数の求め方には割算の筆算のような以下の簡単な方法があります。
2つの数を同時に割れる数で割れるだけ割っていきます。

2 ) 40 48
2 ) 20 24
2 ) 10 12
　　 5　6

割れるだけ割った後は、左側の割った数をすべてかけ合わせます。
2 × 2 × 2 ＝ 8・・・(答)

さらに、ユークリッドの互除法という方法もあります。
48 ÷ 40 = 1 あまり 8
40 ÷ 8 = 5
よって、最大公約数は 8 ・・・(答)

小さい数で大きい数を割る
↓
あまりで割る数を割る
↓
さらにあまりで割る数を割る

をくり返し割り切れるまで続けます。そして最後の割る数が最大公約数となります。

以下、ユークリッドの互除法をpythonで記述したプログラムになります。

# ユークリッドの互除法を利用して最大公約数を求める

a = int(input('整数a:'))
b = int(input('整数b:'))

if a < b:
    a, b = b, a

for num in range(100):
    c = a % b
    a, b = b, c
    
    if c == 0:
        break

print('最大公約数は', a, 'です。')
# 実行結果

整数a:48
整数b:40
最大公約数は 8 です。

次に、最小公倍数についてです。
これは、共通する倍数のうち、最小の数という意味になります。

ここで、27と36の最小公倍数を求めてみます。
倍数をそれぞれ列挙すると

27の倍数・・・27, 54, 81, 108, 135, 162, 129, ・・・
36の倍数・・・36, 72, 108, 144, 180,・・・

したがって、共通する倍数のうち最小の数は108となります。
最大公約数と同様に以下のような求め方もあります。

3)27 36
3) 9 12
　 3　4

割った数と最後に残った2数もすべてかけ合わせると
3 × 3 × 3 × 4 = 108
したがって、27と36の最小公倍数は108・・・(答)

最大公約数と最小公倍数には次のような関係があります。
2数の積 = 最大公約数 × 最小公倍数・・・(A)

40と48の最大公約数は8でした。
40と48の最小公倍数は240です。

(A)の左辺＝40 ×48 = 1920
(A)の右辺=8×240=1920

となり(A)式を満たします。
この関係を利用して最小公倍数を求めることもできます。

【問題】
407 と 481 の最小公倍数を求めなさい。

【解説】
まずは最大公約数を求めます。
この場合ユークリッドの互除法で求めた方が良さそうです。
481 ÷ 407 = 1 ・・・74
407 ÷ 74 = 5・・・37
74 ÷ 37 = 2
したがって、最大公約数は37
よって、最小公倍数は
407 × 481 ÷ 37 = 5291
となります。

上記の最大公約数と最小公倍数の関係をpythonで記述し最大公約数を求めるプログラミングは下のようになります。

# 最小公倍数を求める

a = int(input('整数a:'))
b = int(input('整数b:'))

p, q = a, b

if p < q:
    p, q = q, p

for num in range(100):
    r = p % q
    p, q = q, r
    
    if r == 0:
        break

c = (a * b) // p

print('最小公倍数は', c, 'です。')
# 実行結果

整数a:407
整数b:481
最小公倍数は 5291 です。