最大公約数
2つ以上の整数に共通な約数を公約数といい、その中で最大のものを最大公約数といいます。
[例] 24と60の最大公約数
24の約数は、1, 2, 3, 4, 6, 8, 12, 24
60の約数は、1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60
よって、24と60の最大公約数は12です。
（別解1）
2 ) 24 72
3 ) 63 36
3 ) 21 12
7 4
よって、24と60の最大公約数は
2×2×3＝12
（別解2：因数分解の利用）
24と60をそれぞれ素因数分解すると
24＝2×2×2×3
60＝2×2× ×3×5
となるので、24と60の最大公約数は
2×2×3＝12
ところで、最大公約数がわかると何がうれしいのでしょうか？ここでは、簡単な例として、分数の約分との関係を紹介します。
（最大公約数の利用例）
という分数を約分することを考えます。少しずつ約分をすると
となります。
ここでは、の分母と分子を2, 2, 3で割っていますが、12(＝2×2×3)で割れば、一度で約分が完了します。そして、この12というのが分母60と分子24の最大公約数なのです！
ここまで、小・中学生で学習した範囲の知識で最大公約数を求めてきましたが、実は2つの自然数の最大公約数を簡単に計算することができるアルゴリズムが存在します。これは、「ユークリッドの互除法」と呼ばれ、数学者ユークリッドの『原論』という書に記された歴史上最古のアルゴリズムと言われています。
ユークリッドの互除法
自然数a, bの最大公約数をgcd( a, b )とする。また、aをbで割った余りをrとすると、
gcd( a , b ) = gcd( b , r )
が成立する。つまり、aとbの最大公約数は、bとrの最大公約数と等しい。
この性質を利用して割り算を繰り返し、余りrが0になったときの除数bがaとbの最小公倍数になります。
この説明だけで理解するのは難しいと思いますので、実際にユークリッドの互除法で最大公約数を計算して確認しましょう。
[例]
126と72の最大公約数を求める。（方法1）
2 ) 126 72
3 ) 63 36
3 ) 21 12
7 4
よって、126と76の最大公約数は
2×3×3＝18
（方法2：ユークリッドの互除法の利用）
126÷72＝1…54
72÷54＝1…18
54÷18＝3…0 ←余りが0になったら終わり
↑
これが最小公倍数
【問題1】ユークリッドの互除法を用いて、2つの自然数の最大公約数を求めなさい。
(1) 24, 60
(2) 143, 221
(3) 6, 35
【問題2】ユークリッドの互除法
[プログラム]
10 INPUT PROMPT "a,b=":A,B
20 LET R=＿＿＿＿＿＿＿＿＿＿＿＿
30 IF R<>0 THEN
40 LET A=＿
50 LET B=＿
60 GOTO ＿＿
70 END IF
80 PRINT "GCD(a,b)=";＿
90 END
[出力結果]
・a=60, b=24の場合
a,b=60,24 GCD(a,b)= 12
・a=24, b=60の場合
a,b=24,60 GCD(a,b)= 12
[設問]
(1) 空欄を埋めてプログラムを完成させなさい。
(2) a=60, b=24を入力した場合、30行目は何回実行されるか。
(3) a=24, b=60を入力した場合、30行目は何回実行されるか。
[発展]
このプログラムはa=60, b=24と入力しても、a=24, b=60と入力しても正しい最大公約数12が求まる。つまり、小さい数から大きい数を割ってそのあまりを求めるという計算を行っても答えは正しくなる。それはなぜか。
【問題3】分数の約分
以下のプログラムは2つの分数
（A,B,C,Dは自然数）の和を計算し、分数の形で出力するものである。和の分数は最初に約分しない形で
として得られ、E,Fの最大公約数Gを求めて約分する。このプログラムでE,Fを計算し、それらの最大公約数Gを求める部分は[ア]行から[イ]行である。プログラムの中の空欄には選択肢から最も適切なものを選びその番号を答えなさい。
[プログラム]
100 INPUT PROMPT "A=":A
110 INPUT PROMPT "B=":B
120 INPUT PROMPT "C=":C
130 INPUT PROMPT "D=":D
140 LET E=A*D+B*C
150 LET F=B*D
160 LET X=E
170 LET Y=F
180 LET R=X-Y*INT(X/Y)
190 IF R=0 THEN GOTO 230
200 LET X=[ウ]
210 LET Y=[エ]
220 GOTO 180
230 LET G=Y
240 PRINT E/G;"/";F/G
250 END
[選択肢]
(01) A (02) B (03) C (04) D (05) E (06) F (07) G (08) X (09) Y (10) R
[ヒント]
※このヒントは入試問題にはありません。
（06 慶応大）