どうも、木村（@kimu3_slime）です。
今回は、\(n^n\)を\(3\)で割ったあまりの規則性、その証明について紹介します。
\[n^n \equiv \begin{cases} 0& (n \equiv 0 (\mathrm{mod}\, 3) のとき ) \\ 1 & (n \equiv 1 (\mathrm{mod}\, 3) のとき )\\2 & (n \equiv 2 (\mathrm{mod}\, 3) かつ、 n が奇数のとき ) \\ 1 & (n \equiv 2 (\mathrm{mod}\, 3) かつ、 n が偶数のとき ) \end{cases}\]
n^nを3で割ったあまりの規則性
まず、\(n\)が小さいときにあまりを計算し、その規則性を調べてみましょう。
あまりを調べるにあたって、合同算術の記号\(x\equiv y\, (\mathrm{mod}\, n)\)を用います。
\[1^1 \equiv 1 (\mathrm{mod}\, 3)\]
\[2^2 \equiv 4 \equiv 1(\mathrm{mod}\, 3)\]
\[3^3 \equiv 0(\mathrm{mod}\, 3)\]
が成り立ちます。これらはそれぞれ、左辺を\(3\)で割ったあまりが\(1,1,0\)に等しいという意味です。
\(3\)はそれ自身が\(3\)で割り切れるので、それ自身を何乗しようが3で割り切れます。\(6^6, 9^9\)なども同様ですね。
\(n^n\)は、数が大きくなってくると計算しにくいです。そこであまりの計算に都合が良い形で計算しましょう。
\[\begin{aligned} 4^4 &= (3+1)^4 \\&= 3^4+ C(4,3) 3^3 + C(4,2) 3^2+ C(4,1)3^1 +1 \end{aligned}\]と二項展開できます。\(C(n,k)\)は二項係数です。前半の項は3がかかっているので3で割り切れ、1のみが残ります。したがって、\(4^4 \equiv 1(\mathrm{mod}\, 3)\)です。
同様にして、
\[\begin{aligned} 5^5 &= (6-1)^5 \\&= 6^5+C(6,5)6^4 (-1)\\&+ \cdots + C(5,1)6^1(-1)^4 +(-1)^5 \end{aligned}\]
となります。前半の項は6の倍数なので3で割り切れます。また、\((-1)^5 \equiv -1 \equiv 2 (\mathrm{mod}\, 3)\)です。したがって、\(5^5 \equiv 2(\mathrm{mod}\, 3)\)となりました。
\(7^7\)は、\((6+1)^7\)の展開を考えることで、\(7^7 \equiv 1(\mathrm{mod}\, 3)\)とわかります。
\(8^8\)は、\((9-1)^8\)の展開を考えることで、あまりとして\((-1)^8\)が出てくるので、\(8^8 \equiv 1(\mathrm{mod}\, 3)\)です。
n^nを3で割ったあまりの規則性の証明
以上の結果を一般化すれば、\(3\)を法として、
\[n^n \equiv \begin{cases} 0& (n \equiv 0 (\mathrm{mod}\, 3) のとき ) \\ 1 & (n \equiv 1 (\mathrm{mod}\, 3) のとき )\\2 & (n \equiv 2 (\mathrm{mod}\, 3) かつ、 n が奇数のとき ) \\ 1 & (n \equiv 2 (\mathrm{mod}\, 3) かつ、 n が偶数のとき ) \end{cases}\]
と予想できます。これが正しいことを証明しましょう。
合同式の一般的な性質として、
\(a,b\)を整数、\(n,k\)を正の整数とする。
\(a \equiv b \,(\mathrm{mod}\,n)\)ならば、\(a^k \equiv b^k \,(\mathrm{mod}\,n)\) である。
があります。これを利用して計算しましょう。
\(n \equiv 0 (\mathrm{mod}\, 3)\)のときは、合同式の性質から\(n^n \equiv 0^n \equiv 0 (\mathrm{mod}\, 3)\)です。
\(n \equiv 1 (\mathrm{mod}\, 3)\)のときは、合同式の性質から\(n^n \equiv 1^n \equiv 1 (\mathrm{mod}\, 3)\)です。
\(n \equiv 2 (\mathrm{mod}\, 3)\)のときは、\(n \equiv -1 (\mathrm{mod}\, 3)\)と言い換えられます。合同式の性質から\(n^n \equiv (-1)^n (\mathrm{mod}\, 3)\)です。
さらに、\(n\)が奇数のときは\((-1)^n \equiv -1 \equiv 2 (\mathrm{mod}\, 3)\)で、\(n\)が偶数のときは\((-1)^n \equiv 1 (\mathrm{mod}\, 3)\)となります。
以上、\(n^n\)を\(3\)で割ったあまりの規則性、その証明について紹介してきました。
合同式の性質を知っていると簡単に解ける問題で、合同算術の威力を知るのにちょうど良いと思います。
木村すらいむ（@kimu3_slime）でした。ではでは。
(2012T)
¥5,437
