こんにちは、ウチダです。
いつもお読みいただきましてありがとうございます。
突然ですが、合同式（mod）の基本はマスターできましたか？
たとえば合同式（mod）を使うと、$7^{96}$ を $5$ で割った余りを
$$7^{96}=49^{48}≡(-1)^{48}=1 \pmod{5}$$
と簡潔に求めることができます。
「合同式（mod）の基本が怪しい…」という方は、先にこちらの記事から読み進めることをオススメします。
さて、今日は続きのお話。
合同式（mod）は発展内容なのでセンター試験には登場しませんし、入試でも合同式の問題は出てきません。
しかし、合同式を使った方がはるかに解きやすい問題は数多くあります。
数学太郎
数学花子よって本記事では、基本の記事では扱いきれなかった、合同式のさらなる応用方法 $2$ 選（一次不定方程式・京大入試問題）について
- 東北大学理学部数学科卒業
- 実用数学技能検定１級保持
- 高校教員→塾の教室長の経験あり
の僕がわかりやすく解説します。
合同式（mod）を一次不定方程式に応用しよう【互除法は使いません】
なんと、合同式（mod）を応用することで…
こんな夢みたいなことができるようになってしまいます。
ウチダさて、合同式（mod）を一次不定方程式に応用する上で、まず押さえたい知識がありますので、そちらから順に解説していきます。
合同方程式の解き方
それが「合同方程式」と呼ばれるものです。
(1) $x-2≡4 \pmod{5}$
(2) $4x≡8 \pmod{7}$
合同式が含まれている方程式だから、合同方程式です。
まずはこれを解けるようになりましょう。
いきなり出てきた性質１とか性質４ってなに？と感じたと思います。
これは、冒頭に紹介した記事でも記した、合同式の四則演算に関して成り立つ性質 $5$ つのことです。
今、法を $p$ として、$a≡b \ , \ c≡d$ とする。(ここでは $\pmod{p}$ を省略します。)
このとき、以下の性質が成り立つ。
１．$a+c≡b+d$（合同式の加法）
２．$a-c≡b-d$（合同式の減法）
３．$ac≡bd$（合同式の乗法）
４．$ab≡ac$ で、a と p が互いに素であるとき、$b≡c$（合同式の除法）
５．$a^n≡b^n$（合同式のべき乗）
やっと性質４を使う時が来ましたので、ここで一度証明しておきたいと思います。
合同式の除法の性質
【除法の性質の証明】
$ab≡ac$ より、$ab-ac≡0$ なので、
$$a(b-c)≡0 \pmod{p}$$
となる。
ここから、$a$ もしくは $b-c$ が $p$ の倍数であることがわかる。
ここで、$a$ と $p$ は互いに素であると仮定すると、$b-c$ が $p$ の倍数となるから、$b-c≡0 \pmod{p}$ が言える。
したがって、$$b≡c \pmod{p}$$
(証明終了)
$a$ と $p$ が互いに素でない場合を考えてみると、たとえば $6≡2 \pmod{4}$
の両辺を $2$ で割って$$3≡1 \pmod{4}$$
という間違った式を導いてしまいます。
ウチダ一次不定方程式を解いてみよう【合同方程式】
ではいよいよ、一次不定方程式に合同式（mod）を応用してみましょう。
解答の最初で、いきなりテクニカルな式変形をするので注目です。
「＝（イコール）」の意味は”値”が等しい、「≡（合同）」の意味は”余り”が等しいなので、命題「方程式が成り立つならば合同方程式が成り立つ」は真です。
また、$y$ の係数を法とする理由は、$13y≡0 \pmod{13}$ より
$$57x≡14 \pmod{13}$$
と、$x$ のみの合同方程式が作れるからです。
ウチダ一次不定方程式についてはこちらの記事で詳しく解説しておりますので、ぜひあわせてご覧ください。
合同式（mod）を京大入試問題に応用しよう【超良問】
では次に、京都大学の入試問題にチャレンジしてみましょうか！
※2016年度京都大学入試理系第２問より出題
さすがに一筋縄ではいきませんので、
- Step１ … 実験
- Step２ … 候補を絞る
- Step３ … 共通点を予想【最重要パート】
- Step４ … 合同式（mod）を使って証明
の $4$ ステップに分けて解説していきます。
ウチダStep１．実験
「素数」としか条件が付けられていないため、あまりにも抽象的です。
よって、いろいろ実験してみましょう。
① $p=2$，$q=2$ を代入
$p^q+q^p=2^2+2^2=8$ なのでダメ。
② $p=2$，$q=3$ を代入
$p^q+q^p=2^3+3^2=17$ なのでＯＫ！
③ $p=2$，$q=5$ を代入
$p^q+q^p=2^5+5^2=57$ なのでダメ。
④ $p=2$，$q=7$ を代入
$p^q+q^p=2^7+7^2=177$ なのでダメ。
⑤ $p=3$，$q=5$ を代入
$p^q+q^p=3^5+5^3=368$ なのでダメ。
解 $p=2$，$q=3$ が一つ導けました。
少しだけでも、とりあえず実験してみることで解答の道すじが見えてきます。
さて、$p=2$，$q=3$ 以外が見つからないため、ここで一旦ストップ。
次は、ちょっと理論的に考えてみます。
Step２．候補を絞る
Step１の実験において
⑤ $p=3$，$q=5$
実は、この場合は実験する必要がありませんでした。
なぜなら、$p=奇数$，$q=奇数$ であれば、
となってしまい、偶数かつ素数である自然数は $2$ のみなので、$p^q+q^p$ は合成数となります。
つまり、ここから…
ということがわかります。
ウチダさて、ここまで自力で辿り着く方は結構多いです。
次のStep３を自分で発見できれば、この問題は解けたようなものですよ。
ぜひここで一度、Step１の実験結果を思い出してみてください。
Step３．共通点を予想【最重要パート】
さて、このStep３が最重要パートです。
本当に、もう解説を見ちゃっていいんですか…？
↓↓↓
それでは解説です。＾＾
Step１の実験において、
- ③ $p=2$，$q=5$
- $2^5+5^2=57=3×19$
- ④ $p=2$，$q=7$
- $2^7+7^2=177=3×59$
であったことを思い出すと…
このように予想することができます。
この予想を確信に変えるために、もう一つだけ実験してみましょうか。
⑥ $p=2$，$q=11$
$p^q+q^p=2^{11}+11^2=2169=3×723$
数学は抽象的な学問ですが、このように実験から予想できるという点では、理科みたいなものでもあります。
実験の重要性がわかりましたね。
では、最後の仕上げ。
合同式（mod）を使って、この予想を証明していきましょう！
Step４．合同式（mod）を使って証明
つまり、$2^q+q^2≡0 \pmod{3}$ を示すことと同値ですね。
【解答】
$2≡-1 \pmod{3}$ であり、また $q$ が奇数であることから、性質５を用いて、$$2^q≡(-1)^q=-1 \pmod{3}$$
よって、
ここで、$q$ は $3$ の倍数ではないため、必ず $q+1$，$q-1$ のどちらかは $3$ の倍数となる。
したがって、$(q+1)(q-1)≡0 \pmod{3}$ より、$2^q+q^2$ は $3$ の倍数となることが示せた。
(証明終了)
因数分解して $q+1$，$q-1$ に着目するところは、発想力を必要としますね。
ただ、他の部分は基本的な式変形のみです。
ウチダ合同式（mod）をしっかりマスターしたいと思ったら…？
本記事の要点を改めてまとめます。
- 性質４を使えば「一次不定方程式」が互除法なしで解けます。
- 性質５は重宝します。京都大学の入試問題だって解けちゃいます。
- もちろんセンター試験など入試では出題されません。しかし、積極的に使っていきましょう！
「合同式（mod）の良問をたくさん解いてしっかり力を付けたいな～」という方は、以下の書籍がオススメです。
「マスターオブ整数」がなぜ優れているか、列挙すると
- 意外と少ないページ数。
- 整数問題のみに特化。
- それでいて、基礎問から発展まで良問ぞろい。
- めちゃくちゃ丁寧な解説。
こんなところでしょうか。
とにかく、「整数問題の力を付けたい」という方は、この $1$ 冊をやり込めば間違いないです。
ぜひ使ってみてください＾＾
「整数の性質」全 25 記事をまとめました。こちらから次の記事をCHECK!!
以上で終わりです。
コメントを残す