INTEGERS

数、特に整数に関する記事。

mod 1989

整数整数-1989

私は1989年生まれですが、 $1989$ の現れる問題を発見したので紹介します。

問題*1 $3$ 以上の整数 $n$ に対して合同式

$\displaystyle n^{n^{n^n}}\equiv n^{n^n} \pmod{1989}$

が成り立つことを示せ。

integers.hatenablog.com

で紹介されているCarmichaelの定理を用います。

証明. $n$ が奇数であれば

$n^n\equiv n \pmod{4} \tag{1}$

が成り立つ。理由: $n^n-n=n(n^{n-1}-1)$ であり、 $\lambda(4)=2 \mid n-1$ である。

$n^{n^n}\equiv n^n \pmod{3} \tag{2}$

理由: $n^{n^n}-n^n=n^n(n^{n^n-n}-1)$ であり、 $\lambda(3)=2 \mid n^n-n$ である。

$n\geq 3$ であれば

$n^{n^n}\equiv n^n \pmod{16} \tag{3}$

理由: $n$ が偶数のときは $n \geq 4$ より成立。 $n$ が奇数のときは $n^{n^n}-n^n=n^n(n^{n^n-n}-1)$ であり、(1)より $\lambda(16)=4 \mid n^n-n$ より成立。

(2)、(3)より $n\geq 3$ であれば $a=6, 12, 16$ に対して

$n^{n^n}\equiv n^n \pmod{a}$

が成り立つことが示された。

$\displaystyle n^{n^{n^n}}-n^{n^n}=n^{n^n}(n^{n^{n^n}-n^n}-1)$

なので、 $\lambda(9)=6, \ \lambda(13)=12, \ \lambda(17)=16$ に注意すると

$\displaystyle n^{n^{n^n}} \equiv n^{n^n} \pmod{b}$

が $b=9, 13, 17$ に対して成立する。 $1989=9\times 13 \times 17$ なので、中国式剰余定理より

$\displaystyle n^{n^{n^n}}\equiv n^{n^n} \pmod{1989}$

が示された。 Q.E.D.

*1:バルカン数学オリンピックの問題？