整数問題の解き方:合同式

合同式の基礎知識

今回は整数シリーズの中で、合同式について始めから解説していきます。

以前の整数シリーズは以下よりご覧下さい

整数問題の解法/解説記事まとめ

・・・

合同式は「名前は聞いたことがあるけどよくわからない」、「難しそう」といった印象を持っている人もいるかと思います。

また、学校でしっかり教えて貰わなかった!と言う生徒もいます。

慣れれば整数問題を解く際に、大変便利な物なので、是非今回で身に付けて下さい!

合同式とは

2つの異なる数を同じ数で割った時、その余りが同じものを合同の記号である「≡」で表したものです。

具体的な数字を用いて説明していきます。

17と9は「4」という数で割った時、余りが1で同じです。実際計算してみると、

17÷4=4余り1 又 9÷4=2余り1

この時合同式を使って、17≡9 (mod 4)と書き、

「17と9は4を法として合同」という風に言います。意味は「17と9は4で割った余りが同じ」です。

ここ迄では何が便利なのかよくわからないと思うので、合同式の四則演算を解説してからその威力を紹介します。

合同式の四則演算

合同式は、和(+)、差(-)、積(×)に関しては普通の式と同様に計算できます。実例と共に見ていきます。

今、13≡17(mod4)  と11≡3(mod4)

がある時、

和13+11≡17+3≡0 (mod4)となり、

差13-11≡17-3≡2 (mod4)

積13・11≡17・3≡3(mod4)

でいずれの場合も確かに成立しています。

しかし、商(割り算)だけは、常に成り立つわけではなく、割る数と法とする数が互いに素な時のみ成立します。

これらを文字式で表すと

m≡n(mod A)、p≡q(modA)の時

$$\begin{aligned}m\equiv n\left( modA\right) \\
p\equiv q\left( modA\right) \end{aligned}$$

m+p≡n+q (modA)

mーp≡nーq (modA)

$$\begin{aligned}m+p\equiv n+q\left( modA\right) \\
m-p\equiv n-q\left( modA\right) \end{aligned}$$

mp≡nq (modA)

更に、m^c≡n^c (modA)

$$\begin{aligned}mp\equiv nq\left( modA\right) \\
m^{c}\equiv n^{c}\left( modA\right) \end{aligned}$$

以上のことに注意して、例題に入ります。

例題:2^50を5で割った時の余りを求めよ。

まさか本当に50乗する訳にはいかないので、2つの解法を思い浮かべます。

(1-1)規則性を見つける。

2^1/5=0余り2

2^2/5=0余り4

2^3/5=1余り3

2^4/5=3余り1

2^5/5=6余り2

2^6/5=12余り4

・・・

どうやら、24312431という規則がありそうです。しかしこれでは底である2が大きな数字になった時、時間がかかり過ぎて実践的ではありません。

そこで、

(1-2)合同式を利用する

ここでは$$2^{50}=\left( 2^{4}\right) ^{12}\times 4 と変形出来ます。$$

(2^4)に注目して、2^4=16 、16÷5=3余り1 、 1÷5=0余り1、

つまり、5で割った時16=2と1の余りは同じになります。

即ち、5を法とすると、2^4=16と1が合同であると言えるから、2^4≡1(mod 5) と表せます。

$$2^{4}\equiv 1\left( mod5\right) $$

従って 2^50=(2^4)^12×4≡1^12×4≡4 (mod5)

$$2^{50}=\left( 2^{4}\right) ^{12}\times 4\equiv 1^{12}\times 4=4\left( mod5\right) $$

よって余りは4と求めることが出来ました。

 

この類の問題を解く時に一番大切なことは、

「巨大な数を合同式を使ってどんどん小さい数字にして行く」

と言う事です。そして、その過程で底となる数(今回は2)の何乗かが、法の数の倍数と比べた時(5の倍数)

±1や0等簡単な数字になるようにうまく冪乗を作ってやるとうまく解くことが出来ます。

 

この様にして、普通では計算できない様な数を扱える事が合同式の最大の強みと言えます。

他にも整数分野ではあちこちで合同式を使うとスムーズに回答できる問題があるので、逐次記事を追加して行きます。

ジャンルは違いますが、大きな数の桁数や最高位の数字を求める方法をまとめた記事を作成しました。

→「常用対数を使って桁数や最高位の数を求める方法」を読む。

>>整数問題の解法10選「センス・閃きなしで整数を攻略する方法」に戻る<<

今日も読んでくださり有難うございました。

お役に立ちましたら、SNSボタンでシェアお願いします!

Twitterでフォローしよう