大学入試数学 最大公約数と和の条件—互いに素な二数へ直して可能な組を証明する｜武蔵野個別指導塾

正整数の組を絞り、順序と逆向きの確認までたどります。焦点は最大公約数と和の条件です。

よくあるのは、高校生が演習を解き直すとき、和だけが合う組をすべて答えに残してしまう場面です。たとえば和が決まれば、小さい方から順に並べることはできます。しかし、並べた組の中には指定された数より大きな公約数を持つものもあります。和の式を満たすことと、最大公約数が指定どおりであることは別の条件です。両方を使って候補を絞り、最後に元の条件へ戻す道筋を見ていきます。

和と最大公約数のどちらから使うか

自然数は1以上の整数とします。正整数の組を求める問題では、まず和が最大公約数の倍数かを見ます。倍数でなければ、その最大公約数は両方を割るので和も割るはずだ、という事実に反します。これは解が存在しない場合の判定です。逆に、倍数なら必ずどんな追加条件も満たせるとは限りません。

典型的な問いは、和と最大公約数から組を列挙する型と、和に文字を含めて組の存在や個数を調べる型です。どちらでも、最大公約数で両方を割ってから和を調べます。さらに「順序を区別する」なら (a, b) と (b, a) は、a と b が異なるとき別の順序対です。区別しないなら大小を決めて片方だけを数えます。条件を書き換える前に、この読み取りを答案の最初に置くと数え直しを防げます。

共通の部分を取り除くと何が残るか

正整数 a, b の最大公約数を d とすると、正整数 x, y を用いて a = dx、b = dy と書けます。このとき x と y は互いに素、つまり最大公約数が1です。もし両方に1より大きい公約数があれば、d にその公約数を掛けた数が a と b の公約数になり、d が最大であることに反します。

逆も必要です。x, y が互いに素なら、dx と dy の最大公約数は d です。実際、d は共通の約数です。また x と y の最大公約数が1であることから、整数 u, v が存在して ux + vy = 1 と書けます。dx と dy の任意の公約数は、その整数の組合せである d も割るので、d を超えません。したがって最大公約数は d です。この逆向きが、縮めた候補を元に戻すときの根拠です。

和を S とすると、a + b = S は d(x + y) = S になります。S が d で割り切れるとき、商を N とおけば x + y = N です。ここで x, y は正整数なので 1 ≤ x ≤ N − 1 です。さらに y = N − x だから、x と y の共通の約数は x と N の共通の約数と一致します。両方を割る数は和 N も割り、x と N を割る数は差 N − x も割るからです。よって gcd(x, y) = gcd(x, N) です。ここで gcd は正整数の最大公約数を表します。

図1のように、元の条件、縮めた和、互いに素という条件を対応させます。単に d の倍数を並べるだけでは、縮めた後にも共通の因子が残る候補を除けません。たとえば N が偶数なら、偶数の x は N と2を公約数に持つため除外できます。ただし奇数なら必ず残るわけではなく、N に別の素因数があればそれとの共通因子も調べます。

候補を調べる順番にも理由があります。最初に範囲を定めれば、調査が有限であり、漏れなく調べたことが伝わります。次に N の素因数で割れるかを判定します。N と x に1より大きな公約数があれば、その公約数は素因数を持ち、それは N の素因数でもあります。したがって N のどの素因数でも割れないことを調べれば十分です。1は素因数を持たず、どの正整数とも互いに素です。

基本例題：縮めた和を一覧にする

【例題1・標準】正整数 a, b が a + b = 30、gcd(a, b) = 3 を満たします。順序を区別せず、可能な組をすべて求めてください。

3は30を割るので、和の条件だけで不可能とは決まりません。a = 3x、b = 3y とおくと、x, y は互いに素な正整数です。順序を区別しないので x ≤ y として調べます。

3x + 3y = 30
x + y = 10
1 ≤ x ≤ 5

x と y が互いに素であることは、x と10が互いに素であることと同じです。1から5までの候補を並べると、x = 1, 3 が残ります。2と4は2を、5は5を10と共有します。対応する y はそれぞれ9、7です。

図2のように、候補を除く理由を元の数ではなく縮めた和との公約数で見ます。元に戻すと答えは {3, 27}、{9, 21} です。波括弧は順序を区別しない組を表します。

必要性は、任意の解を3で割ったときに上の一覧に入ることから示せました。十分性も確認します。3 + 27 = 30、9 + 21 = 30 であり、それぞれを3で割った組 (1, 9)、(3, 7) は互いに素です。したがって元の最大公約数はいずれも3です。候補を見つけただけで終えず、除外と逆向きの両方を言葉にします。

別の方法として、元の和30から正整数の組を列挙し、各組の最大公約数を調べても解けます。ただし、3の倍数であるという条件を後回しにすると表が大きくなります。先に縮めると、和と公約数の2条件を一つの小さな範囲で判定できます。

順序と追加条件を答案に残す

【例題2・やや難】正整数 a, b が a + b = 56、gcd(a, b) = 4 を満たし、さらに a < b です。条件を満たす順序対 (a, b) をすべて求めてください。

4で割り a = 4x、b = 4y とおきます。x, y は互いに素で、大小の向きは正の数4で割っても変わりません。

x + y = 14
x < y
1 ≤ x < 7

14の素因数は2と7です。1から6では7の倍数はなく、偶数の2、4、6を除くと x = 1, 3, 5 です。よって (x, y) は (1, 13)、(3, 11)、(5, 9) です。これを4倍して、答えは (4, 52)、(12, 44)、(20, 36) です。

元の和はいずれも56です。縮めた各組は互いに素なので、元の最大公約数は4です。また小さい数を前に置いているため a < b も成り立ちます。逆向きの (52, 4) などは和と最大公約数を満たしますが、大小条件を満たさないので答えに入りません。順序対だから自動的に両向きを入れるのではなく、各向きが追加条件に合うかを判定します。

大小条件がなければ、各組を入れ替えた3組も加わります。ここでは x = y という中央の候補がありません。一般に x = y で互いに素となるのは x = y = 1 の場合だけなので、和が2の場合には、入れ替えても同じ順序対を二重に数えない注意が必要です。中央があるかを確かめずに個数を2倍する方法は使えません。

【例題3・難】正整数 a, b の和は 36、最大公約数は正整数 d です。順序を区別する組 (a, b) がちょうど2組となるような d をすべて求め、その組も示してください。

まず d は36の正の約数です。a = dx、b = dy、N = 36/d とおくと、x + y = N、gcd(x, y) = 1 です。正整数2つの和なので N ≥ 2 です。36の約数のうち、この条件を満たす N は 2, 3, 4, 6, 9, 12, 18, 36 です。これで検査範囲を尽くしています。

N = 2 では (x, y) = (1, 1) の1組です。N = 3, 4, 6 では、1から N − 1 のうち N と互いに素な x はそれぞれ次のとおりです。

N = 3: 1, 2
N = 4: 1, 3
N = 6: 1, 5

それぞれ2組です。一方 N = 9 では 1, 2, 4, 5 が、N = 12 では 1, 5, 7, 11 が互いに素です。N = 18 では 1, 5, 7, 11 が、N = 36 では 1, 5, 7, 11 が互いに素です。これらは少なくとも4組あるため、全個数を数えなくても2組ではありません。いずれも範囲内の異なる x であり、y = N − x も正です。

したがって N = 3, 4, 6 で、d = 12, 9, 6 です。元の組は順に次のとおりです。

d = 12: (12, 24), (24, 12)
d = 9: (9, 27), (27, 9)
d = 6: (6, 30), (30, 6)

各組は和が36で、縮めた組が互いに素ですから最大公約数も指定した d です。候補を除く際には「4個以上ある」という根拠だけで足りますが、残した場合にはちょうど2個であることまで調べます。文字を含む場合も、まず割り切れる条件と正の範囲から有限にすることが分かれ目です。

和だけ合う組を残した答案を直す

例題1で「3の倍数で和が30だから {6, 24} も答え」とした答案を考えます。和は確かに30で、両方とも3の倍数です。しかし最大公約数は6であり、3ではありません。3が公約数であることは必要ですが、最大であることまで保証しません。

図3のように、{6, 24} を3で割ると {2, 8} になり、2という共通因子が残ります。これを取り除き、縮めた組が互いに素のものだけを採用します。反対に、和を確かめずに互いに素の組だけ選ぶのも不十分です。縮めた和と互いに素の両方を確認してから元の数へ戻します。

もう一つの失敗は、和が最大公約数で割り切れないのに整数でない商を用いて候補を探すことです。共通の約数は和も割るので、その時点で解なしと結論できます。これは計算が途中で止まったのではなく、条件同士の矛盾を示した答案です。さらに、順序を区別しない問いで入れ替えを2組に数えた場合は、集合として同じ組かどうかを書いて整理します。

自分で確かめる5問

次の各問で自然数は1以上とします。答えは指定された形で示し、候補を尽くした理由と元の条件の確認も書いてください。

1. 【標準】和が42、最大公約数が3の正整数の組を、順序を区別せずすべて求めてください。
2. 【標準】和が35、最大公約数が6の正整数の組が存在するか答え、理由を示してください。
3. 【やや難】和が60、最大公約数が5である正整数の順序対 (a, b) をすべて求めてください。
4. 【やや難】和が48、最大公約数が4で、a < b を満たす正整数の順序対 (a, b) の個数を求めてください。
5. 【難】和が24の正整数の順序対 (a, b) で、最大公約数が a と b の差に等しいものをすべて求めてください。

練習の答えと戻し方

1. 3で割ると x + y = 14、x ≤ y、gcd(x, 14) = 1 です。1 ≤ x ≤ 7 のうち該当するのは1、3、5です。したがって {3, 39}、{9, 33}、{15, 27} です。各組の和は42で、3で割った組は (1, 13)、(3, 11)、(5, 9) と互いに素です。

2. 存在しません。6が両方を割るなら和も6で割り切れますが、35は6で割り切れません。和が35であるという元の条件と、最大公約数が6であるという条件が両立しないためです。

3. 5で割ると x + y = 12 で、1 ≤ x ≤ 11 です。12と互いに素な x は1、5、7、11です。順序を区別するので答えは (5, 55)、(25, 35)、(35, 25)、(55, 5) です。いずれも和が60で、縮めた組は互いに素なので最大公約数は5です。

4. 4で割れば x + y = 12、x < y なので 1 ≤ x ≤ 5 です。12と互いに素な候補は1と5で、2組です。元に戻すと (4, 44)、(20, 28) です。それぞれ和が48、最大公約数が4であり、前の数が後の数より小さいことも確かめられます。

5. 最大公約数を d とし a = dx、b = dy とします。差は正なので a > b、条件より d(x − y) = d です。d > 0 だから x − y = 1、また d(x + y) = 24 です。x + y は奇数で3以上の24の約数ですから3です。よって x = 2、y = 1、d = 8 となり、答えは (16, 8) です。和は24、差は8、最大公約数も8で、すべての条件に戻ります。

手元に残す要点

• 最大公約数 d は和を割ります。
• d で両数を割ると互いに素な正整数になります。
• 縮めた和 N と一方の数が互いに素か調べます。
• 範囲と順序を明示し、候補を尽くします。
• 元に戻して和と最大公約数を確認します。

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

候補が多すぎるときは、最初に共通の数で割ったかを確かめます。候補は出るのに答えが合わないときは、公約数であることと最大公約数であることを分け、縮めた2数に共通因子が残っていないかを見ます。個別指導で答案を検討するなら、和の式、縮めた後の範囲、除外した数の理由を順に説明できるかを確認します。順序の扱いと逆向きの確認まで書けば、可能な組を漏れなく証明できます。