2^{50}\,を7で割ったときの余りを求めよ.$ \\[.8zh] \hspace{.5zw}(2)\ \ $17^{50}\,を9で割ったときの余りを求めよ.$ \\[.8zh] \hspace{.5zw}(3)\ \ $23^{100}\,を19で割ったときの余りを求めよ.$ \\ 累乗数の余りと下位桁の数}}}} \\\\[.5zh] 累乗数の余りは,\ 主に3つの方法で求められる.\ 基本は合同式の利用である. \\[.2zh] 問題を通して,\ 各方法の要点やメリット・デメリットを確認してほしい.\ \\\\ $[1]$\ \ \textbf{\textcolor[named]{ForestGreen}{余りの種類は限られている}}から,\ \textbf{\textcolor{red}{$\bm{a^n}$の余りは必ず循環する.}} \\[.2zh] \phantom{ [1]}\ \ よって,\ 具体的に書き出して\textbf{\textcolor{red}{周期性}}を調べる. \\\\ $[2]$ \ $\bm{\textcolor{blue}{合同式}}を利用して\bm{\textcolor{red}{底aの絶対値を小さくする.}}$ \\[.5zh] \centerline{$\bm{\textcolor{cyan}{a\equiv b\pmod m}}\ のとき \bm{\textcolor{red}{a^n\equiv b^n \pmod m}} (n：自然数)$} \\\\ $[3]$\ \ \textbf{\textcolor{magenta}{二項定理}}(数I\hspace{-.1em}I)を利用する. \phantom{ (1)}\ \ 下線部は9の倍数である. \\[.2zh] \phantom{ (1)}\ \ $17^{50}$を9で割ったときの余りは,\ $\textcolor{red}{\kumiawase{50}{50}(-\,1)^{50}}$を9で割ったときの余りに等しい. \ (3)\ \ \textcolor{cyan}{フェルマーの小定理}より (1)\ \ 実際に計算して余りを書き出してみると,\ 以下のように\bm{周期3で循環}することがわかる. \\[.5zh] \phantom{(1)}\ \ 50は3で割ると2余る数であるから,\ 2^{50}\,を7で割ったときの余りは4であるとわかる. \\[.2zh] \phantom{(1)}\ \ 誰でもできる単純な方法だが,\ 3つのデメリットがある. \\[1zh] \phantom{(1)}\ \ 第1に,\ (2),\ (3)のように底aの値が大きい場合には実際に計算するのが非常に大変である. \\[1zh] \phantom{(1)}\ \ 第2に,\ 循環の周期が長い場合も計算が面倒になる. \\[.2zh] \phantom{(1)}\ \ 7で割ったときの余りならば,\ 0から6までの7種類しかない. \\[.2zh] \phantom{(1)}\ \ よって,\ a^8\,まで計算するとその余りはすでに出てきた余りと一致するはずで,\ 以降は循環する. \\[.2zh] \phantom{(1)}\ \ (3)のように割る数が19の場合,\ 最悪20乗まで計算する羽目になる. \\[1zh] \phantom{(1)}\ \ 第3に,\ 記述試験において余りが循環することを自明としてよいかが微妙である. \\[.2zh] \phantom{(1)}\ \ もっとも,\ 周期kで循環することの証明は容易なので,\ 記述しておけばよいだけである. \\[.5zh] \phantom{(1)}\ \ a^n\,をmで割ったときの余りが周期kで循環する \\[.2zh] \phantom{(1)}\ \ \Longleftrightarrow\ a^{n+k}\,とa^n\,をmで割ったときの余りが一致する \\[.2zh] \phantom{(1)}\ \ \Longleftrightarrow\ \bm{a^{n+k}-a^n\,がmで割り切れる(mの倍数である)} \\[.5zh] \phantom{(1)}\ \ \rei\ \ 2^{n+3}-2^n=2^n(2^3-1)=2^n\cdot7\ より,\ 2^n\,を7で割ったときの余りは周期3で循環する. \\\\ \phantom{(1)}\ \ 合同式を利用すると,\ 論理的に不足なく,\ 非常に簡潔に済む. \\[.2zh] \phantom{(1)}\ \ a^n\equiv b^n\,を利用するため,\ まずは\bm{7を超えるところまで2を何乗かする.} \\[.2zh] \phantom{(1)}\ \ 3乗で8となり7を超えるから,\ \bm{50乗を3乗ごとにまとめ,\ 8\equiv1を適用}すればよい. \\[.2zh] \phantom{(1)}\ \ このようにして,\ 底aや指数nを徐々に小さくしていくといつかは求まる. \\[.2zh] \phantom{(1)}\ \ 特に,\ \bm{a^n\equiv\pm\,1となるようなnを見つける}ことができれば楽になる. \\[1zh] (2)\ \ 17\equiv-\,1\pmod9\ のように\bm{負の剰余を利用}し,\ 底aの絶対値を小さくすると簡潔に済む. \\[.2zh] \phantom{(1)}\ \ 負の剰余を利用しない場合,\ 別解1のようになる.\ 本問の場合は大して変わらない. \\[1zh] \phantom{(1)}\ \ 参考までに,\ 二項定理を利用する方法も示しておいた(別解2). \\[.2zh] \phantom{(1)}\ \ まず,\ 17を9の倍数部分と余りの部分に分ける(\bm{割り算の等式の形}). \\[.2zh] \phantom{(1)}\ \ 17=9\cdot1+8ではなく17=9\cdot2-1のように\bm{余りの部分の絶対値が小さくなるようにする.} \\[.2zh] \phantom{(1)}\ \ (9\cdot2-1)^{50}\,を二項展開すると,\ ほとんどの項が9の倍数になる. \\[.2zh] \phantom{(1)}\ \ 結局,\ 9の倍数ではない項(本問では末項のみ)を9で割ったときの余りを求めることになる. \\[.2zh] \phantom{(1)}\ \ このことを合同式で17^{50}\equiv(-\,1)^{50}\,と表せるわけであり,\ 合同式の有用性は強烈である. \\[1zh] (3)\ \ 普通は別解のように地道にやるしかないが,\ 割る数が大きいと中々面倒である. \\[.2zh] \phantom{(1)}\ \ 上級者は以下に示す裏技的知識をもっておくことを推奨する. \\[1zh] \phantom{(1)}\ \ \bm{フェルマーの小定理 pが素数のとき a^{p-1}\equiv1\pmod p} \\[.2zh] \phantom{(1)}\ \ \bm{オイラーの定理 a,\ mが互いに素のとき a^{\phi(m)}\equiv1\pmod m} \\[1zh] \phantom{(1)}\ \ フェルマーの小定理を一般化したのがオイラーの定理である. \\[.2zh] \phantom{(1)}\ \ \bm{\phi(m)\,はmと互いに素なm以下の自然数の個数(オイラー関数)}のことであり,\ 以前紹介した. \\[1zh] \phantom{(1)}\ \ これらを利用するとa^n\equiv1となるnを容易に見つけることができ,\ 後の計算が楽になる. \\[.2zh] \phantom{(1)}\ \ オイラーの定理より,\ a,\ mが互いに素ならば必ずa^n\equiv1となるnが存在するわけである. \\[1zh] \phantom{(1)}\ \ 本問の場合,\ 19は素数であるから,\ フェルマーの小定理を適用できる. \\[.2zh] \phantom{(1)}\ \ 余りを求めることが主題ならば,\ 記述試験で無断使用しても問題ない(と思う). \\[1zh] \phantom{(1)}\ \ (1)の場合,\ フェルマーの小定理より2^6\equiv1\pmod7なので,\ これを利用することもできる. \\[.2zh] \phantom{(1)}\ \ ところで,\ 2^3\equiv1\pmod7であった. \\[.2zh] \phantom{(1)}\ \ このように,\ 2つの定理を用いて求まる指数nが,\ a^n\equiv1となる最小の数とは限らない. \\[.2zh] \phantom{(1)}\ \ ただし,\ nは最小の数の倍数になることが知られている. \\[1zh] \phantom{(1)}\ \ (2)の場合,\ 9は素数ではないからフェルマーの小定理は適用できない. \\[.2zh] \phantom{(1)}\ \ 17と9は互いに素なので,\ オイラーの定理が適用できる. \\[.2zh] \phantom{(1)}\ \ 以前,\ pが素数のとき,\ \phi(p^n)=p^n-p^{n-1}\,となることを示した. \\[.2zh] \phantom{(1)}\ \ \phi(9)=\phi(3^2)=3^2-3^1=6より17^6\equiv1\pmod9なので,\ これを利用することもできる. 13^n-9^n-4^n\ (n:自然数)は36で割り切れることを示せ.$ \\ 36=4\times9\ (4,\ 9は互いに素)\ より,\ \bm{4の倍数かつ9の倍数}であることを示せばよい. \\[.2zh] \bm{合同式で底を小さくする}ことで容易に示すことができる. \\[1zh] \bm{a^n-b^n\,の因数分解公式(暗記必須)を用いた別解}も重要である. \\[.2zh] a^2-b^2=(a-b)(a+b),\ \ a^3-b^3=(a-b)(a^2+ab+b^2)\ を一般化したものである. \\[.2zh] この公式は,\ 一般に\bm{a^n-b^n\,がa-bで割り切れる(a-bの倍数である)}ことを意味している. nを自然数とする.$ \\[1zh] \hspace{.5zw}$ (1)\ \ 3^{2n}+4^{n+3}\ は5の倍数であることを示せ.$ \\[.8zh] \hspace{.5zw}$ (2)\ \ 19^n+(-\,1)^{n-1}2^{4n-3}\ は7で割り切れることを示せ. \ [\,東京工業大・改\,]$ a^{m+n}=a^m\times a^n,\ \ a^{mn}=(a^m)^n=(a^n)^m\ といった計算を正しく実行できる必要がある. \\[.2zh] a^n\,がaをn個掛けたものという認識があれば間違わない. \rei\ \ a^5=a^2\times a^3,\ \ a^6=(a^2)^3=(a^3)^2 \\[1zh] \bm{底や指数をそろえる}ことを目指して変形していくと,\ 自ずと\equiv0が示される. \\[.2zh] 19は\bm{絶対値が小さい負の剰余}で表し,\ 2^{4n-3}\,は\bm{2^3\equiv1}の利用を想定して変形した. \\[.2zh] 47^{2011}\,の一の位の数を求めよ.$ \\[.5zh] \hspace{.5zw}(2)\ \ $21^{21}\,を400で割ったときの余りを求めよ.$ \\[.5zh] \hspace{.5zw}(3)\ \ $99^{100}\,の下位5桁を求めよ.$ \\ \bm{下位桁の数}を求める問題も,\ 実質余りを求める問題である. \\[.2zh] 例えば,\ \bm{一の位の数は10で割ったときの余り,\ 下2桁は100で割ったときの余り}に等しい. \\[1zh] (1)\ \ 10で割ったときの余りを求めればよいから,\ 10を法とする合同式を利用する. \\[.2zh] \phantom{(1)}\ \ \bm{2乗ごとにまとめ,\ 7^2\equiv-\,1\ を利用}すると簡潔に済む. \\[1zh] (2)\ \ 割る数が大きくなると,\ 合同式で底を小さくすることが困難になる. \\[.2zh] \phantom{(1)}\ \ \bm{割る数が累乗数の場合,\ 二項定理の利用が有効}である. \\[.2zh] \phantom{(1)}\ \ 割る数\,400=20^2\,を考慮すると,\ \bm{21=20+1として二項展開}すればよいことがわかる. \\[.2zh] \phantom{(1)}\ \ 20^2\,をもつ項はすべて400で割り切れるから,\ 後は残りの部分を400で割ることになる. \\[.2zh] \phantom{(1)}\ \ 余りを421と答えてしまうミスが多いので注意すること. \kumiawase{21}{20}=\kumiawase{20}{1}=20 \\[1zh] (3)\ \ 下位5桁は\bm{100000=100^3\,で割ったときの余り}であるから,\ やはり二項定理が有効である. \\[.2zh] \phantom{(1)}\ \ 99=100-1と考えて二項展開すると,\ 100^3\,をもつ項は下位5桁に影響しなくなる. \\[.2zh] \phantom{(1)}\ \ 残りの部分を実際に計算し,\ その下位5桁を答えればよい.
