2019年01月09日更新
合同式の内容と性質、および整数問題での効果的な使い方を詳しく解説
本記事では合同式の内容と性質、割り算を中心とした整数問題での使い方を詳しく解説していきます。合同式とは何なのか、\(mod\) の意味、そして「\(2^{100}\)を\(7\)で割ったときの余りを求めなさい」といった整数問題での使い方を身につけていきましょう。

はじめに

「合同式ってどんな式? 数字が合同とは? 合同式にはどんな性質があるの? 余りを求める整数問題で、合同式はどうやって使うの?」本記事ではこれらの質問にわかりやすく答えていきます。

合同式とは?

合同=割り算の余りが等しい

整数\(a\)、\(b\)を整数\(m\)で割ったときの余りが等しいとき、

 \(a\)と\(b\)は\(m\)を法として合同である

といいます。

合同の記号は図形と同じ

合同は数式で、

 \(a≡b(mod m)\)

と書き、読み方は、

 \(a\)合同\(b\)、モッド\(m\)

となります。


合同の記号は中学数学で習った図形の合同のものと同じです。

合同式の性質

加法・減法・乗法について成り立つ

合同式には次の3つの性質があります。

\(a≡b(mod m)\)、\(c≡d(mod m)\)のとき、次のことが成り立つ。

\(1 a+c≡b+d(mod m)\)

\(2 a-c≡b-d(mod m)\)

\(3 ac≡bd(mod m)\)

合同式の性質の証明

合同式の性質の証明は下記のとおりです。


【性質\(1\)の証明】

整数\(a\)、\(b\)を整数\(m\)で割ったときの商を順に\(p\)、\(q\)、余りをともに\(x\)、整数\(c\)、\(d\)を整数\(m\)で割ったときの商を順に\(r\)、\(s\)、余りをともに\(y\)とすると、

 \(a=mp+x\)

 \(b=mq+x\)

 \(c=mr+y\)

 \(d=ms+y\)

と表すことができる。

このとき、

 \(a+c=mp+x+mr+y\)

    \(=m(p+r)+x+y\)

 \(b+d=mq+x+ms+y\)

    \(=m(q+s)+x+y\)

よって、余りはともに\(x+y\)となり等しくなる。(終)


【性質\(2\)の証明】

整数\(a\)、\(b\)、\(c\)、\(d\)を上記のように定めると、

 \(a-c=mp+x-(mr+y)\) 

    \(=m(p-r)+x-y\)

 \(b-d=mq+x-(ms+y)\)

    \(=m(q-s)+x-y\)

よって、余りはともに\(x-y\)となり等しくなる。(終)


【性質\(3\)の証明】

整数\(a\)、\(b\)、\(c\)、\(d\)を上記のように定めると、

 \(ac=(mp+x)(mr+y)\)

   \(=m^{2}pr+mpy+mrx+xy\)

   \(=m(mpr+py+rx)+xy\)

 \(bd=(mq+x)(ms+y)\)

   \(=m^{2}qs+mqy+msx+xy\)

   \(=m(mqs+qy+sx)+xy\)

よって、余りはともに\(xy\)となり等しくなる。(終)


\(n\)乗でもOK

合同式の乗法の性質を利用したものとして、次のことが成り立ちます。


\(a≡b(mod m)\)のとき、

 \(a^{n}≡b^{n}(mod m)\)


定期試験や模試ではよく使うので、覚えておきましょう。

合同式の使い方

割り算の余りを\(1\)にする

それでは実際に、整数問題で合同式を使っていきます。

まずは割り算の余りを求める問題です。


【例題1】

\(2^{99}\)を\(7\)で割ったときの余りを求めなさい。


\(2^{10}\)であれば\(1024\)なので、筆算で余りを求めることも可能です。

しかし、\(2^{99}\)となると筆算では無理ですね。

ここで合同式の出番です。


【例題1の解答】

\(2^{99}=2^{3×33}=8^{33}\)で、\(8÷7\)の余りは\(1\)なので、

 \(2^{99}≡8^{33}≡1^{33}(mod 7)\)

よって、

 \(2^{99}≡1(mod 7)\)

ゆえに余りは\(1\)となる。(終)


割られる数に指数がついているときには、指数を掛け算に直して割られる数を分解します

今回は

 \(99=3×33\)

 \(99=9×11\)

の2つの組み合わせがあり、

 \(2^{99}=2^{3×33}=8^{33}\)

 \(2^{99}=2^{9×11}=512^{11}\)

と表すことができます。

\(8÷7\)または\(512÷7\)の余りを元に合同式を使います。

どちらも余りは\(1\)になりますが、\(8÷7\)としたほうが、計算は速いですよね。

割り算の余りで\(1\)を作るのがポイントです


それでは次に、冒頭の\(2^{100}\)の割り算に挑戦してみましょう。

割り算の余りで\(1\)を作れないときには?

【例題2】

\(2^{100}\)を\(7\)で割ったときの余りを求めなさい。


先程の問題と同じように、指数の\(100\)を掛け算に直して\(2^{100}\)を分解しても、\(7\)で割ったときに余りが\(1\)になるような組み合わせを作ることができません。

このような場合には、合同式の性質3を利用します。


【例題2の解答】

\(2^{100}=2^{1+3×33}=2・8^{33}\)なので、

 \(2^{100}≡2・8^{33}≡2・1^{33}(mod 7)\)…①

 \(2^{100}≡2(mod 7)\)

よって余りは\(2\)となる。(終)


合同式の性質3を①の、「\(2・8^{33}≡2・1^{33}(mod 7)\)」に利用しています。

両辺の係数\(2\)は、\(7\)で割ったときの余りは\(2\)なので、そのままつけておくことが可能なのです

一の位の求め方は?

高校数学の単元「指数関数・対数関数」では、「\(3^{100}\)の最高位の数を求めなさい」など、位の数を求める問題が登場します。

しかし今回の問題では合同式を使いましょう。


【例題3】

\(3^{100}\)の一の位の数を求めなさい。


この問題も【例題2】と同じく、\(3^{100}\)を実際に計算することはできません。

そこで、整数の一の位にどのような性質があるのかを考えます。

例えば、\(10456\)の一の位は\(6\)、\(5237\)の一の位は\(7\)ですね。

ここで合同式を使うと、

 \(10456≡6(mod ?)\)

 \(5237≡7(mod ?)\)

と表せるのですが、「?」に共通して入る数字は何でしょうか?


【例題3の解答】

\(3^{100}\)の一の位を求めるには、\(10\)で割ったときの余りを求めればよい

よって、\(3^{100}=3^{4×25}=81^{25}\)より、

 \(3^{100}≡81^{25}≡1^{25}(mod 10)\)

 \(3^{100}≡1(mod 10)\)

ゆえに、一の位の数は\(1\)となる。(終)


このように、一の位の数は合同式を使い、\(10\)で割ったときの余りとして求めることができます。

指数と割り算の応用問題

それでは最後は応用問題です。


【例題4】

\(7^{n}+2^{4n-3}\)が\(9\)で割り切れることを示しなさい。


\(2^{4n-3}\)の指数をどのように直すかがポイントとなります。


【例題4の解答】

与式より、

 \(7^{n}+2^{4n-3}=7^{n}+2^{4(n-1)+1}=7^{n}+2・16^{n-1}\)

 \(7^{n}+2・16^{n-1}≡7^{n}+2・7^{n-1}(mod 9)\)

よって、

 \(7^{n}+2^{4n-3}≡7^{n}+2・7^{n-1}(mod 9)\)

ここで、

 \(7^{n}+2・7^{n-1}=7・7^{n-1}+2・7^{n-1}=9・7^{n-1}\)

なので、

 \(7^{n}+2^{4n-3}≡9・7^{n-1}≡0(mod 9)\)

ゆえに、\(7^{n}+2^{4n-3}\)は9で割り切ることができる。(終)

まとめ

整数問題の割り算は、指数の知識を使って解けるものもありますが、合同式の性質を利用することで、非常に速く、そして正確に解くことができます。

教科書では応用分野として扱われていますが、本記事で合同式の性質や使い方を身につけて、整数問題を克服していきましょう!

この記事の執筆者
スタモ編集部
最高の学習をもっと身近に、どこでも。スタモ編集部は、大学受験や日々の勉強に役立つ記事を発信しています。予備校講師や塾講師の経験のある東大、京大、早慶の卒業者メンバーが中心に、どこよりも詳しく、どこよりも丁寧な内容をお届けいたします。
関連記事
数学的帰納法はこれでマスター!基本から大学入試レベルの問題の解き方まで徹底解説!
証明が苦手な方なら数学的帰納法はすごい難しいことをしているように見えるのではないでしょうか?しかし、その仕組みを理解すれば意外と簡単なんですよ。本記事では、数学的帰納法の基本や仕組み、問題の解き方について分かりやすく解説していきます。
反比例について徹底解説!基礎からからグラフの描き方まで初学者にもわかりやすく解説します
「反比例って苦手だったな…」「反比例のグラフの描き方忘れちゃった!」「日常生活で反比例の関係にあるものって?」本記事では反比例が苦手な方に向けて、今さら聞けない基本から徹底的に解説していきます。
0から分かる特性方程式!数列の漸化式の問題での使い方を詳しく解説
本記事では特性方程式の内容と証明、その使い方を詳しく解説していきます。特性方程式と、その元となる数列の漸化式(ぜんかしき)とは何かを理解し、さまざまな漸化式の問題をとおして特性方程式の使い方を身につけていきましょう。
0から分かる2倍角の公式!導出から公式を用いた計算まで徹底解説
この記事では、加法定理から2倍角の公式を導出します。また公式を用いた計算まで例題を解いて確認しましょう!
【等差数列】基礎から学んで3つの公式を使いこなそう!
等差数列は数列の基礎、土台です。数列は大学入試において頻出テーマなので、等差数列が苦手であっては大学合格は厳しいと言っても過言ではないでしょう。本記事では等差数列の3つの公式について分かりやすく解説していきます。
切片とは?傾き・2点の座標がわかっている時の求め方、切片の範囲についても解説!
切片とはなんでしょうか。切片とは直線に置いてy軸と交わっている点のことを指し、直線の式を求める際に傾きとともに最も大切な要素の一つです。本記事では切片とその求め方について解説します。
© 2018 スタモ.