上野竜生です。abを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)
例２） 13n≡4n(mod 9)
例３） 80N≡-N(mod 9) （∵80≡-1 (mod 9)）
合同式は必ずしも「あまり」を返すのではありませんので35≡17 (mod 9)というような表現でも誤りではありません。あくまでも「あまりが等しい」というだけで右辺の値が0≦(あまり)<aを満たす数学の定義での「あまり」である必要はないのです。
パターン１ 同じものが出るまで実験する
(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)
という風に同じものが繰り返されます。これを利用して解きます。
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
パターン２ nがらみでも諦めない
2-1を\(\frac{1}{2} \)と表現するのはなるべく避けましょう。これは大学に行けば理由がわかります（一応下にも参考を載せます）。n-1乗を作り，整数のまま処理することが重要です。
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の倍数。
これは0から6の中から探してみればわかりますが4のことです。高校生には少し難しいのでmod nの世界では分数は使わない！と覚えておきましょう。
8n+2n≡3n+(-3)n
≡3n-3n （∵nは奇数)
≡0 (mod 5)
パターン３ 最終的には二項定理
75C01075-75C11074+・・・-75C73102+75C7410-75C75
下線部の項はすべて102=100の倍数なので最後の2項だけ調べればよい。
75C7410-75C75=75・10-1=749より100で割った余りは49
よって3150を100で割った余りは49
もちろんパターン１に当てはめて3nを順番に計算し，100で割った余りが繰り返されるところまで計算してもできなくはないですがしんどいです。
解説を読んで数学がわかった「つもり」になりましたか？数学は読んでいるうちはわかったつもりになりますが演習をこなさないと実力になりません。そのためには問題集で問題を解く練習も必要です。オススメの参考書を厳選しました
<高校数学>上野竜生です。数学のオススメ参考書などをよく聞かれますのでここにまとめておきます。基本的にはたくさん買うよりも…
上野竜生です。大学数学の参考書をまとめてみました。フーリエ解析以外は自分が使ったことある本から選びました。 大…
上野竜生です。当サイトでも少し前まで各ページで学習サイトをオススメしていましたが他にもオススメできるサイトはた…
