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

上野竜生です。abを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」

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

合同式の基本

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

例1) 13≡4(mod 9)

例2) 13n≡4n(mod 9)

例3) 80N≡-N(mod 9) (∵80≡-1 (mod 9))

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

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

(1) 7100を9で割った余りを求めよ。
(2) 8100を6で割った余りを求めよ。

(1)実験すると 71≡7 , 72≡49≡4, 73≡4・7≡28≡1, 74≡7 (mod 9)

(2)実験すると 81≡2 , 82≡4 , 83≡8≡2 (mod 6)

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

答え(1) 73≡343≡1(mod 9)より
7100≡(73)33・7≡133・7≡7 (mod 9)
よって余りは7
(2) 8≡2 (mod 6) , 83≡512≡2より83≡8(mod 6)
8100≡897・83≡897・8≡898,
898≡895・83≡895・8≡896,
以下これを繰り返し用いると
8100≡898≡896≡894≡・・・≡84≡82 (mod 6)
82≡64≡4 (mod6)より余りは4
実験すれば、繰り返されることぐらいはすぐにわかります。ですが論証としては単純に「あまりが7→4→1を繰り返す」と説明するだけでは不十分です。

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

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

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

答え22n-1≡2・22n-2≡2・(22)n-1≡2・4n-1 (mod 7)
18≡4 (mod 7)より18n≡4n≡4・4n-1(mod 7)
よって22n-1+3・18n≡2・4n-1+3・4・4n-1≡14・4n-1≡0 (mod 7)
となり7の倍数。
大学で習いますが、(mod 7)の世界では2-1といえば2・a≡1 (mod 7)を満たすaのことです。
これは0から6の中から探してみればわかりますが4のことです。高校生には少し難しいのでmod nの世界では分数は使わない!と覚えておきましょう。
nが奇数のとき8n+2nは5で割り切れることを証明せよ。
答え8≡3, 2≡(-3) (mod 5)より
8n+2n≡3n+(-3)n
≡3n-3n   (∵nは奇数)
≡0 (mod 5)

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

3150の下2ケタを求めよ。
下2ケタということは100で割った余りです。
答え3150=975=(10-1)75を二項定理で展開すると
75C0107575C11074+・・・-75C73102+75C7410-75C75
下線部の項はすべて102=100の倍数なので最後の2項だけ調べればよい。
75C7410-75C75=75・10-1=749より100で割った余りは49
よって3150を100で割った余りは49

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

数学はもちろん他の科目も勉強できる「スタディサプリ」なら人気講師の授業動画で、塾にいかなくてもまるで塾にいったかのような勉強ができます。塾と比較すると格安で、しかも無料おためしもできます。当サイトオススメのサイトです。


スタディサプリについて解説したページはこちら
スポンサーリンク

シェアする

  • このエントリーをはてなブックマークに追加

フォローする