こんにちは、ウチダです。
いつもお読みいただきましてありがとうございます。
さて、整数の性質で発展内容として学ぶ「合同式（mod）」ですが、こいつがメチャクチャ便利なやつなのです！
この例題のように、とんでもない桁の数を扱うときに合同式（mod）を知っていれば、
$$5^{100}≡(-1)^{100}=1 \pmod{6}$$
と式変形し、余りは $1$ と簡単に求めることができます。
[ふきだし set=”悩む男性”]おお～。これだけ見てもすごく便利なのは伝わってくるね。でも…なんでそんなに簡単に求められるの？[/ふきだし]
[ふきだし set=”悩む女性”]まずは合同式の基本をしっかりと固めてから、練習問題をたくさん解きたいわ。[/ふきだし]
よって本記事では、合同式（mod）の意味から、合同式（mod）の基本問題 $3$ 選の解き方まで
- 東北大学理学部数学科卒業
- 実用数学技能検定１級保持
- 高校教員→塾の教室長の経験あり
の僕がわかりやすく解説します。
合同式（mod）とは？【商を無視して余りに注目しよう】
合同式（mod）を学ぶ上で必ず押さえておきたいポイントは
- 合同式とは、商を考えない式。
- 合同式の使い方は、「余りを求める」「一の位の数を求める」「倍数であることを証明する」この $3$ つが基本。
以上です。
順に解説していきます。
合同式（mod）の記号の読み方など
まず、「”mod”とは何ぞや」という疑問についてです。
これは「modulo（モジュロ）」と呼ばれていて、日本語に直すと「剰余演算」という意味があります。
[ふきだし set=”ウチダ”]つまり、「これから書く式は、余りについては同じことを言ってますよ～。」と示す記号だと思ってください。[/ふきだし]
また、「＝（イコール）」は「両辺の値が等しい」という意味の記号ですから、それを使うと混乱してしまいますよね。
よって、「 $≡$（合同）」という記号を使うことにします。
<補足>これは中学校で習う「図形の合同」で用いた記号と同じものです。
ここまでの話を、例題を通して整理します。
先ほどの例題で
$$5^{100}≡(-1)^{100}=1 \pmod{6}$$
と式変形して解きました。
こうしてできた式の読み方は色々あって
- $5^{100}$ 合同 $1$ モッド $6$
- $5^{100}$ 合同 $1$ モジュロ $6$
- $5^{100}$ は法（ほう）を $6$ として $1$ と合同である。
[ふきだし set=”悩む男性”]…ん？急に出てきた「法（ほう）」ってなんですか？[/ふきだし]
[ふきだし set=”ウチダ”]法律って国家の”基準”ですよね。よって、法（ほう）には「基準」という意味があります。日本語で式を説明できないと不便なので、日常で使う言葉を数学の用語として定義しました～、ということです。[/ふきだし]
最初は用語を覚えるのに苦労すると思いますが、次第に慣れていきますので、今はそんなに気にしなくてOKですよ！
合同式（mod）に成り立つ性質５つ
さて、冒頭で合同式（mod）は「商を考えない式」であると伝えました。
ふつうの割り算（除法）であれば、「商と余り」の $2$ つの要素を同時に考えなくてはいけませんでした。
しかし、合同式（mod）を使えば、商を無視して余りのみに注目することができます。
[ふきだし set=”ウチダ”]整数問題を解く上で、「商の情報はどうでもいい」ということはよくあるんですよ。だから合同式（mod）はめちゃくちゃ便利なんです。[/ふきだし]
ではここで、合同式（mod）に成り立つ性質 $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$（合同式のべき乗）
[ふきだし set=”悩む女性”]これをいきなり覚えなきゃいけないんですか？[/ふきだし]
[ふきだし set=”ウチダ”]そんなことはありません！使っていくうちに自然と理解できていきます。ただし、性質４には注意が必要です。[/ふきだし]
記号に慣れていないうちは「何これ」と思うかもしれません。
ただ、
- 加法
- 減法
- 乗法（べき乗）
- 除法
という $4$ つの演算のうち、除法以外の $3$ つは、「＝（イコール）」のときと全く同じ性質が成り立ち、除法のみ「互いに素」という条件が付く、という意味ですので、そんなに身構える必要はありません。
この $5$ つの性質については、必要とあらば適宜補足していきますので、予備知識はここまでにして早速問題を解いていきますか！
合同式（mod）の基本問題３選で慣れよう
ではここから、合同式（mod）を実際に使っていくことで、合同式と友達になっていただきます。
具体的には
- 余りを求める問題【 $2$ 問】
- 一の位の数を求める問題
- 倍数であることの証明問題
以上 $3$ 種類の問題を解いていきましょう。
余りを求める問題
(1) $14$
(2) $14^2$
(3) $14^{51}$
冒頭の例題でも見た通り、余りを求める問題で大活躍します。
だって、合同式（mod）は「商を無視して余りのみに注目する式」ですもんね＾＾
先ほどまとめた性質を上手く使いながら解いていきましょう。
【解答】
(1) $10≡0 \pmod{5}$ であるから、性質２を用いると、$14-0≡14-10=4 \pmod{5}$
したがって、$14$ を $5$ で割った余りは $4$ である。
(2) $2$ 乗を掛け算の形で表すと、性質３より、$14^2=14×14≡4×4=16 \pmod{5}$
ここで、$16=15+1≡1 \pmod{5}$ より、$14^2≡1 \pmod{5}$
したがって、$14^2$ を $5$ で割った余りは $1$ である。
(3) 性質５を用いて、$14^{51}≡(-1)^{51}=-1 \pmod{5}$
また、$-1=4-5≡4 \pmod{5}$ なので、$14^{51}≡4 \pmod{5}$
したがって、$14^{51}$ を $5$ で割った余りは $4$ である。
(解答終了)
初めての問題なので、解答は丁寧すぎるぐらいに書いてみました。
(1)と(2)では普通に割り算した方が速いかもしれませんが、(3)は合同式を使わないと厳しいですよね。
[ふきだし set=”ウチダ”]ここで気づいてほしいのは、性質５を使うとなんでこんなに簡単になるのか、ということです。[/ふきだし]
正解を発表すると、$1$ の ～ 乗や $-1$ の ～ 乗は簡単に求めることができるからですね。
余りがマイナスって、少し変な感じがしますが、最後に性質１や性質２を使って正の数に戻してやれば、何の問題もありません。
余りを求める問題（少し応用）
今の基本を活かして、$1$ 問だけ応用問題を解いてみます。
これを(3)のように解こうとすると、$4^{33}≡(-3)^{33} \pmod{7}$ なので、ここで計算が止まってしまいます。
よって、少し工夫して考える必要があるのです。
【解答】
$4^{33}=(4^3)^{11}=64^{11}$ である。
ここで、$64=63+1≡1 \pmod{7}$ を利用すると、
$4^{33}=64^{11}≡1^{11}=1 \pmod{7}$
となるから、余りは $1$ だと簡単にわかる。
(解答終了)
合同式の素晴らしさが感じられてきましたね！
重要なことなので、ここに記しておきます。
一の位の数を求める問題
一見、合同式とは何ら関りはないようにも思えますが、「一の位の数とは何か」よ～く考えてると…
↓↓↓（正解発表）
$10$ で割ったときの余り、つまり mod $10$ を考えればいいことになりませんか？
よって、合同式（mod）を使った解答は以下のようになります。
【解答】
$3^{100}=(3^2)^{50}=9^{50}$ である。
ここで、$9^{50}≡(-1)^{50}=1 \pmod{10}$ より、
$3^{100}≡1 \pmod{10}$ であることがわかる。
したがって、$3^{100}$ の一の位の数は $1$ である。
(解答終了)
こういう問題はよく中学受験などでも出題されやすい問題です。
これを初等的に解こうとすると、$3^1$，$3^2$，…の一の位の数だけを並べていって
$$3 \ , \ 9 \ , \ 7 \ , \ 1 \ , \ 3 \ , \ …$$
と $4$ つごとに規則的に並んでいることを発見し、この $100$ 番目なので、答えは $1$ となります。
[ふきだし set=”ウチダ”]この初等的な解答を、数式を用いて理論的かつ簡潔に記したものが「合同式（mod）をつかった解答」になるわけですね。[/ふきだし]
倍数であることの証明問題
さて、合同式（mod）は倍数であることの証明問題においても、非常に有用です。
この問題においても、合同式（mod）基準で解釈してみましょう。
すると…
↓↓↓（正解発表）
$7$ で割ったときの余りが $0$、つまり $2^{n+1}+3^{2n-1}≡0 \pmod{7}$ を示せばよいことがわかります。
それでは解答です。
【解答】
$3^{2n-1}=3^{2(n-1)+1}=3×9^{n-1}$ であり、また $9=2 \pmod{7}$ であることを利用すると、
したがって、すべての自然数 $n$ に対して、$2^{n+1}+3^{2n-1}$ は $7$ の倍数である。
(解答終了)
「 $2^{n-1}$ でくくってみよう」という発想ができるかどうか。
ここが問題が解けるかどうかの分かれ目ですね。
[ふきだし set=”ウチダ”]数学Ⅱ「二項定理」や数学Ｂ「数学的帰納法」を使えば、もっと機械的に証明することも可能ですが、合同式（mod）を使った解答が一番簡潔で美しいです。[/ふきだし]
合同式（mod）のさらなる応用や入試問題はこちらの記事へ
いかがだったでしょうか。
本記事の要点を改めてまとめておきます。
- 合同式とは、商を無視し余りのみに注目している式のこと。
- 合同式の基本的な使い方として「余りを求める」「一の位の数を求める」「倍数であることを証明する」の $3$ つを押さえよう！
- 余り → $1^n$ もしくは $(-1)^n$ を作り出す！
- 一の位の数 → つまり mod $10$ を考えればOK！
- 倍数の証明 → 余りが $0$ を合同式で示す！
基本でも結構お腹いっぱいの内容です。
まあ、もともと発展内容の分野ですからね～。
これ以上の応用問題（不定方程式を解く問題・京大入試問題）は以下の記事で詳しく解説しておりますので、こちらもぜひあわせてご覧ください。
「整数の性質」全 25 記事をまとめました。こちらから次の記事をCHECK!!
以上で終わりです。
コメントを残す