大学入試数学 一次式どうしの公約数—整数の一次結合で共通因子の候補を固定する｜武蔵野個別指導塾

文字を消して定数を作り、その約数を元の2式で確かめる手順から、候補を絞る一次式の公約数です。

よくあるのは、高校生が演習を解き直すとき、2つの一次式に大きな整数を代入し、そのたびに両方を素因数分解する場面です。数値を1組調べるには有効でも、文字が動くすべての場合を調べるには終わりが見えません。係数をそろえて差を取ると、文字を含まない整数が現れます。その整数の約数に候補を絞り、元の式へ戻して確かめる方法を考えます。

何を固定し、何を調べ直すか

整数 n に対して 2n + 1 と 3n + 4 の公約数を考えるとき、2式の値そのものは n とともに変化します。一方、前者の3倍から後者の2倍を引くと、いつも -5 です。どんな n でも公約数はこの -5 を割ります。大きな値が出ても、調べる候補は正の約数 1 と 5 に固定されます。

問題の出方には、最大公約数の取り得る値を求める型、互いに素となる n の条件を求める型、ある整数が公約数となる n を求める型があります。いずれも最初に見るのは、2式が同時に割り切れるという条件です。最大公約数を直接決めようとする前に、公約数全体に共通する制約を作ります。

ただし、固定された数の約数なら何でも公約数になるわけではありません。候補は必要条件であり、元の2式を割るかという逆向きの確認が残ります。さらに「取り得る値」を問われたら、その値を実現する n が存在することも示します。候補を列挙した段階と、答えが実際に現れる段階を分けると、答案の抜けを見つけやすくなります。

差で文字を消すと何が残るか

整数 A、B と正整数 d について、A = du、B = dv を満たす整数 u、v があるとき、d は A と B の公約数です。A または B が負でも定義は同じです。0 は任意の正整数で割り切れますが、両方が 0 のときは最大公約数を定めないので、最大公約数を問う場合は2式が同時に0にならないことを確認します。

d が A と B を割るなら、整数 r、s に対して rA + sB も割ります。実際、rA + sB = d(ru + sv) で、括弧の中は整数です。この形を整数の一次結合と呼びます。引き算も、負の整数を掛けた和として含まれます。

A = an + b、B = cn + e とすると、a、b、c、e は整数で、次が成り立ちます。

cA - aB = c(an + b) - a(cn + e)
        = bc - ae

したがって、A と B のどの正の公約数も定数 bc − ae を割ります。定数が負なら、その正の約数は絶対値の正の約数です。定数が 0 なら、すべての正整数が 0 を割るため、この情報だけでは候補を有限にできません。その場合は2式の関係を調べ直します。係数に共通因子があれば両方をその因子で割った整数を使い、より小さい定数を得られる場合もあります。

図1のように、まず一次結合で候補を絞り、次に候補ごとに元の2式を調べます。矢印は一方向です。後戻りの確認を省いて、定数を割ることから2式を割ることを結論してはいけません。

図1の候補は、最大公約数の候補としても使えます。ただし、その候補 d が2式を割るとわかっても、最大公約数が d と確定するとは限りません。d より大きい候補が同時に割る場合があるからです。大きい候補を排除するか、公約数の候補をすべて確認して最大を選びます。

例えば候補が 1、2、4 のとき、2が公約数であることだけから最大公約数を2とは言えません。4も公約数かどうかが分かれ目です。反対に、候補が 1 と素数 p のみなら、p が共通に割る場合は最大公約数が p、そうでない場合は 1 です。この違いは候補の包含関係から生じます。

基本例題：候補が素数のとき

【例題1・標準】n を整数とします。2n + 1 と 3n + 4 の最大公約数を、n を5で割った余りに応じて求めてください。答えは余りごとに最大公約数を示してください。

まず両式が同時に0になることはありません。仮に両方0なら次の一次結合も0ですが、実際は -5 だからです。正の最大公約数を d とすると、

3(2n + 1) - 2(3n + 4) = -5

より d は 5 を割ります。したがって d の候補は 1、5 です。5 が公約数となる条件を調べるため、n = 5q + r、0 ≦ r ≦ 4 と置きます。q、r は整数です。

2n + 1 = 5(2q) + 2r + 1
3n + 4 = 5(3q) + 3r + 4

r を 0、1、2、3、4 と順に入れると、最初の式が5で割り切れるのは r = 2 の場合です。このとき2つ目の式も 3・2 + 4 = 10 により5で割り切れます。よって答えは、余りが 2 なら 5、それ以外なら 1 です。

図2のように、5つの余りのうち最初の式を割る行を見つけ、その行で2つ目の式も確認します。余りが2の n は n = 2、7 など実際に存在します。例えば n = 2 では2式は 5、10 で、最大公約数は5です。余り0の n = 0 では1、4となり、最大公約数は1です。いずれの候補も実現します。

この例では、一次結合が -5 だからといって、2式のどちらかが必ず5の倍数になるとは限りません。公約数が5を超えないことと、5が公約数になることは別の主張です。また、n が負でも、正の整数5で割った余りは0から4のいずれかなので、同じ分類に含まれます。

候補が合成数なら最大まで調べる

【例題2・やや難】n を整数とします。3n + 2 と 5n + 6 の最大公約数の取り得る値をすべて求め、それぞれを実現する整数 n を1つずつ示してください。

文字を消すと、

5(3n + 2) - 3(5n + 6) = -8

です。両式が同時に0なら左辺は0となり -8 に反するため、最大公約数は定まります。その値は8の正の約数 1、2、4、8 のいずれかです。ここで4が公約数となる n があっても、その n で8が公約数なら最大公約数は8です。候補の実現は別に確かめます。

n = 1、0、2、6 を順に代入すると、次のようになります。

n = 1: 3n + 2 = 5、5n + 6 = 11、最大公約数は 1
n = 0: 3n + 2 = 2、5n + 6 = 6、最大公約数は 2
n = 2: 3n + 2 = 8、5n + 6 = 16、最大公約数は 8
n = 6: 3n + 2 = 20、5n + 6 = 36、最大公約数は 4

例えば最後の行は、20と36を4で割ると5と9になり、5と9は互いに素です。したがって4より大きい公約数はありません。候補の4つがそれぞれ実現したので、答えは 1、2、4、8 です。候補が有限であり、それ以外がないことと、各候補に実例があることを合わせて全体が決まります。

別の見方では、n の余りを8通りに分け、各行の2式を8の約数で調べても答えられます。すべての n に対する分類が必要ならその方法が適します。一方、取り得る値だけを問うこの問題では、上限となる候補を証明した後、それぞれに1例を示す方が短く済みます。実例を見つけるだけでは候補以外の値の排除にならない点には注意します。

係数の共通因子がある場合

【例題3・難】n を整数とします。6n + 4 と 9n + 10 の最大公約数が 2 となる n を、ある正整数で割った余りを用いてすべて表してください。

まず、両式が同時に0なら以下の一次結合が0になるはずですが、実際は -8 です。したがって最大公約数は定まります。係数の最大公約数 3 を使えば、3倍と2倍で文字を消せます。

3(6n + 4) - 2(9n + 10) = -8

公約数は8の約数です。最初の式は常に偶数なので、最大公約数が2になるには、2つ目の式も偶数である必要があります。9n + 10 は n と同じ偶奇なので、n は偶数です。n = 2k と置くと、

6n + 4 = 2(6k + 2)
9n + 10 = 2(9k + 5)

となります。共通の2を取り出した後、最大公約数が2となる条件は、括弧内の2整数が互いに素であることです。この2整数の公約数も、次の式から4を割ります。

3(6k + 2) - 2(9k + 5) = -4

したがって互いに素でないなら共通の素因数は2です。6k + 2 は常に偶数なので、9k + 5 が奇数なら互いに素、偶数なら互いに素ではありません。9k + 5 が奇数となるのは k が偶数の場合です。逆に k が偶数なら、元の2式はともに2で割れ、4では同時に割れないため、8の約数である最大公約数は2です。

結論は n を4で割った余りが0、すなわち n = 4t、t は整数です。例えば n = 4 では2式は28と46で、最大公約数は2です。n = 2 では16と28で最大公約数が4となり、単に n が偶数という条件では足りません。n が奇数なら2つ目の式が奇数なので最大公約数は2になれません。必要性と十分性の両方を確認しました。

ここで最初の係数を機械的に9倍と6倍で消すと -24 が得られます。これも正しい制約ですが、不要な因子3が入り、候補が増えます。小さい係数の一次結合を探すと逆確認が軽くなります。ただし、より小さな定数を見つけられなくても、0でない定数なら有限の候補に絞る方針は有効です。

逆向きに飛んだ答案を直す

例題1について「公約数は5を割る。5は5を割るから、いつでも最大公約数は5」と書いたとします。前半は正しく、後半の推論が逆向きです。n = 0 を入れると2式は1と4で、5はどちらも割りません。この1例で「いつでも」という主張は崩れます。

図3のように、一次結合から進めるのは公約数から定数の約数への矢印です。逆向きに候補を戻すときは、各式の整除という別の確認が必要です。例題1なら n の余りが2のときに両式が5で割り切れると示して初めて、5が公約数だと結論できます。

別の失敗は、最大公約数の候補に 1 があることから、すべての n で互いに素だとするものです。1はどの整数の公約数でもあるため、これだけでは他の公約数の有無がわかりません。共通の素因数を排除する、または候補のうち1以外を元の式で排除する必要があります。

また、2式の一方が0になる n を見落とさないようにします。一方が0でも他方が0でなければ、公約数は0でない方の正の約数で、最大公約数はその絶対値です。両方が0になる可能性のある問題では、その場合を先に分けます。一次結合の定数が0でない例題1〜3では、同時に0となる場合はありません。

手を動かして確かめる5問

いずれも n は整数です。最大公約数は正とし、2式が同時に0でないことを確認して答えてください。

1. 【標準】4n + 1 と 7n + 3 の最大公約数を、n を5で割った余りごとに求めてください。
2. 【標準】5n + 1 と 8n + 3 の最大公約数の取り得る値をすべて求め、各値を与える n を1つずつ示してください。
3. 【やや難】2n + 3 と 4n + 1 の最大公約数が5となる n を、5で割った余りで表してください。
4. 【やや難】4n + 2 と 6n + 8 の最大公約数が2となる n を、5で割った余りで表してください。
5. 【難】3n + 1 と 7n + 5 の最大公約数の取り得る値をすべて求め、各値を与える n を1つずつ示してください。

5問の答えと考え方

1の答え

7(4n + 1) - 4(7n + 3) = -5

同時に0にならず、最大公約数は1または5です。4n + 1 が5で割り切れるのは n の余りが1のときです。このとき 7n + 3 も5で割り切れます。よって余り1なら5、余り0、2、3、4なら1です。n = 1 では5と10、n = 0 では1と3となり、それぞれ元の条件に合います。

2の答え

8(5n + 1) - 5(8n + 3) = -7

同時に0にならず、候補は1と7です。n = 4 では21と35で最大公約数は7、n = 0 では1と3で最大公約数は1です。両候補が実現するので答えは1、7です。定数の約数以外が現れないことと、代入による存在をそれぞれ示しています。

3の答え

2(2n + 3) - (4n + 1) = 5

同時に0にならず、最大公約数は1または5です。2n + 3 が5で割り切れるのは n を5で割った余りが1の場合です。その場合、一次結合の式から 4n + 1 も5で割り切れます。逆に最大公約数が5なら最初の式が5で割れるので、同じ余りが必要です。答えは余り1です。n = 1 では5と5となり、条件に戻ります。

4の答え

3(4n + 2) - 2(6n + 8) = -10

この定数でも候補は絞れますが、両式から2を取り出すと見通しがよくなります。2n + 1 と 3n + 4 の最大公約数を考えると、

3(2n + 1) - 2(3n + 4) = -5

となるため、元の最大公約数は2または10です。5が括弧内の公約数となるのは、n を5で割った余りが2のときです。したがって最大公約数が2となるのは、5で割った余りが0、1、3、4のときです。n = 0 では2と8で最大公約数は2、n = 2 では10と20で最大公約数は10です。

5の答え

7(3n + 1) - 3(7n + 5) = -8

同時に0にならず、候補は1、2、4、8です。n = 0 では1と5で1、n = 1 では4と12で4、n = 3 では10と26で2、n = 5 では16と40で8です。いずれも2式に代入して得た値で、各最大公約数を直接確認できます。4候補がすべて実現するので答えは1、2、4、8です。

答案に残す要点

1. 共通の正の約数は、2式の整数の一次結合を割ります。
2. 文字を消した定数が0でなければ、その正の約数に候補が絞れます。
3. 候補を元の2式に戻し、最大かどうかと実現するかを確かめます。
4. 定数が0の場合や、2式が同時に0となる場合は別に扱います。

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

係数をそろえる計算で止まるなら、2式をそれぞれ何倍すれば n の係数が一致するかを書き出します。候補までは出せるのに答えが合わないなら、候補から元の2式へ戻る行を指でたどり、必要条件と十分性を区別します。個別指導で確認するときも、具体的な n を1つ代入した後、別の余りではどうなるかを問い、計算と論理のどちらでつまずいたかを見ます。一次結合は候補を固定し、元の式への代入がその候補の行き先を決めます。