高校数学A 最大公約数と最小公倍数の逆算—二数の積と互いに素の条件から候補を絞る｜武蔵野個別指導塾

最大公約数と最小公倍数から二数を探し、積が合っても共通因子が残る候補を除く鍵は逆算です。

よくあるのは、高校生が2数の積に合う因数の組を並べ、そのまま答えにしてしまう場面です。積が合うことは必要ですが、それだけでは最大公約数まで指定どおりとは限りません。割った後の2数に共通因子が残っていないかを調べると、残す組と除く組の境目が見えます。

ここで扱う2数は正整数です。最大公約数と最小公倍数が与えられたときに元の数を求め、候補の漏れや条件に合わない組を調べます。約数や倍数は、数学Aの「数学と人間の活動」で扱う整数の内容です。

何を先に決めるか

出方には、与えられた最大公約数と最小公倍数から2数の組を全部求める型があります。また、組の個数を数える型や、和や上限などの追加条件で組を選ぶ型もあります。どの場合も、2数の順序を区別するか、同じ数を認めるかを問題文から読み取ります。

最大公約数を g、最小公倍数を L とすると、まず g が L を割り切るかを確認します。割り切れなければ、条件を満たす正整数の組はありません。割り切れる場合は L/g を作り、その因数の組を調べます。ここでの割り切れるという判定は出発点であり、元の2数の候補を無条件に採用する許可ではありません。

順序を区別しない場合は、割った後の小さい方を u、大きい方を v として u ≤ v にそろえると重複を防げます。順序を区別する問題なら、異なる2数を入れ替えた組も別に数えます。同じ数の組は入れ替えても増えません。

公約数で割ると何が残るか

正整数 a、b の最大公約数が g なら、ある正整数 u、v を使って a = gu、b = gv と書けます。u と v は互いに素、つまり最大公約数が 1 です。もし 1 より大きい共通の約数 d が残るなら gd が a と b の共通約数になり、g が最大という条件に反します。

正整数の最小公倍数は、その2数のどちらの倍数でもあります。共通の倍数は g の倍数なので、最小公倍数 L も g の倍数です。したがって g が L を割ることは、解が存在するための必要条件です。

互いに素な正整数 u、v の最小公倍数は uv です。素因数を考えると、u と v の両方に同じ素数は現れないので、それぞれに必要な素因数を合わせた積が最小の共通倍数になります。両数を g 倍すると最小公倍数も g 倍されるため、L = guv です。これは g が 1 の場合や u = v = 1 の場合にも成り立ちます。

図1のように、元の2数を g で割ると、互いに素な因数の組へ移ります。逆にその組へ g を掛ければ元の数に戻ります。

図1の対応で大切なのは、矢印を両方向にたどれることです。正整数 u、v が互いに素で uv = L/g なら、gu と gv の最大公約数は g、最小公倍数は guv = L です。必要な条件を得るだけでなく、その条件を満たす候補が元の問いにも十分であることまで確認しています。

また a・b = g・L が成り立ちます。実際、a・b = (gu)(gv) = g・(guv) = g・L です。ただしこの積の式だけから、任意の因数の組の最大公約数が g と決まるわけではありません。共通因子を除く判定を加えて初めて逆算できます。

g と L が正整数で g が L を割るなら、u = 1、v = L/g は必ず互いに素です。したがって、この条件は解の存在にも十分です。特に g = L なら u = v = 1 となり、順序にかかわらず元の組は (g, g) です。g と L の大小だけを見て、割り切れるかを調べ忘れないようにします。

基本例題：因数の組を端から調べる

正整数 a、b の最大公約数が 7、最小公倍数が 420 です。a ≤ b として、組 (a, b) をすべて求めてください。

7 は 420 を割り切るので、候補は存在します。a = 7u、b = 7v と置くと u、v は互いに素な正整数で u ≤ v です。最小公倍数の式から次のように求めます。

7uv = 420
uv = 420 / 7
uv = 60

u は 60 の正の約数で、u ≤ v より u² ≤ 60 です。8² は 60 より大きいので、u は 1 から 7 までを調べれば足ります。割り切れる u と対応する v を並べ、共通の約数を調べます。

u     v     最大公約数
1    60       1
2    30       2
3    20       1
4    15       1
5    12       1
6    10       2

図2のように積が 60 でも、2 と 30、6 と 10 はそれぞれ 2 を共通因子に持ちます。7 を掛ける前にこの2組を外します。

残る4組をそれぞれ 7 倍すると答えは次のとおりです。

(a, b) = (7, 420), (21, 140), (28, 105), (35, 84)

元の条件へ戻して確かめます。最大公約数は順に 7、7、7、7 です。それぞれの積は 2940 なので、正整数2個の積と最大公約数・最小公倍数の関係から最小公倍数は 2940 / 7 = 420 です。a ≤ b も各組で満たします。

この列挙が尽くされる理由は、u が 60 の正の約数で、u ≤ v のもとでは 60 の平方根以下に限られるからです。1 から 7 の割り切れる数をすべて試しており、それ以外に小さい側の候補はありません。2数の順序を区別する問いなら、4組はいずれも異なる数なので、逆順も加えて8組になります。

標準例題：共通因子が残る組を除く

正整数 x、y の最大公約数が 11、最小公倍数が 693 です。順序を区別せず、考えられる2数の組をすべて求めてください。

693 は 11 で割り切れます。x = 11u、y = 11v と置き、小さい方を u とします。u、v は互いに素です。

11uv = 693
uv = 693 / 11
uv = 63
63 = 3²・7

u ≤ v として因数の組を並べます。8² > 63 なので、u は 1 から 7 の範囲です。

(u, v) = (1, 63), (3, 21), (7, 9)

(3, 21) には共通因子 3 があるため除きます。(1, 63) と (7, 9) は互いに素なので残ります。11 を掛けると、答えは (11, 693)、(77, 99) です。

確認すると、11 と 693 の最大公約数は 11、最小公倍数は 693 です。77 と 99 の最大公約数も 11 であり、その積 7623 を 11 で割ると 693 です。両方とも正整数で、逆順を新たな組として数えていません。

3² を片方にまとめれば、もう片方には 3 が現れません。これを 3 と 3 に分けると互いに素ではなくなるので、積が正しいだけの (3, 21) は使えません。小さい候補から割って調べる方法でも、素因数のまとまりを分ける方法でも、この点を同じように確認します。

発展例題：和が最小の組を探す

正整数 p、q の最大公約数が 5、最小公倍数が 1155 です。p ≤ q として、p + q が最小となる組とその和を求めてください。

5 は 1155 を割り切ります。p = 5u、q = 5v と置くと、u、v は互いに素で u ≤ v です。積と和を割った後の数で表します。

5uv = 1155
uv = 1155 / 5
uv = 231
p + q = 5u + 5v
p + q = 5(u + v)

231 = 3・7・11 です。u² ≤ 231 であり、16² > 231 なので、u は 1 から 15 までを調べます。231 の約数でこの範囲に入るものは 1、3、7、11 です。それぞれについて v と和を出します。

u     v     u + v
1    231      232
3     77       80
7     33       40
11    21       32

4組はいずれも共通の素因数がなく、互いに素です。和が最小なのは (u, v) = (11, 21) ですから、元の組と和は次のとおりです。

p = 5・11 = 55
q = 5・21 = 105
p + q = 55 + 105 = 160

55 と 105 の最大公約数は 5 です。積 5775 を 5 で割ると 1155 であり、最小公倍数も指定に戻ります。p ≤ q と正整数の条件も満たします。

積が一定なら2数が近いほど和が小さいと予想できますが、近い整数の組が必ず積と互いに素の条件を満たすとは限りません。ここでは候補を尽くして和を比較したので、存在しない組を想定せず最小と判定できます。条件に上限が付く場合も、まず元の数に戻してから上限に入るかを確認します。

積だけを合わせた誤答を直す

基本例題で (u, v) = (2, 30) を採用すると、元の数は (14, 210) です。積は 14・210 = 2940 で、7・420 と一致します。しかし 14 は 210 を割り切るので、この組の最大公約数は 14、最小公倍数は 210 です。指定された 7 と 420 にはなりません。

図3のように、割った後に 2 が両方に残っていることが誤りの原因です。元の数に戻すと共通因子が 7・2 になり、最大公約数が大きくなります。

図3の誤答は、積の関係を逆向きに使うときに、互いに素という条件を落としたものです。修正するときは因数の組を書いた横に最大公約数を記し、1 以外の組を消してから g を掛けます。最後に元の2数で最大公約数と最小公倍数を確かめれば、表の転記間違いにも気づけます。

別の失敗は、g が L を割らないのに L/g を整数とみなして候補を探し始めることです。共通の倍数 L は共通の約数 g の倍数でなければならないので、この場合は計算を進めても解は得られません。また、u = v を認めるか迷ったときは互いに素の条件に戻ります。等しい正整数が互いに素になるのは両方が 1 の場合です。

練習問題

各問の数は正整数とし、組の順序は区別しません。必要な組は小さい数から順に書いてください。

1. 最大公約数が 13、最小公倍数が 1170 となる2数の組をすべて求めてください。
2. 最大公約数が 7、最小公倍数が 385 となる2数の組をすべて求めてください。
3. 最大公約数が 9、最小公倍数が 594 となり、どちらも 200 以下である2数の組をすべて求めてください。
4. 最大公約数が 8、最小公倍数が 275 となる2数の組が存在するか判定し、理由を述べてください。
5. 最大公約数が 4、最小公倍数が 364 となる2数の組の個数を求め、各組も書いてください。

練習問題の解答と確かめ

1

2数を 13u、13v とし、u ≤ v とします。u、v は互いに素です。

uv = 1170 / 13
uv = 90

u² ≤ 90 なので u は 1 から 9 まで調べます。因数の組は (1, 90)、(2, 45)、(3, 30)、(5, 18)、(6, 15)、(9, 10) です。共通因子がある (3, 30)、(6, 15) を除きます。

答えは (13, 1170)、(26, 585)、(65, 234)、(117, 130) です。各組の最大公約数は 13、積は 15210 で、15210 / 13 = 1170 です。元の最大公約数と最小公倍数に戻ります。

2

2数を 7u、7v とし、u ≤ v とします。割った後の2数は互いに素です。

uv = 385 / 7
uv = 55
55 = 5・11

u² ≤ 55 を満たす正の約数は 1、5 です。対応する組 (1, 55)、(5, 11) はいずれも互いに素ですから、答えは (7, 385)、(35, 77) です。最大公約数はそれぞれ 7、積は 2695 で、2695 / 7 = 385 となります。

3

2数を 9u、9v とし、u ≤ v とします。まず互いに素な候補を求め、次に上限を確かめます。

uv = 594 / 9
uv = 66

u² ≤ 66 の範囲の約数から得る因数の組は (1, 66)、(2, 33)、(3, 22)、(6, 11) です。いずれも互いに素です。9 を掛けると (9, 594)、(18, 297)、(27, 198)、(54, 99) となります。

両方が 200 以下なのは (27, 198)、(54, 99) です。それぞれの最大公約数は 9、積は 5346 で、5346 / 9 = 594 です。大きい側も順に 198、99 なので、上限を満たします。

4

組は存在しません。正整数2数の最大公約数は、それらの共通倍数である最小公倍数を割ります。しかし 275 = 8・34 + 3 なので、8 は 275 を割り切れません。したがって与えられた2条件は両立しません。

例えば大きい方の値が大きいという事実だけでは存在を決められません。余りが 0 かどうかを先に調べることで、因数の組を探す前に不可能と判断できます。

5

2数を 4u、4v とし、u ≤ v とします。u、v は互いに素です。

uv = 364 / 4
uv = 91
91 = 7・13

u² ≤ 91 の範囲の約数は 1、7 なので、因数の組は (1, 91)、(7, 13) です。どちらも互いに素ですから、元の組は (4, 364)、(28, 52) の2組です。最大公約数はどちらも 4、積は 1456 で、1456 / 4 = 364 です。順序を区別しないため、逆順を追加しません。

覚えておくこと

• 正整数の最大公約数 g は最小公倍数 L を割ります。
• 2数を gu、gv とすると u、v は互いに素で uv = L/g です。
• 因数の組を漏れなく並べ、共通因子が残る組を除きます。
• g を掛けて元に戻し、順序や上限も確認します。

どこで止まったかを見分ける

候補が多すぎるときは、積を満たすことと互いに素であることを別々に判定できているかを見ます。候補が少なすぎるときは、1 を含む組や平方根付近までの約数を落としていないかを調べます。解がないとした場合は、g が L を割るかを改めて確かめます。

個別指導では、求めた1組を使い、なぜ g で割った後に共通因子を残せないのかを本人の式で説明してもらいます。次に、表の外に候補がない理由を u ≤ v から述べ、元の2数が指定された最大公約数と最小公倍数に戻るかを一緒に点検します。逆算の答えは、候補を並べる根拠と元の条件への復元までそろって完成です。