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 (mod p)$

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

$a^{p - 1} \equiv 1 (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 整数の積として知られる形と一致します。

式	指数から 1 引いた数	割り切れる数
$n^{3} - n$	$2$	$6$
$n^{5} - n$	$4$	$30$
$n^{7} - n$	$6$	$42$
$n^{13} - n$	$12$	$2730$

例：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$ 。

$2^{2024} = (2^{12})^{168} \times 2^{8} \equiv 1^{168} \times 2^{8} = 256$

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

例：3 の 100 乗を 7 で割る

$3^{6} \equiv 1 (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$ 。

$a^{p - 1} \equiv 1$ が使えるのは、 $a$ が $p$ の倍数でないときだけです。

$a$ が $p$ の倍数なら余りは最初から $0$ 。この場合は $a^{p} \equiv a$ の形で押さえる。

例：一の位を求める

一の位は $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$ 個。数が合っていれば拾い漏れはありません。

$n^{11} - n$ がすべての整数 $n$ で割り切れる最大の数はどれですか。

22
66
2310

__RESULT__

$10$ の約数は $1, 2, 5, 10$ 。 $1$ を足すと $2, 3, 6, 11$ で、素数は $2$ 、 $3$ 、 $11$ の 3 つです。積は $66$ になります。 $22$ は $3$ を拾い落とした値、 $2310$ は $11$ 以下の素数を全部掛けた値にあたります。

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

参考文献

Fermat's little theorem - Wikipedia

Petit théorème de Fermat - Wikipédia

Kleiner fermatscher Satz - Wikipedia

$2730 = 2 \times 3 \times 5 \times 7 \times 13$ の 5 つは、$12$ の約数に $1$ を足して素数になったものです。$p-1$ が $12$ を割れば $n^{12} \equiv 1 \pmod p$ が成り立つ、それだけで $n^{13}-n$ が $p$ で割り切れる。$4$ だけが素数にならず落ちます。同じ数え方で $n^5-n$ は $30$、$n^7-n$ は $42$。後半は余りの周期で、$2^{12} \equiv 1 \pmod{13}$ から $2^{2024}$ の余りが $9$ と出る計算、一の位を求めるときに定理が使えない理由まで扱いました。