MENU
カテゴリー
おすすめプログラミングスクール紹介中! 一覧はこちらから

合同式の基本的な使い方3選とは【まずは練習問題でmodに慣れよう】

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

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

さて、整数の性質で発展内容として学ぶ「合同式(mod)」ですが、こいつがメチャクチャ便利なやつなのです!

例題. $5^{100}$ を $6$ で割った余りを求めなさい。

この例題のように、とんでもない桁の数を扱うときに合同式(mod)を知っていれば、

$$5^{100}≡(-1)^{100}=1 \pmod{6}$$

と式変形し、余りは $1$ と簡単に求めることができます。

数学太郎
おお~。これだけ見てもすごく便利なのは伝わってくるね。でも…なんでそんなに簡単に求められるの?
数学花子
まずは合同式の基本をしっかりと固めてから、練習問題をたくさん解きたいわ。

よって本記事では、合同式(mod)の意味から、合同式(mod)の基本問題 $3$ 選の解き方まで

  • 東北大学理学部数学科卒業
  • 実用数学技能検定1級保持
  • 高校教員→塾の教室長の経験あり

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

スポンサーリンク
目次

合同式(mod)とは?【商を無視して余りに注目しよう】

合同式(mod)を学ぶ上で必ず押さえておきたいポイントは

  • 合同式とは、商を考えない式。
  • 合同式の使い方は、「余りを求める」「一の位の数を求める」「倍数であることを証明する」この $3$ つが基本。

以上です。

順に解説していきます。

合同式(mod)の記号の読み方など

まず、「”mod”とは何ぞや」という疑問についてです。

これは「modulo(モジュロ)」と呼ばれていて、日本語に直すと「剰余演算」という意味があります。

ウチダ
つまり、「これから書く式は、余りについては同じことを言ってますよ~。」と示す記号だと思ってください。

また、「=(イコール)」は「両辺の値が等しい」という意味の記号ですから、それを使うと混乱してしまいますよね。

よって、「 $≡$(合同)」という記号を使うことにします。
<補足>これは中学校で習う「図形の合同」で用いた記号と同じものです。

ここまでの話を、例題を通して整理します。

例題. $5^{100}$ を $6$ で割った余りを求めなさい。

先ほどの例題で

$$5^{100}≡(-1)^{100}=1 \pmod{6}$$

と式変形して解きました。

こうしてできた式の読み方は色々あって

  • $5^{100}$ 合同 $1$ モッド $6$
  • $5^{100}$ 合同 $1$ モジュロ $6$
  • $5^{100}$ は法(ほう)を $6$ として $1$ と合同である。
数学太郎
…ん?急に出てきた「法(ほう)」ってなんですか?
ウチダ
法律って国家の”基準”ですよね。よって、法(ほう)には「基準」という意味があります。日本語で式を説明できないと不便なので、日常で使う言葉を数学の用語として定義しました~、ということです。

最初は用語を覚えるのに苦労すると思いますが、次第に慣れていきますので、今はそんなに気にしなくてOKですよ!

合同式(mod)に成り立つ性質5つ

さて、冒頭で合同式(mod)は「商を考えない式」であると伝えました。

ふつうの割り算(除法)であれば、「商と余り」の $2$ つの要素を同時に考えなくてはいけませんでした。

しかし、合同式(mod)を使えば、商を無視して余りのみに注目することができます。

ウチダ
整数問題を解く上で、「商の情報はどうでもいい」ということはよくあるんですよ。だから合同式(mod)はめちゃくちゃ便利なんです。

ではここで、合同式(mod)に成り立つ性質 $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には注意が必要です。

記号に慣れていないうちは「何これ」と思うかもしれません。

ただ、

  • 加法
  • 減法
  • 乗法(べき乗)
  • 除法

という $4$ つの演算のうち、除法以外の $3$ つは、「=(イコール)」のときと全く同じ性質が成り立ち、除法のみ「互いに素」という条件が付く、という意味ですので、そんなに身構える必要はありません。

この $5$ つの性質については、必要とあらば適宜補足していきますので、予備知識はここまでにして早速問題を解いていきますか!

スポンサーリンク

合同式(mod)の基本問題3選で慣れよう

ではここから、合同式(mod)を実際に使っていくことで、合同式と友達になっていただきます。

具体的には

  • 余りを求める問題【 $2$ 問】
  • 一の位の数を求める問題
  • 倍数であることの証明問題

以上 $3$ 種類の問題を解いていきましょう。

余りを求める問題

問題. 次の数を $5$ で割った余りを求めなさい。
(1) $14$
(2) $14^2$
(3) $14^{51}$

冒頭の例題でも見た通り、余りを求める問題で大活躍します。

だって、合同式(mod)は「商を無視して余りのみに注目する式」ですもんね^^

先ほどまとめた性質を上手く使いながら解いていきましょう。

【解答】

(1) $10≡0 \pmod{5}$ であるから、性質2を用いると、$14-0≡14-10=4 \pmod{5}$

したがって、$14$ を $5$ で割った余りは $4$ である。

(2) $2$ 乗を掛け算の形で表すと、性質3より、$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) 性質5を用いて、$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)は合同式を使わないと厳しいですよね。

ウチダ
ここで気づいてほしいのは、性質5を使うとなんでこんなに簡単になるのか、ということです。

正解を発表すると、$1$ の ~ 乗や $-1$ の ~ 乗は簡単に求めることができるからですね。

余りがマイナスって、少し変な感じがしますが、最後に性質1や性質2を使って正の数に戻してやれば、何の問題もありません。

余りを求める問題(少し応用)

今の基本を活かして、$1$ 問だけ応用問題を解いてみます。

応用問題. $4^{33}$ を $7$ で割った余りを求めよ。

これを(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$ だと簡単にわかる。

(解答終了)

合同式の素晴らしさが感じられてきましたね!

余りを求める問題は「 $1$ もしくは $-1$ の $n$ 乗」という形を作り出せれば勝ち

重要なことなので、ここに記しておきます。

一の位の数を求める問題

問題. $3^{100}$ の一の位の数を求めなさい。

一見、合同式とは何ら関りはないようにも思えますが、「一の位の数とは何か」よ~く考えてると…

↓↓↓(正解発表)

$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$ となります。

ウチダ
この初等的な解答を、数式を用いて理論的かつ簡潔に記したものが「合同式(mod)をつかった解答」になるわけですね。

倍数であることの証明問題

さて、合同式(mod)は倍数であることの証明問題においても、非常に有用です。

問題. すべての自然数 $n$ に対して、$2^{n+1}+3^{2n-1}$ は $7$ の倍数であることを示しなさい。

この問題においても、合同式(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}$ であることを利用すると、

\begin{align}2^{n+1}+3^{2n-1}&≡2^{(n-1)+2}+3^{2(n-1)+1}\\&=4×2^{n-1}+3×9^{n-1}\\&≡4×2^{n-1}+3×2^{n-1}\\&=(4+3)×2^{n-1}\\&=7×2^{n-1}\\&≡0 \pmod{7}\end{align}

したがって、すべての自然数 $n$ に対して、$2^{n+1}+3^{2n-1}$ は $7$ の倍数である。

(解答終了)

$2^{n-1}$ でくくってみよう」という発想ができるかどうか。

ここが問題が解けるかどうかの分かれ目ですね。

ウチダ
数学Ⅱ「二項定理」や数学B「数学的帰納法」を使えば、もっと機械的に証明することも可能ですが、合同式(mod)を使った解答が一番簡潔で美しいです。

合同式(mod)のさらなる応用や入試問題はこちらの記事へ

いかがだったでしょうか。

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

  • 合同式とは、商を無視し余りのみに注目している式のこと。
  • 合同式の基本的な使い方として「余りを求める」「一の位の数を求める」「倍数であることを証明する」の $3$ つを押さえよう!
    • 余り → $1^n$ もしくは $(-1)^n$ を作り出す!
    • 一の位の数 → つまり mod $10$ を考えればOK!
    • 倍数の証明 → 余りが $0$ を合同式で示す!

基本でも結構お腹いっぱいの内容です。

まあ、もともと発展内容の分野ですからね~。

これ以上の応用問題(不定方程式を解く問題・京大入試問題)は以下の記事で詳しく解説しておりますので、こちらもぜひあわせてご覧ください。

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

以上で終わりです。

よかったらシェアしてね!
  • URLをコピーしました!
  • URLをコピーしました!
スポンサーリンク

コメントを残す

コメントする

CAPTCHA


目次