n^nを3で割ったあまりの規則性、証明

どうも、木村(@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)でした。ではでは。

 

Elementary Number Theory

Elementary Number Theory

posted with AmaQuick at 2021.02.02
Burton(著)
(2012T)
4.6outof5stars
¥5,437

 

こちらもおすすめ

倍数同士の和は同じ倍数となること、整数の合同modとは

合同式の性質を使った整数の余りの計算方法

組み合わせ・二項係数nCkの覚え方:パスカルの三角形