大学入試数学 対偶と素因数の条件—直接示しにくい整除命題を否定から組み直す｜武蔵野個別指導塾

「かつ」の否定を「または」に直し、平方が素数で割り切れる条件をたどり直すときに頼るのが対偶です。

よくあるのは、演習の解き直しで、対偶を作ったつもりの答案の一行目に「かつ」がそのまま残っているという場面です。もとの命題は「a も b も 3 の倍数ならば a + b は 3 の倍数である」なのに、生徒が書いた仮定は「a が 3 の倍数でない、かつ b が 3 の倍数でない」でした。この仮定は正しい対偶の仮定より狭く、a = 3、b = 1 のような組を初めから捨てています。捨てた組の分だけ証明が短くなったように見えて、実は示せていない範囲が残ります。ここでは、否定の作り方を一か所ずつ点検しながら、素因数の条件を使う整除命題を組み直します。

対偶が効くのはどんな形の問いか

整数の証明で対偶が登場するのは、仮定から出発するより、結論を否定して出発するほうが道が短いときです。出方は大きく三つに分かれます。

一つ目は、平方や積が素数で割り切れる条件を問う型です。「n² が 3 の倍数ならば n は 3 の倍数である」のように、仮定が積や平方の整除で、結論がもとの数の整除になります。この型では、n² を 3 で割った余りを直接調べようとすると、n の値から平方を作る計算が重くなります。対偶にすると、n を 3 で割った余りで場合分けする話になり、扱う数が一気に小さくなります。

二つ目は、結論に「または」や「〜でない」が入る型です。「ab が 21 の倍数でないならば、a が 3 の倍数でない または b が 7 の倍数でない」のように、否定を含む結論は、そのまま示そうとすると場合が多く散らかります。対偶を取ると、否定が仮定へ移り、仮定が一つにまとまるので、出発点がはっきりします。

三つ目は、仮定が「かつ」で結ばれている型です。この型は対偶が効くこともありますが、対偶の仮定が「または」になるため、場合分けが増えることがあります。「a も b も 3 の倍数ならば a + b は 3 の倍数である」の対偶は「a + b が 3 の倍数でないならば、a が 3 の倍数でない または b が 3 の倍数でない」であり、仮定が二股に分かれます。二股のそれぞれを同じ計算で処理できるなら対偶は強い武器になり、処理が別々になるなら直接法のほうが短くなります。

最初に見る整数条件は、割る数が素数かどうか、平方を割った余りの種類がいくつあるか、二つの数が互いに素かどうかの三つです。この三つを押さえると、対偶と直接法のどちらを選ぶかが決まります。

否定の書き換えと素因数の条件

真か偽のどちらかに定まる文だけを命題として扱います。「整数 n について、n が 6 の倍数ならば n は 3 の倍数である」は、どの n を取っても真偽が決まるので命題です。一方、「n は大きい」は n の値で真偽が変わるうえ、大きさの基準も定まらないため、命題にはなりません。「P ならば Q」という形の文では、前半の P を仮定、後半の Q を結論と呼びます。この形に対して「Q でないならば P でない」を作ったものが対偶です。もとの命題と対偶は、片方が真ならもう片方も真、片方が偽ならもう片方も偽という関係にあります。P と Q の真偽の組み合わせは四通りあり、P が真で Q が偽のときだけ「P ならば Q」は偽になります。この一通りでは「Q でない」が真で「P でない」も偽になるため、「Q でないならば P でない」も偽です。残りの三通りではどちらも真になるので、二つの命題は同じ真偽を持ちます。

否定を作るときに落とし穴になるのが、「かつ」と「または」の入れ替えです。「a が 3 の倍数であり、かつ b が 3 の倍数である」の否定は、「a が 3 の倍数でない、または b が 3 の倍数でない」です。両方に「でない」を付けて「かつ」でつなぐと、条件が強くなりすぎます。同じように、「すべての整数 n について成り立つ」の否定は「成り立たない整数 n が少なくとも一つある」であり、「n が 3 の倍数でない」の否定は「n が 3 の倍数である」です。割り切ることを表す記号では、3 | n の否定が 3 ∤ n です。否定を一段作るたびに、どの語を入れ替えたかを声に出して確かめると、この種の取りこぼしは減ります。

次に、ここから繰り返し使う素因数の条件を確認します。p を素数とします。このとき、整数 a と b について、p が ab を割り切るならば、p は a または b を割り切ります。素数は 1 とその数自身のほかに正の約数を持たないので、積を割り切る素数の力は、二つの因数のどちらか一方に必ず入ります。この条件は、p が素数であることが本体です。p が 6 のような合成数だと、6 は 2 と 3 の積を割り切りますが、2 も 3 も 6 では割り切れません。条件を使う前に、割る数が素数であることを確かめる必要があります。

互いに素という条件も、この記事の主役です。整数 a と b に共通する正の約数をすべて集め、その最大のものが 1 に収まるとき、a と b は互いに素であると呼びます。互いに素な二数は共通の素因数を持たず、逆に共通の素因数を持たなければ最大公約数は 1 です。さらに、a と b が互いに素ならば、ax + by = 1 を満たす整数 x と y が存在します。この一次結合は、整数の割り算を繰り返して余りを小さくしていく操作から作れます。素因数の条件と一次結合は、どちらも「共通の約数があれば取り出せる」という同じ考え方の別の表し方です。

図1は、もとの命題と対偶で、仮定と結論がどこへ移るかを一枚にまとめたものです。仮定の「かつ」が対偶では「または」になって戻ってくる点に注目してください。

図1のように、対偶は仮定と結論を入れ替えたうえで、それぞれを否定した形になります。入れ替えと否定の順序を間違えると、別の命題を作ってしまうので、一行ずつ書き写して確かめます。

基本例題：平方が 3 の倍数ならもとの数も 3 の倍数か

例題1【標準】n を整数とします。n² が 3 の倍数ならば、n は 3 の倍数であることを証明してください。

結論は「n は 3 の倍数である」で、否定は「n は 3 の倍数でない」です。仮定の否定は「n² は 3 の倍数でない」になります。したがって対偶は「n が 3 の倍数でないならば、n² は 3 の倍数でない」です。この形なら、n を 3 で割った余りで場合分けできます。整数 n を 3 で割った余りは 0、1、2 の三通りですが、n が 3 の倍数でないという仮定から、余りは 1 か 2 に限られます。そこで k を整数として、n = 3k + 1 と n = 3k + 2 の二つを調べます。

（i）n = 3k + 1 のときは、平方を展開して余りを出します。

n² = (3k + 1)²
= 9k² + 6k + 1
= 3(3k² + 2k) + 1

3(3k² + 2k) は 3 の倍数なので、n² を 3 で割った余りは 1 です。よって n² は 3 の倍数ではありません。

（ii）n = 3k + 2 のときも、同じ手順で計算します。

n² = (3k + 2)²
= 9k² + 12k + 4
= 9k² + 12k + 3 + 1
= 3(3k² + 4k + 1) + 1

同じく、n² を 3 で割った余りは 1 です。よって n² は 3 の倍数ではありません。

（i）と（ii）で、n が 3 の倍数でないすべての場合を尽くしました。どちらでも n² は 3 の倍数でないので、対偶が示せました。もとの命題と対偶の真偽は一致するため、n² が 3 の倍数ならば n は 3 の倍数であることが示されました。

図2は、この例題で使った余りの対応を表にしたものです。n を 3 で割った余りが 1 でも 2 でも、平方の余りは 1 になります。この表があると、場合分けの結果を一覧で確かめられます。

図2のように、平方の余りが 0 になるのは、もとの数の余りが 0 のときだけです。この一方向の対応が、対偶の証明の中心になります。逆に、平方の余りが 1 だからといって、もとの数の余りが 1 とは限らない点にも注意してください。余り 2 の平方も 1 になるので、平方からもとの数は一意に戻せません。対偶で示せるのは、余り 0 の位置が動かないという性質です。

標準例題と発展例題

例題2【標準】a と b を整数とします。a² + b² が 3 の倍数ならば、a も b も 3 の倍数であることを証明してください。

結論の「a も b も 3 の倍数である」は、「a が 3 の倍数であり、かつ b が 3 の倍数である」と同じです。この否定は「a が 3 の倍数でない、または b が 3 の倍数でない」です。したがって対偶は「a が 3 の倍数でない、または b が 3 の倍数でないならば、a² + b² は 3 の倍数でない」になります。仮定が「または」なので、二つの場合を書くことになりますが、どちらも同じ計算で処理できます。

（i）a が 3 の倍数でないとき 例題1の表から、a² を 3 で割った余りは 1 です。b² の余りは、b が 3 の倍数なら 0、そうでなければ 1 です。よって a² + b² の余りは 1 + 0 = 1 か 1 + 1 = 2 であり、どちらも 0 ではありません。

（ii）b が 3 の倍数でないとき 同じく b² の余りは 1 です。a² の余りは 0 か 1 なので、a² + b² の余りは 1 か 2 です。よって 3 の倍数ではありません。

（i）と（ii）で、対偶の仮定を尽くしました。どちらでも a² + b² は 3 の倍数でないので、対偶が示せました。もとの命題も成り立ちます。

この例題で間違えやすいのは、対偶の仮定を「a が 3 の倍数でない、かつ b が 3 の倍数でない」と書いてしまう点です。この書き方だと、a だけが 3 の倍数でない場合と、b だけが 3 の倍数でない場合が抜けます。たとえば a = 2、b = 3 のとき、a² + b² = 4 + 9 = 13 で 3 の倍数ではありませんが、この組は「a も b も 3 の倍数でない」を満たしません。示すべき範囲から外れてしまうのです。かつの否定はまたはである、という一行が答案の骨格を決めます。

例題3【やや難】p を素数、a と b を整数とします。p が ab を割り切るならば、p は a または b を割り切ることを証明してください。

この命題は、対偶を取ると「p が a も b も割り切らないならば、p は ab を割り切らない」になります。この形も正しいのですが、証明を進めるには、p と a が共通の約数を持たないことから ab の素因数を論じる必要があり、素因数分解の一意性に頼る流れになります。ここでは直接法を使うと短くなります。

p が a を割り切るならば、結論の「または」が満たされるので証明は終わりです。そこで p が a を割り切らないとします。p は素数なので、正の約数は 1 と p だけです。p は a を割り切らないので、p と a の共通の正の約数は 1 しかありません。つまり p と a は互いに素です。互いに素な二数には一次結合が作れるので、px + ay = 1 を満たす整数 x と y が存在します。この等式の両辺に b を掛けます。

pbx + aby = b

左辺の第一項 pbx は p の倍数です。第二項 aby も、p が ab を割り切るという仮定から p の倍数です。p の倍数どうしの和は p の倍数なので、右辺の b は p の倍数です。よって p は b を割り切ります。

p が a を割り切る場合と割り切らない場合の二つで、どちらでも「p は a または b を割り切る」が成り立ちました。この証明では、仮定の p が素数であることを、p と a の共通の約数が 1 しかないという場面で使っています。もし p が素数でなければ、この一歩が崩れます。p = 6、a = 2、b = 3 を考えると、6 は ab = 6 を割り切りますが、6 は 2 も 3 も割り切れません。条件を確かめずに使うと、この反例を見落とします。

この例題の結果は、平方に対しても使えます。p が n² を割り切るならば、a = n、b = n と思って条件を当てはめると、p は n を割り切ります。n² の整除から n の整除へ戻るこの一歩は、後の練習問題でも使います。

例題4【難】a、b、c を整数とします。a² + b² + c² が 4 の倍数ならば、a、b、c はすべて偶数であることを証明してください。

結論は「a、b、c はすべて偶数である」です。この否定は「a、b、c のうち少なくとも一つは奇数である」になります。「すべて」の否定が「少なくとも一つは〜でない」になる点は、かつの否定と同じくらい間違えやすいところです。対偶は「a、b、c のうち少なくとも一つが奇数ならば、a² + b² + c² は 4 の倍数でない」です。

準備として、整数を 4 で割った余りと平方の余りの関係を調べます。偶数は 2m と書けるので、その平方は 4m² となり、4 で割った余りは 0 です。奇数は 2m + 1 と書けるので、その平方は 4m² + 4m + 1 = 4(m² + m) + 1 となり、4 で割った余りは 1 です。つまり平方を 4 で割った余りは、偶数なら 0、奇数なら 1 です。

対偶の仮定では、奇数の個数が 1 個、2 個、3 個のいずれかです。それぞれの場合に、平方の和の余りを計算します。

（i）奇数が 1 個のときは、平方の余りが 1 が 1 個、0 が 2 個なので、和の余りは 1 です。（ii）奇数が 2 個のときは、1 が 2 個、0 が 1 個なので、和の余りは 2 です。（iii）奇数が 3 個のときは、1 が 3 個なので、和の余りは 3 です。

どの場合も和の余りは 1、2、3 のどれかであり、0 にはなりません。よって a² + b² + c² は 4 の倍数ではありません。対偶が示せたので、もとの命題も成り立ちます。

この例題では、奇数の個数で場合分けする前に、平方の余りが 0 か 1 の二種類しかないことを確定させました。場合分けの数を減らす準備を先に置くと、対偶の証明が短くなります。もし準備を省いて、a、b、c の偶奇の八通りを闇雲に並べると、同じ計算を繰り返す答案になります。対偶を取った後も、余りの種類を数える手間は残るという点を覚えておいてください。

誤答を直す：かつの否定をかつのままにすると何が抜けるか

例題2でよく出る誤答を、そのまま並べます。生徒の答案には「対偶は『a が 3 の倍数でない、かつ b が 3 の倍数でないならば、a² + b² は 3 の倍数でない』である」と書かれていました。計算自体は正しく、a も b も 3 の倍数でないときに a² + b² の余りが 2 になることも示されています。しかし、この答案が示したのは、対偶の仮定の一部だけです。

原因は、結論の否定を作る段階にあります。「a も b も 3 の倍数である」は「a が 3 の倍数であり、かつ b が 3 の倍数である」という二つの条件の連言です。連言の否定は、一方でも崩れれば真になるので、「または」でつながります。両方に「でない」を付けて「かつ」でつなぐと、二つとも崩れている場合しか仮定に入りません。a = 1、b = 3 のように、片方だけが 3 の倍数でない組は、正しい対偶の仮定では拾われますが、誤った仮定では捨てられます。

直し方は二段階です。第一段階で、否定の一行を「または」で書き直します。第二段階で、「または」の仮定から出発する証明では、どちらの枝も示す必要があることを確認します。例題2では、a が 3 の倍数でない枝と、b が 3 の倍数でない枝を並べました。二つの枝は計算が同じでも、答案には両方を書きます。片方だけで「対称なので同じ」と済ませるなら、その一言を添えて、読む人が枝の対応を確かめられるようにします。

図3は、誤った対偶と正しい対偶を並べたものです。左の誤りでは「かつ」が残り、右の正しい形では「または」に変わっています。答案を書き終えたら、対偶の一行目だけを指でなぞり、もとの命題の結論の否定と一致するかを確かめてください。

図3のように、違いは一語ですが、その一語が示す範囲を狭めます。範囲が狭まった答案は、計算が合っていても証明として不足します。

練習問題

次の五問を解いてください。答えは問題の後にまとめて置きます。

練習1　n を整数とします。n² が 5 の倍数ならば、n は 5 の倍数であることを証明してください。

練習2　a と b を整数とします。「a が 3 の倍数であり、かつ b が 5 の倍数ならば、ab は 15 の倍数である」という命題について、対偶を述べてください。そのうえで、もとの命題を証明してください。

練習3　a と b を正の整数とします。a と b が互いに素ならば、a + b と ab は互いに素であることを証明してください。

練習4　p を素数、n を整数とします。n² が p² の倍数ならば、n は p の倍数であることを証明してください。

練習5　p と q を異なる素数、n を整数とします。n² が pq の倍数ならば、n は pq の倍数であることを証明してください。

練習問題の答えと解き方

練習1の解き方 対偶は「n が 5 の倍数でないならば、n² は 5 の倍数でない」です。n を 5 で割った余りは 1、2、3、4 の四通りです。k を整数として、それぞれの平方の余りを計算します。n = 5k + 1 のとき n² = 25k² + 10k + 1 で余りは 1、n = 5k + 2 のとき n² = 25k² + 20k + 4 で余りは 4、n = 5k + 3 のとき n² = 25k² + 30k + 9 = 25k² + 30k + 5 + 4 で余りは 4、n = 5k + 4 のとき n² = 25k² + 40k + 16 = 25k² + 40k + 15 + 1 で余りは 1 です。どの場合も余りは 1 か 4 なので、n² は 5 の倍数ではありません。対偶が示せたので、もとの命題も成り立ちます。

練習2の解き方 もとの命題の仮定は「a が 3 の倍数であり、かつ b が 5 の倍数である」、結論は「ab は 15 の倍数である」です。結論の否定は「ab は 15 の倍数でない」、仮定の否定は「a が 3 の倍数でない、または b が 5 の倍数でない」です。よって対偶は「ab が 15 の倍数でないならば、a が 3 の倍数でない、または b が 5 の倍数でない」です。もとの命題の証明は、a = 3m、b = 5n とおくと ab = 15mn となり、m と n は整数なので ab は 15 の倍数です。

練習3の解き方 対偶は「a + b と ab が互いに素でないならば、a と b は互いに素でない」です。a + b と ab の最大公約数を d とし、d が 1 より大きいとします。d には素因数があるので、その一つを p とします。p は ab を割り切るので、素因数の条件から p は a または b を割り切ります。p が a を割り切るならば、p は (a + b) − a = b も割り切ります。p が b を割り切るならば、同じく p は (a + b) − b = a も割り切ります。どちらでも p は a と b の共通の素因数になり、a と b の最大公約数は 1 より大きくなります。よって a と b は互いに素ではありません。対偶が示せたので、もとの命題も成り立ちます。

練習4の解き方 n² が p² の倍数ならば、n² は p の倍数でもあります。p は素数なので、例題3の結果を a = n、b = n として使うと、p は n を割り切ります。よって n は p の倍数です。

練習5の解き方 n² が pq の倍数なので、n² は p の倍数であり、q の倍数でもあります。p と q は素数なので、例題3の結果から p は n を割り切り、q も n を割り切ります。p と q は異なる素数なので互いに素です。n = ps とおくと、q は ps を割り切ります。q は p を割り切らないので、素因数の条件から q は s を割り切ります。s = qt とおくと n = pqt となり、n は pq の倍数です。

覚えておくこと

• 対偶は、結論の否定から仮定の否定へ進む形で、もとの命題と同じ真偽になります。
• 否定を作るときは「かつ」を「または」へ、「すべて」を「少なくとも一つ」へ入れ替えます。
• 結論に「または」や「でない」が入るときは、対偶を取ると仮定が一つにまとまります。
• 仮定が「かつ」の命題では、対偶の仮定が「または」になり、場合分けが増えることがあります。
• 素数 p では p が ab を割り切るなら p は a または b を割り切り、互いに素な二数では一次結合が作れます。

つまずきの見分け方

対偶を書いた行に「かつ」が残っていたら、まず否定の作り方を疑ってください。もとの結論が「かつ」で結ばれていれば、その否定は「または」です。次に、対偶の仮定が「または」になったとき、答案が両方の枝を書いているかを確かめます。片方の枝だけで「同じ計算」と書くなら、同じになる理由を一文添えます。最後に、直接法で二、三行に収まる命題ではないかを振り返ります。p が素数で p が ab を割り切る場面のように、互いに素と一次結合で片付く命題は、対偶より直接法が短くなります。

答案の一行目で立ち止まったら、否定の一行を書き直すところから始めてください。仮定と結論のどちらを否定したのかがはっきりすれば、その後の場合分けは自然に決まります。対偶の一行目を直すことが、整除の答案を組み直す最初の一歩です。