検索用コード
2^{50}\,を7で割ったときの余りを求めよ.$ \\[.5zh] \hspace{.5zw}(2)\ \ $17^{50}\,を9で割ったときの余りを求めよ.$ \\  3つの方法を示す.\ 実質的に同じだが,\ 多少のメリット・デメリットはある. {余りの種類は限られている}}からの余りは必ず循環する.}} \\[.2zh] \phantom{ [1]}\ よって,\ 具体的に書き出して\textbf{\textcolor{red}{周期性}}を調べる. 合同式}で\textcolor{red}{指数の底の絶対値を小さくする.}{a^n\equiv b^n \pmod p}}\ \ (n:自然数)$} \\\\  $[3]$\ \textbf{\textcolor{magenta}{二項定理}}を利用する. 例えば,\ 7で割ったときの余りでならば,\ 0~6の7種類しかない. \\ よって,\ a^7までに必ず1乗と同じ余りになるものが存在し,\ 以降は循環する. \\[1zh] 実際に書き出すのもよいが,\ やはり合同式を用いるのが簡潔で本質的である. \\ このときに用いる公式は,\ 次のように繰り返して導かれる. 公式の適用例  pで割ったときの余りは,\ \bm{(p+b)^nに変形してから二項定理を適用}するとわかる. \\ 二項定理を用いた二項展開式が次である 下線部はpを因数にもつから,\ pで割り切れる.\ よって,\ 最後の項が余りである. \\ 例として4^{10}を3で割ったときの余りを求めてみる. \ 合同式では,\ 下線部は0として扱うから,\ 先の例のように簡潔になる. \\ 9の倍数余りを実際に書き出すと次のように\bm{周期3で循環}することがわかる. \\     ここでは合同式を用いた解答を示した. \\ \phantom{(1)}\ 7で割ったときの余りであるから,\ \bm{7を超えるところまで2を何乗かする.} \\ \phantom{(1)}\ 3乗で8となり7を超えるから,\ \bm{50乗を3乗ごとにまとめ,\ 8\equiv1を適用}する. \\[1zh] (2)\ 17のように底が大きくなると,\ 具体的に書き出して調べるのは容易ではない. \\ \phantom{(1)}\ やはり,\ 合同式を利用する方法に慣れておきたい. \\ \phantom{(1)}\ 17\equiv-1\pmod9\ のように\bm{負の剰余を活用}すると圧倒的に簡潔になる. \\ \phantom{(1)}\ 二項定理を利用する別解も示す. \\ \phantom{(1)}\ 9で割ったときの余りは,\ \{(9の倍数)+b\}^n\ の形にして二項展開して求める. \\ \phantom{(1)}\ 17=9\cdot1+8\ ではなく,\ 17=9\cdot2-1\ のように\bm{bの絶対値を小さくする}こと. 13^n-9^n-4^n\ は36で割り切れることを示せ.$ \\ 36で割り切れる4の倍数)-4^n=(4の倍数)}$ \\[1zh]  $よって \textcolor{cyan}{(13^n-4^n)-9^n=(9の倍数)-9^n=(9の倍数)}$ \\\\ \centerline{$\therefore 4の倍数かつ9の倍数であるから,\ \bm{36で割り切れる.}$ 36=4\times9\ (4,\ 9は互いに素)\ より,\ \bm{4の倍数かつ9の倍数}であることを示す. \\ \bm{合同式で底を小さくする}ことで容易に示すことができる. \\[1zh] \bm{a^n-b^n\ の因数分解公式を用いた別解}も重要である.\ この公式は暗記事項である. \\ a^2-b^2=(a-b)(a+b),\ \ a^3-b^3=(a-b)(a^2+ab+b^2)\ の一般化である. \\ 整数分野では\bm{因数分解して積の形にする}ことが重要であり,\ この公式が役立つ. \\ この公式は,\ \bm{a^n-b^n\ がa-bで割り切れる}ことを意味しているのである. \\  \rei\ \ 3^n-1=(3-1)(3^{n-1}+\cdots\cdots+1)\ より,\ 3^n-1は2の倍数である. \\ これをうまく利用すると,\ 別解のように証明できる. 全ての自然数a}について,\ \textcolor{red}{a^5の1の位とaの1の位は等しい}.}$ \\  \ {\small \syoumei\ $a^5\equiv a\pmod5\ (\because\ フェルマーの小定理), また,\ 偶奇で分類して調べると,\ a^5\equiv a\pmod2がすぐわかる. nを自然数とする.$ \\[.5zh] \hspace{.5zw}$ (1)\ \ 3^{2n}+4^{n+1}\ は5の倍数であることを示せ.$ \\[.5zh] \hspace{.5zw}$ (2)\ \ 19^n+(-1)^{n-1}2^{4n-3}\ は7で割り切れることを示せ. \ \ [東工大]$ \\ 5の倍数である.}7で割り切れる 通常は数学的帰納法を用いて証明するパターンだが,\ 合同式を使うと簡潔に済む. \\ \bm{底と指数をそろえる}ことを目指して変形するとまとめることができる. \\ 19は\bm{絶対値が小さい負の剰余}で表す. \\ 2^{4n-3}\ は,\ まず指数部分を簡単にすることを目指す. \\ しかし,\ 整数問題であるから,\ 2^{-3}\cdot2^{4n}=\bunsuu18\cdot2^{4n}\ と分数にすべきではない. \\ よって,\ 上の解答のように変形することになるのだが,\ 慣れが必要かもしれない. 47^{2011}\ の一の位の数を求めよ.$ \\[.5zh] \hspace{.5zw}(2)\ \ $21^{21}を400で割ったときの余りを求めよ.$ \\[.5zh] \hspace{.5zw}(3)\ \ $99^{100}の下位5桁を求めよ.$ \\ 一の位の数\ 3下線部の項は20^2=400で割り切れる下線部の下位5桁は0であるから影響しない.$ \\[1zh] \bm{「下何桁の数」}を求める問題も,\ 実質余りを求める問題である. \\ 例えば,\ \bm{一の位の数は10で割った余り,\ 下位2桁は100で割った余り}である. \\[1zh] (1)\ 10で割った余りと考え,\ 合同式で求める. \\ \phantom{(1)}\ \bm{2乗ごとにまとめ,\ 7^2\equiv-1\ を利用}すると楽である. \\ \phantom{(1)}\ このように,\ 何乗かして余りが\pm1になるものが見つかれば楽になる. \\[1zh] (2)\ 割る数が大きくなると,\ 合同式で底を小さくすることが困難になる. \\ \phantom{(1)}\ このような場合,\ 二項定理が威力を発揮する. \\ \phantom{(1)}\ 割る数\,400=20^2\ を考慮し,\ \bm{21=20+1と考えて二項展開}すればよい. \\ \phantom{(1)}\ 20^2\,がある項は当然400で割り切れるから,\ 後は残った部分を400で割る. \\ \phantom{(1)}\ なお,\ 1^nは記述を省略した. \\[1zh] (3)\ \bm{100000=100^3\,で割ったときの余り}だが,\ やはり二項定理が役立つ. \\ \phantom{(1)}\ 100=99-1と考えて二項展開すると,\ 100^3\,を因数にもつ部分は無視できる. \\ \phantom{(1)}\ 残りの部分を実際に計算し,\ その下位5桁を答えればよい.