2^n-1の素因数についての補題

まず任意の素数$p$に対して${\mathrm{\Phi }}_p(2)={\displaystyle \frac{2^p-1}{2-1}}\equiv 3(\mathrm{mod}4)$でありかつ${\mathrm{\Phi }}_1(2)\equiv 1(\mathrm{mod}4)$である.
$n$が平方因子を持たない,すなわち相異なる素数$p_1,p_2,...,p_k$が存在して$n={\displaystyle \prod _{i=1}^k{p}_i}$となるとき,${\mathrm{\Phi }}_n(2)\equiv 3(\mathrm{mod}4)$であることを示そう. まず$k=1$の場合は先に示した通り成り立つ.$k=1,2,...,a-1$の場合にこれが成り立つとすれば,$n={\displaystyle \prod _{i=1}^a{p}_i}$であるとき,

$${\mathrm{\Phi }}_n(2)={\displaystyle \frac{2^n-1}{{\displaystyle \prod _{d|n,d\ne n}{\mathrm{\Phi }}_d(2)}}}\equiv {\displaystyle \frac{3}{1\times 3^{d(n)-2}}}\equiv {\displaystyle \frac{3}{3^{2^a-2}}}\equiv 3(\mathrm{mod}4)$$となり帰納的に示される.
$n$が平方因子を持つ場合,すなわち相異なる素数$p_1,p_2,...,p_k$と少なくとも$1$つは$2$以上である正整数$e_1,e_2,...,e_a$が存在して$n={\displaystyle \prod _{i=1}^a{p}_i^{e_i}}$となるとき,${\mathrm{\Phi }}_n(2)\equiv 1(\mathrm{mod}4)$であることを示そう.
$N_k$を$k$番目に小さい平方因子をもつ正整数であるとすれば,$N_1$より小さい正整数は全て平方因子を持たないので,$${\mathrm{\Phi }}_{N_1}(2)={\displaystyle \frac{2^{N_1}-1}{{\displaystyle \prod _{d|N_1,d\ne N_1}{\mathrm{\Phi }}_d(2)}}}\equiv {\displaystyle \frac{3}{{\displaystyle \prod _{d|rad(N_1),d\ne (N_1)}{\mathrm{\Phi }}_d(2)}}}\equiv 3\times 3^{d(rad(N_1))-1}=3^{2^a}\equiv 1(\mathrm{mod}4)$$
である.$k=1,2,3,...a-1$に対して${\mathrm{\Phi }}_{N_k}(2)\equiv 1(\mathrm{mod}4)$であるならば,$N_k$の$1$でない任意の約数$d$は平方因子を持つならば$N_k$より小さいので${\mathrm{\Phi }}_d(2)\equiv 1(\mathrm{mod}4)$であり,持たないならば${\mathrm{\Phi }}_d(2)\equiv 3(\mathrm{mod}4)$であるので,$${\mathrm{\Phi }}_{N_k}(2)={\displaystyle \frac{2^{N_k}-1}{{\displaystyle \prod _{d|N_k,d\ne N_k}{\mathrm{\Phi }}_d(2)}}}\equiv {\displaystyle \frac{3}{{\displaystyle \prod _{d|rad(N_k),d\ne (N_k)}{\mathrm{\Phi }}_d(2)}}}\equiv 3\times 3^{d(rad(N_k))-1}=3^{2^a}\equiv 1(\mathrm{mod}4)$$
である.以上より帰納的に示された.

対偶「$n^2+1$が平方因子を持たないならば,$(n+1)(8n^2+9)(2^{n^2+1}-1)$は平方数でない」を示す.$n^2+1$が平方因子を持たず,$(n+1)(8n^2+9)(2^{n^2+1}-1)$が平方数となるような正整数$n$の存在を仮定する.補題より,${\mathrm{\Phi }}_{n^2+1}(2)\equiv 3(\mathrm{mod}4)$であるので,ある$4$で割って$3$余る素数$p$が存在して,$v_p({\mathrm{\Phi }}_{n^2+1}(2))$が奇数となる.また平方剰余の第一補充測より,$n^2+1$は$4$で割って$3$あまる素因数を持たないので先に示したような$p$に対して,$\mathrm{mod}p$における$2$の位数は$n^2+1$となる.$p>n^2+1>n+1$より$n+1$は$p$で割り切れず,よって$8n^2+9$は$p$で割り切れる必要があるが,$8n^2+9\equiv 1(\mathrm{mod}4)$よりこれは$p$に等しくなく,また$p>n^2+1$より${\displaystyle \frac{8n^2+9}{p}}<{\displaystyle \frac{8n^2+9}{n^2+1}}<9$であり,かつ${\displaystyle \frac{8n^2+9}{p}}\equiv 3(\mathrm{mod}4)$より,${\displaystyle \frac{8n^2+9}{p}}$は$9$以下の$4$で割って$3$余る素数,すなわち$3$または$7$で割り切れるはずだが, $8n^2+9\equiv n^2+2(\mathrm{mod}7)$であるが,$\mathrm{mod}7$において$-2$と等しくなるような平方数は存在しないので$7$では割り切れない.よって$3p=8n^2+9$.が成立するはずだが,$v_3(8n^2+9)\geqq 2$と$8n^2+9$が$3$で割り切れることが同値であるので$3p$は$9$の倍数であるため$p=3$である必要があるが,このときこれを達成する$n$は存在しないので矛盾.よって示された.