n の 13 乗から n を引くと 2730 の倍数になる（フェルマーの小定理の応用）

$n^{13}-n$ は、$n$ がどんな整数でも $2730$ で割り切れます。$n=2$ なら $8190=2730\times 3$。

$2730=2\times 3\times 5\times 7\times 13$ です。この 5 つの素数がどこから来たのかが、問題の中身になります。

フェルマーの小定理

$p$ を素数とすると、どんな整数 $a$ についても次が成り立ちます^[1]。

$$a^p\equiv a(\mathrm{mod}p)$$

$a$ が $p$ の倍数でなければ、両辺を $a$ で割った形も使えます^[2]。

$$a^{p-1}\equiv 1(\mathrm{mod}p)$$

$a^{p-1}$ が $1$ に戻る。この「戻る」性質が、大きな指数を扱うときの足場になります。

5 つの素数がどこから来るか

$n^{13}-n=n(n^{12}-1)$ と書けます。素数 $p$ で割り切れるかを、$p$ ごとに見ます。

$n$ が $p$ の倍数なら、最初の因数で割り切れて終わり。そうでなければ $n^{12}-1$ を調べます。

$p-1$ が $12$ を割るとしましょう。$12=(p-1)m$ と書けるので、$n^{12}=(n^{p-1}{)}^m\equiv 1^m=1$。

つまり $n^{12}-1$ が $p$ で割り切れます。条件は $p-1$ が $12$ の約数であること、ただそれだけ。

$12$ の約数は $1,2,3,4,6,12$ の 6 個。$1$ を足すと $2,3,4,5,7,13$ で、$4$ だけが素数ではありません。

残る $2,3,5,7,13$ は互いに素なので、積の $2730$ でも割り切れます。

例：n の 5 乗と 7 乗

$n^5-n$ なら、$4$ の約数 $1,2,4$ に $1$ を足して $2,3,5$。積は $30$ です。

$n^7-n$ なら、$6$ の約数 $1,2,3,6$ に $1$ を足して $2,3,4,7$。$4$ が落ちて $2\times 3\times 7=42$。

$n^3-n$ なら $2$ の約数 $1,2$ から $2,3$ で、積は $6$。連続する 3 整数の積として知られる形と一致します。

例：n の 9 乗のとき

$8$ の約数は $1,2,4,8$。$1$ を足すと $2,3,5,9$ で、$9$ は素数ではありません。

残るのは $2,3,5$ で、積は $30$。$n^9-n$ は $30$ の倍数になります。

指数が大きくなれば強くなる、とは限らない。$9$ より小さい $7$ のほうが $42$ で、こちらが上回ります。

累乗の余りは周期でくり返す

$2^k$ を $13$ で割った余りを並べます。$2,4,8,3,6,12,11,9,5,10,7,1$ ときて、$12$ 個目で $1$ に戻る。

戻ったあとは同じ並びのくり返しです^[3]。周期が $12$ だと分かれば、指数は $12$ で割った余りだけを見れば足ります。

例：2 の 2024 乗を 13 で割る

$13$ は素数で $2$ はその倍数ではないので、$2^{12}\equiv 1$ が使えます。

指数を $12$ で割ります。$2024=12\times 168+8$。

$$\begin{array}{rl}{2}^{2024}& ={\left(2^{12}\right)}^{168}\times 2^8\\ & \equiv 1^{168}\times 2^8=256\end{array}$$

$256=13\times 19+9$ なので、答えは $9$ です。$2024$ 個の掛け算をせずに済みました。

例：3 の 100 乗を 7 で割る

$3^6\equiv 1(\mathrm{mod}7)$ です。$100=6\times 16+4$ なので、$3^{100}\equiv 3^4$。

$3^4=81=7\times 11+4$ で、余りは $4$。

$7^{222}$ を $11$ で割る場合も同じ手順です。$7^{10}\equiv 1$、$222=10\times 22+2$、$7^2=49=44+5$ で余りは $5$。

例：一の位を求める

一の位は $10$ で割った余りです。$10$ は素数ではないので、定理をそのまま当てられません。

代わりに周期を直接調べます。$7^k$ の一の位は $7,9,3,1$ の 4 つでくり返す。

$100$ を $4$ で割ると余り $0$ なので、$7^{100}$ の一の位は $1$。$3^{2024}$ も周期 $4$ で、余り $0$ から一の位は $1$ です。

$2^{2024}$ は $2,4,8,6$ の周期 $4$。ただし $2^0=1$ が並びに入らないので、$2024$ を $4$ で割った余り $0$ は 4 番目の $6$ にあたります。

周期は p - 1 の約数になる

$2^k\equiv 1$ となる最小の $k$ は、いつも $p-1$ とは限りません。$p-1$ の約数のどれかになります。

$3^k$ を $13$ で割ると $3,9,1$ で周期は $3$。$12$ の約数です。

だから $12$ で割った余りを見れば必ず正しく、周期がもっと短ければ計算がさらに楽になる。安全側は $p-1$ です。

検算のしかた

小さい指数で公式を試します。$2^{12}=4096$ で、$4096=13\times 315+1$。確かに $1$ に戻りました。

$n^{13}-n$ のほうは、$n=2$ で $8190$。$2730$ で割ると $3$ になり、割り切れています。

素数を集め忘れていないかも見ます。$12$ の約数は $6$ 個で、$1$ を足して素数になるのが $5$ 個。数が合っていれば拾い漏れはありません。

$p-1$ が指数を割る素数を拾い、掛け合わせる。手順が短いので、指数が変わっても同じ道で答えまで進めます。

参考文献