(1) $N=111^{111}$を法$19$で簡約してください｡ つまり, $N\equiv n \pmod{19}$で$0\leq n \leq 18$となる整数$n$を見つけてください｡ 下の計算結果は自由に使用してください｡ \begin{align*} 111^1 &\equiv 16 \pmod{19} \\ 111^2 &\equiv 9 \pmod{19} \\ 111^3 &\equiv 11 \pmod{19} \\ 111^4 &\equiv 5 \pmod{19} \\ 111^5 &\equiv 4 \pmod{19} \\ 111^6 &\equiv 7 \pmod{19} \\ 111^7 &\equiv 17 \pmod{19} \\ 111^8 &\equiv 6 \pmod{19} \\ 111^9 &\equiv 1 \pmod{19} \\ \end{align*}
(2) $N^N$を法$19$で簡約してください｡
与えられた$111$のべき乗の合同式の計算結果の中で, 特に$111^9 \equiv 1 \pmod{19}$が右辺が$1$なので使い勝手が良さそうです｡ これを利用するために指数を$111=9\cdot 12 + 3$と書きます｡
すると \begin{align*} 111^{111} &\equiv 111^{9\cdot 12 + 3} \pmod{19}\\ &\equiv (111^9)^{12}\cdot 111^3 \pmod{19}\\ &\equiv 1^{12} \cdot 11 \pmod{19}\\ &\equiv 11 \end{align*} ここで3つ目の合同式の変形には, 与えられた計算結果$111^3 \equiv 11 \pmod{19}$を用いました｡
この計算から$N=111^{111}$を法$19$で簡約すると$11$になることがわかりました｡
問1の結果の$N\equiv 11 \pmod{19}$の両辺を$N$乗すると \[N^N \equiv 11^N \pmod{19}\] となります｡ 右辺の$11$のべき乗を計算するために, まず$11^2$を計算すると \[11^2=121=19\cdot 6 + 7\] より$11^2\equiv 7 \pmod{19}$を得ます｡ この両辺に$11$を掛けると \[11^3 \equiv 77 \equiv 1 \pmod{19}\] となります｡
さて, $111$は$3$の倍数なので$N=111^{111}$も$3$の倍数です｡ そこで, $N=3m$ ($m\in \Z$)と書くと \[11^N \equiv 11^{3m} \equiv (11^3)^m \equiv 1^m \equiv 1 \pmod{19}\] を得ます｡ 以上から, $N^N$を法$19$で簡約化した結果は$1$となることがわかりました｡