aのb乗をNで割った余り｜数学の偏差値を上げて合格を目指す

当サイトは、PRを含む場合があります。

上野竜生です。a^bをNで割った余りを求める問題を解いてみます。

$aのb乗をNで割った余り$

「余り」の別表現

小学校では30÷7=4あまり2などと表現しましたが一般に
N÷a=bあまりrであることを次のように表現することができます。
N=a・b+r　（0≦r<a）

この最後の0≦r<aと定めるおかげでb,rはただ1つに定めることができます。

少し違和感があるかもしれませんが一般に数学ではこのようにおきます。たとえば

×　-30=7・(-4)+(-2)⇔「-30÷7=-4あまり-2」　←あまりが0≦(あまり)<7の範囲にない
○　-30=7・(-5)+5　⇔「-30÷7=-5あまり5」

となります。（なお一部のプログラム言語などでは上の×で示したような「あまり」を返すこともあります）

合同式の基本

詳しくは合同式のページをご覧ください。今回使う考えの具体例を下に書くのでそれが理解できれば次に進みましょう。

例１）　13≡4(mod 9)

例２）　13ⁿ≡4ⁿ(mod 9)

例３）　80N≡-N(mod 9)　（∵80≡-1 (mod 9)）

合同式は必ずしも「あまり」を返すのではありませんので35≡17 (mod 9)というような表現でも誤りではありません。あくまでも「あまりが等しい」というだけで右辺の値が0≦(あまり)<aを満たす数学の定義での「あまり」である必要はないのです。

パターン１　同じものが出るまで実験する

(1)　7¹⁰⁰を9で割った余りを求めよ。
(2)　8¹⁰⁰を6で割った余りを求めよ。

(1)実験すると 7¹≡7 , 7²≡49≡4, 7³≡4・7≡28≡1, 7⁴≡7 (mod 9)

(2)実験すると 8¹≡2 , 8²≡4 , 8³≡8≡2 (mod 6)

という風に同じものが繰り返されます。これを利用して解きます。

答え(1)　7³≡343≡1(mod 9)より
7¹⁰⁰≡(7³)³³・7≡1³³・7≡7 (mod 9)
よって余りは7
(2)　8≡2 (mod 6) , 8³≡512≡2より8³≡8(mod 6)
8¹⁰⁰≡8⁹⁷・8³≡8⁹⁷・8≡8⁹⁸,
8⁹⁸≡8⁹⁵・8³≡8⁹⁵・8≡8⁹⁶,
以下これを繰り返し用いると
8¹⁰⁰≡8⁹⁸≡8⁹⁶≡8⁹⁴≡・・・≡8⁴≡8² (mod 6)
8²≡64≡4 (mod6)より余りは4

実験すれば、繰り返されることぐらいはすぐにわかります。ですが論証としては単純に「あまりが7→4→1を繰り返す」と説明するだけでは不十分です。

パターン２　nがらみでも諦めない

すべての自然数nに対して2^2n-1+3・18ⁿは7の倍数であることを証明せよ。

2^-1を$\frac{1}{2} $と表現するのはなるべく避けましょう。これは大学に行けば理由がわかります（一応下にも参考を載せます）。n-1乗を作り，整数のまま処理することが重要です。

答え2^2n-1≡2・2^2n-2≡2・(2²)^n-1≡2・4^n-1　(mod 7)
18≡4 (mod 7)より18ⁿ≡4ⁿ≡4・4^n-1(mod 7)
よって2^2n-1+3・18ⁿ≡2・4^n-1+3・4・4^n-1≡14・4^n-1≡0 (mod 7)
となり7の倍数。

大学で習いますが、(mod 7)の世界では2^-1といえば2・a≡1 (mod 7)を満たすaのことです。
これは0から6の中から探してみればわかりますが4のことです。高校生には少し難しいのでmod nの世界では分数は使わない！と覚えておきましょう。

nが奇数のとき8ⁿ+2ⁿは5で割り切れることを証明せよ。

答え8≡3, 2≡(-3) (mod 5)より
8ⁿ+2ⁿ≡3ⁿ+(-3)ⁿ≡3ⁿ-3ⁿ（∵nは奇数)≡0 (mod 5)

パターン３　最終的には二項定理

3¹⁵⁰の下2ケタを求めよ。

下2ケタということは100で割った余りです。

答え3¹⁵⁰=9⁷⁵=(10-1)⁷⁵を二項定理で展開すると
₇₅C₀10⁷⁵-₇₅C₁10⁷⁴+・・・-₇₅C₇₃10²+₇₅C₇₄10-₇₅C₇₅
下線部の項はすべて10²=100の倍数なので最後の2項だけ調べればよい。
₇₅C₇₄10-₇₅C₇₅=75・10-1=749より100で割った余りは49
よって3¹⁵⁰を100で割った余りは49

この例では最後の2項が残ってしまったので二項定理を使った解法じゃないと厳しいのです。合同式の証明をもう1度見てほしいのですが，基本的に合同式では最後の項だけに注目して証明しているので，後ろの2項以上が残った場合は合同式は通用しないのです。
もちろんパターン１に当てはめて3ⁿを順番に計算し，100で割った余りが繰り返されるところまで計算してもできなくはないですがしんどいです。

解説を読んで数学がわかった「つもり」になりましたか？数学は読んでいるうちはわかったつもりになりますが演習をこなさないと実力になりません。そのためには問題集で問題を解く練習も必要です。オススメの参考書を厳選しました

<高校数学>