この記事は仮面ライダービルドの数式の第3話です。

\frac{2^n+1}{n^2}∈N\\
n=3

これは1990年のIMO(国際数学オリンピック)の問題です。
∈Nは左の式の値が自然数になる、という意味で、これを満たすnの値はn=1,3となります。
IMOの問題ではnは１より大きい自然数、という制限が入っているのですが、その辺の説明はカットされていますね。
(そもそも、nに無理数や複素数を認めると無数に解はあります。)
この式を解くためには、この式がn>3の範囲では絶対に自然数にならない、ということを示す必要があります。

この問題はかなり難しく、正解率もかなり低かったらしいですが、
そもそもこんなレベルの問題を高校生に出すのもおかしいと思うんですよね。

こちらのリンクに解説があります。
https://mks.mff.cuni.cz/kalva/imo/isoln/isoln903.html

またこちらに解説動画あります。
今回はこちらを参考にしました。
https://www.youtube.com/watch?v=cmFzBFWzGvE&t=1163s

先に行っておくと、かなりエグいです。
この先は、覚悟した人だけ読んで下さい。

まず、分子は奇数なので、分母も奇数です。ですから、nは奇数です。
そのため、以下の式でnを置き換えます。

n=3^{k}m \qquad2 \nmid m, 3 \nmid m

後ろの記号はmは2でも3でも割り切れない、という意味です。
要は、nを素因数分解して、3とそれ以外に分けます。
そして、$n>3$で成り立たない事を証明するため、k=0,1でm=1であることを証明します。

まず、kの値を計算します。

\frac{2^n+1}{n^2}=\frac{2^{3^km}+1}{(3^km)^2}=\frac{3^{k+1}x}{3^{2k}m^2} \qquad x \nmid 3\\
\\
\therefore k+1  \geq 2k, \qquad k=0,1

分子の式がなぜこんな変形ができるのかは後述します。
分子も分母も3の素因数の数が確定して、
分母のほうが多くないといけないので、k=0,1が確定します。

そして、mが5以上の素数を持たない証明をして、m=1が確定します。

よって、n=1,3が確定します

$2^{3^km}+1=3^{k+1}x$の理由

$n=3^{k}m$ を使って、$n^2+1$を計算しますが、その前に$u=2^m$と置きます。

\begin{align}
u^{3^{k}}+1&=u^{3^{k}}+1^3\\
&=(u^{3^{k-1}}+1)(u^{2\times3^{k-1}}-u^{3^{k-1}}+1)\\
\end{align}\\
\because a^3+b^3=(a+b)(a^2-ab+b^2)

$a^3+b^3$の式を使って、因数分解しました。

ここで重要なことは、$k$の数を1つ減らせば因数分解できる、ということです。
$k$の数が0になるまで、因数分解を繰り返します。
一旦、右の気持ち悪い式は$M_{k-1}$と置き換えて隠しましょう。

\begin{align}
u^{3^{k}}+1&=(u^{3^{k-1}}+1)(u^{2\times3^{k-1}}-u^{3^{k-1}}+1)\\
&=(u^{3^{k-1}}+1)M_{k-1}\\
&=(u^{3^{k-2}}+1)M_{k-2}M_{k-1}\\
&\ldots\\
&=(u+1)M_1 \ldots M_{k-2}M_{k-1}
\end{align}\\

では、$u=2^m$をもとに戻します。

\begin{align}
u^{3^{k}}+1&=(u^{3^{k-1}}+1)(u^{2\times3^{k-1}}-u^{3^{k-1}}+1)\\

(u+1)M_0 \ldots M_{k-1}&=(2^n+1)M_1 \ldots M_{k-1}\\
M_0&=2^{2m}-2^m+1=4^{m}-2^m+1\\
M_{k-1}&=4^{m\times 3^{k-1}}-2^{m\times3^{k-1}}+1
\end{align}\\

これらの各パーツを9で割った余りを計算します。

m	$2^m \ (mod \ 9)$	$2^m+1 \ (mod \ 9)$
1	2	3
2	4	5
3	8	0
4	7	8
5	5	6
6	1	2
7	2	3

| m | $4^m(mod \ 9)$ |$2^m(mod \ 9)$ | $4^m-2^m+1 \ (mod \ 9)$ |
|:-:|:-:|:-:|:-:|:-:|
| 1 | 4 |2 |3 |
| 2 | 7 |4 |4 |
| 3 | 1 |8 |-6 (3) |
| 4 | 4 |7 |-2 (7) |
| 5 | 7 |5 |3 |
| 6 | 1 |1 |1 |
| 7 | 4 |2 |3 |

いずれも6周期で循環しています。
ここで、mが2でも3でも割り切れない、を思い出すと、mを6で割った余りは1か5です。

すると、先程の表の1と5の欄をみると、いずれも3か6になっています。

これらのパーツは9で割ると、3か6が余るということは、
どのパーツも3の素因数が1つだけ持つことがわかります。
もし、3の素因数を2つ以上持つと、9で割ったときに0になります。

このパーツは、u+1が1個、Mがk個で合計k+1個あるので、$3^{k+1}$の素因数を導けます。

mが5以上の素因数を持たない理由

mを素因数分解した時、一番小さい数をpとします。

2^n+1 | n^2 \\
2^n+1 | p

$2^n+1$はpで割れます。
よって以下の式が成り立ちます。

2^n \equiv -1 (mod p)\\
\\
2^{2n} \equiv 1 (mod p)\\
2^{p-1} \equiv 1 (mod p)

下はフェルマーの小定理と言われる式です。
ここで、以下の式を考えます。

2^y \equiv 1 (mod p)\\
※y=gcd(2n, p-1)

yは2nとp-1の最大公約数とします。
すると以下の式が成り立ちます。

2n | y,\  p-1 | y

つまり、yは2nでもp-1を割り切れる数です。
ところが、pはmの中で最も小さい数ですから、p-1とmは互いに素です。
n=m, 3mなので、2n=6mですが、mでは割れないので、yは6の約数でy=1,2,3,6です。

yの値がわかったのでpを求めます。

2^y \equiv 1 (mod \ p)\\

2^y - 1 \equiv 0 (mod \ p)\\

2^1-1=1\\
2^2-1=3\\
2^3-1=7\\
2^6-1=63\\

3は最初に除外してますし、pは素数なので、候補はp=7だけです。
p=7を検証します。

n	$2^n+1 (mod \space 7)$
0	1
1	3
2	5
3	2
4	3
5	5
6	2
7	3

2^n+1は7で割れません。
よって、mが小さい素数を持たない、m=1であることが確定します。