合同式(mod)を応用して京大入試問題を解こう【不定方程式の問題も解説】

こんにちは、ウチダショウマです。

いつもお読みいただきましてありがとうございます。

突然ですが、合同式(mod)の基本はマスターできましたか?

たとえば合同式(mod)を使うと、$7^{96}$ を $5$ で割った余りを

$$7^{96}=49^{48}≡(-1)^{48}=1 \pmod{5}$$

と簡潔に求めることができます。

「合同式(mod)の基本が怪しい…」という方は、先にこちらの記事から読み進めることをオススメします。

あわせて読みたい
合同式の基本的な使い方3選とは【まずは練習問題でmodに慣れよう】
合同式の基本的な使い方3選とは【まずは練習問題でmodに慣れよう】合同式(mod)の意味が分からない?本記事では、合同式(mod)の基本的な部分についてまとめました。具体的には、「modとは何か」「合同式に成り立つ性質5つ」「余りを求める問題」「一の位の数を求める問題」「倍数であることの証明問題」を解説します。

さて、今日は続きのお話。

合同式(mod)は発展内容なのでセンター試験には登場しませんし、入試でも合同式の問題は出てきません。

しかし、合同式を使った方がはるかに解きやすい問題は数多くあります。

数学太郎のアイコン画像数学太郎
へ~。合同式をどうやって応用するのか、詳しく知りたいな~。
数学花子のアイコン画像数学花子
京都大学さんが作られた、超良問の入試問題があると聞きました。わかりやすく解説お願いします!

よって本記事では、基本の記事では扱いきれなかった、合同式のさらなる応用方法 $2$ 選(一次不定方程式・京大入試問題)について

  • 東北大学理学部数学科卒業
  • 教員採用試験に1発合格 → 高校教諭経験アリ

の僕がわかりやすく解説します。

スポンサーリンク
スポンサーリンク
目次

合同式(mod)を一次不定方程式に応用しよう【互除法は使いません】

なんと、合同式(mod)を応用することで…

一次不定方程式を互除法なしで解く

こんな夢みたいなことができるようになってしまいます。

ウチダのアイコン画像ウチダ
互除法がわかりづらいがために、一次不定方程式に苦手意識を持つ方は多いかと思います。互除法の原理については「ユークリッドの互除法の原理をわかりやすく解説!【互除法の活用2選アリ】」の記事をご覧ください。

さて、合同式(mod)を一次不定方程式に応用する上で、まず押さえたい知識がありますので、そちらから順に解説していきます。

合同方程式の解き方

それが「合同方程式」と呼ばれるものです。

例題. 次の合同方程式を解きなさい。
(1) $x-2≡4 \pmod{5}$
(2) $4x≡8 \pmod{7}$

合同式が含まれている方程式だから、合同方程式です。

まずはこれを解けるようになりましょう。

【解答】

(1) 合同式の性質1より、$x-2+2≡4+2 \pmod{5}$

よって、$x≡6 \pmod{5}$

ここで、$6≡1 \pmod{5}$ より、$x≡1 \pmod{5}$

(2) $4$ と $7$ は互いに素であるので、合同式の性質4より、$4x÷4≡8÷4 \pmod{7}$

よって、$x≡2 \pmod{7}$

(解答終了)

いきなり出てきた性質1とか性質4ってなに?と感じたと思います。

これは、冒頭に紹介した記事でも記した、合同式の四則演算に関して成り立つ性質 $5$ つのことです。

【合同式(mod)に成り立つ性質 $5$ つ】
今、法を $p$ として、$a≡b \ , \ c≡d$ とする。(ここでは $\pmod{p}$ を省略します。)
このとき、以下の性質が成り立つ。
1.$a+c≡b+d$(合同式の加法)
2.$a-c≡b-d$(合同式の減法)
3.$ac≡bd$(合同式の乗法)
4.$ab≡ac$ で、a と p が互いに素であるとき、$b≡c$(合同式の除法)
5.$a^n≡b^n$(合同式のべき乗)

やっと性質4を使う時が来ましたので、ここで一度証明しておきたいと思います。

合同式の除法の性質

【除法の性質の証明】

$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}$$

という間違った式を導いてしまいます。

ウチダのアイコン画像ウチダ
合同式は、除法のみ「互いに素」に注意しなくてはいけないということですね。互いに素については「互いに素な自然数とは?【応用例7選もわかりやすく解説します】」の記事で詳しく解説してます。

一次不定方程式を解いてみよう【合同方程式】

ではいよいよ、一次不定方程式に合同式(mod)を応用してみましょう。

問題. 方程式 $57x+13y=14$ の整数解をすべて求めなさい。

解答の最初で、いきなりテクニカルな式変形をするので注目です。

【解答】

$57x+13y=14$より、$57x+13y≡14 \pmod{13}$ と式変形できる。

一次不定方程式を合同式(mod)を応用して解いてみよう

また $13y≡0 \pmod{13}$ より、$57x≡14 \pmod{13}$ となる。

ここで、

  • $57≡5 \pmod{13}$ より、$5x≡14 \pmod{13}$
  • $14≡40 \pmod{13}$ より、$5x≡40 \pmod{13}$

$5$ と法 $13$ は互いに素なので、両辺を $5$ で割ることができる。

よって、$$x≡8 \pmod{13}$$

が導けたので、$x=13k+8$( $k$ はある整数)と表すことができた。

問題の方程式に代入すると、

\begin{align}13y&=-57x+14\\&=-57(13k+8)+14\\&=13×(-57k)+14-57×8\\&=13×(-57k)-442\\&=13×(-57k)-13×34\end{align}

両辺を $13$ で割ると、$y=-57k-34$

したがって、求める整数解は、$$x=13k+8,y=-57k-34 \ ( \ k \ はある整数)$$

(解答終了)

「=(イコール)」の意味は”値”が等しい、「≡(合同)」の意味は”余り”が等しいなので、命題「方程式が成り立つならば合同方程式が成り立つ」は真です。

また、$y$ の係数を法とする理由は、$13y≡0 \pmod{13}$ より

$$57x≡14 \pmod{13}$$

と、$x$ のみの合同方程式が作れるからです。

ウチダのアイコン画像ウチダ
あとは合同方程式の解き方を応用すればOKですね!ここから $x≡~ \pmod{13}$ の形にする式変形は、少し慣れが必要ですので、一次不定方程式の問題で練習するといいでしょう。

一次不定方程式については「一次不定方程式の解き方とは?【応用問題3選もわかりやすく解説します】」の記事で解説しておりますので、ぜひあわせてご覧ください。

スポンサーリンク

合同式(mod)を京大入試問題に応用しよう【超良問】

では次に、京都大学の入試問題にチャレンジしてみましょうか!

問題. 素数 $p$,$q$ を用いて、$p^q+q^p$ と表される素数をすべて求めなさい。
※2016年度京都大学入試理系第2問より出題

さすがに一筋縄ではいきませんので、

  • Step1 … 実験
  • Step2 … 候補を絞る
  • Step3 … 共通点を予想【最重要パート】
  • Step4 … 合同式(mod)を使って証明

の $4$ ステップに分けて解説していきます。

ウチダのアイコン画像ウチダ
超良問なので、自分で解かずして解説だけ読むのはあまりにももったいないです。ぜひStep $1$ を読んだら、$5$ 分だけでもいいので立ち止まって考えてみてほしいと思います♪

Step1.実験

「素数」としか条件が付けられていないため、あまりにも抽象的です。

よって、いろいろ実験してみましょう。

① $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$ なのでOK!

③ $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$ 以外が見つからないため、ここで一旦ストップ。

次は、ちょっと理論的に考えてみます。

Step2.候補を絞る

Step1の実験において

⑤ $p=3$,$q=5$

実は、この場合は実験する必要がありませんでした。

なぜなら、$p=奇数$,$q=奇数$ であれば、

\begin{align}p^q+q^p&=奇数^{奇数}+奇数^{奇数}\\&=奇数+奇数\\&=偶数\end{align}

となってしまい、偶数かつ素数である自然数は $2$ のみなので、$p^q+q^p$ は合成数となります。

つまり、ここから…

解の候補は $p=2$,$q=奇数の素数$ しかない!

ということがわかります。

ウチダのアイコン画像ウチダ
$p=奇数の素数$,$q=2$ という場合は考えません。なぜなら、$p^q+q^p$ は $p$ と $q$ を入れ替えても同じ式となる、つまり対称式なので、$p<q$ としても一般性を失わないからです。

さて、ここまで自力で辿り着く方は結構多いです。

次のStep3を自分で発見できれば、この問題は解けたようなものですよ。

ぜひここで一度、Step1の実験結果を思い出してみてください。

Step3.共通点を予想【最重要パート】

さて、このStep3が最重要パートです。

本当に、もう解説を見ちゃっていいんですか…?

↓↓↓

それでは解説です。^^

Step1の実験において、

  • ③ $p=2$,$q=5$
    • $2^5+5^2=57=3×19$
  • ④ $p=2$,$q=7$
    • $2^7+7^2=177=3×59$

であったことを思い出すと…

$q≠3$ であれば、$p^q+q^p$ は $3$ の倍数となるのでは???

このように予想することができます。

この予想を確信に変えるために、もう一つだけ実験してみましょうか。

⑥ $p=2$,$q=11$

$p^q+q^p=2^{11}+11^2=2169=3×723$

数学は抽象的な学問ですが、このように実験から予想できるという点では、理科みたいなものでもあります。

実験の重要性がわかりましたね。

では、最後の仕上げ。

合同式(mod)を使って、この予想を証明していきましょう!

Step4.合同式(mod)を使って証明

予想. $q$ が $5$ 以上の素数ならば、$2^q+q^2$ は $3$ の倍数である。

つまり、$2^q+q^2≡0 \pmod{3}$ を示すことと同値ですね。

【解答】

$2≡-1 \pmod{3}$ であり、また $q$ が奇数であることから、性質5を用いて、$$2^q≡(-1)^q=-1 \pmod{3}$$

よって、

\begin{align}2^q+q^2&≡-1+q^2\\&=q^2-1\\&=(q+1)(q-1) \pmod{3}\end{align}

ここで、$q$ は $3$ の倍数ではないため、必ず $q+1$,$q-1$ のどちらかは $3$ の倍数となる。

したがって、$(q+1)(q-1)≡0 \pmod{3}$ より、$2^q+q^2$ は $3$ の倍数となることが示せた。

(証明終了)

因数分解して $q+1$,$q-1$ に着目するところは、発想力を必要としますね。

ただ、他の部分は基本的な式変形のみです。

ウチダのアイコン画像ウチダ
「京大の入試問題は美しい」と言われる所以はここにありますね。ぜひ京大の問題をじっくり解いて、柔軟な発想を養っていきましょうね^^

合同式(mod)をしっかりマスターしたいと思ったら…?

本記事の要点を改めてまとめます。

  1. 性質4を使えば「一次不定方程式」が互除法なしで解けます。
  2. 性質5は重宝します。京都大学の入試問題だって解けちゃいます。
  3. もちろんセンター試験など入試では出題されません。しかし、積極的に使っていきましょう!

「合同式(mod)の良問をたくさん解いてしっかり力を付けたいな~」という方は、以下の書籍がオススメです。

マスターオブ整数」がなぜ優れているか、列挙すると

  • 意外と少ないページ数。
  • 整数問題のみに特化。
  • それでいて、基礎問から発展まで良問ぞろい。
  • めちゃくちゃ丁寧な解説。

こんなところでしょうか。

とにかく、「整数問題の力を付けたい」という方は、この $1$ 冊をやり込めば間違いないです。

ぜひ使ってみてください^^

「整数の性質」全 25 記事をまとめました。こちらから次の記事をCHECK!!

あわせて読みたい
整数の性質とは?【高校数学Aの解説記事総まとめ25選】
整数の性質とは?【高校数学Aの解説記事総まとめ25選】「整数の性質」の総まとめ記事です。本記事では、整数の性質の解説記事全25個をまとめています。「整数の性質をしっかりマスターしたい」「整数の性質を自分のものにしたい」という方は必見です。

以上で終わりです。

遊ぶ数学公式LINEやってます!

遊ぶ数学管理人「ウチダショウマ」に数学を直接教わることができるオンライン家庭教師サービス”Play MATH”を開始しました。

その他にも

・ウチダショウマとお話がしたい
・勉強に関する悩みを相談したい

などでもOKですので、ぜひ気軽にご連絡ください。

↓友達追加はこちらから↓

友だち追加

スポンサーリンク

コメント

コメントする

目次
閉じる