4

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

309
0
$$$$

まず以下のような問題を考えてみて欲しい.

$n$を正整数とする.$(n+1)(8n^2+9)(2^{n^2+1}-1)$が平方数ならば,$n^2+1$は平方因子を持つことを示せ.

ただし,正整数$N$が平方因子を持つとは,ある素数$p$が存在して$N$$p^2$で割り切れることを示す.










--------ネタバレ防止スペース--------









\

以下のような補題を紹介しよう.

$2$以上の整数$n$に対して,$n$が平方因子を持つことと$\Phi_n(2)\equiv1\pmod 4$は同値である.

まず任意の素数$p$に対して$\Phi_p(2)=\dfrac{2^p-1}{2-1}\equiv3\pmod 4$でありかつ$\Phi_1(2)\equiv1\pmod4$である.
$n$が平方因子を持たない,すなわち相異なる素数$p_1,p_2,...,p_k$が存在して$n= \displaystyle\prod_{i=1}^{k}p_i $となるとき,$\Phi_n(2)\equiv3\pmod 4$であることを示そう. まず$k=1$の場合は先に示した通り成り立つ.$k=1,2,...,a-1$の場合にこれが成り立つとすれば,$n=\displaystyle\prod_{i=1}^{a}p_i $であるとき,

$$\Phi_n(2)=\dfrac{2^n-1}{\displaystyle \prod_{d|n,d\not=n}\Phi_d(2) }\equiv\dfrac{3}{1×3^{d(n)-2}}\equiv\dfrac{3}{3^{2^a-2}}\equiv3\pmod 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} $となるとき,$\Phi_n(2)\equiv1\pmod4$であることを示そう.
$N_k$$k$番目に小さい平方因子をもつ正整数であるとすれば,$N_1$より小さい正整数は全て平方因子を持たないので,$$\Phi_{N_1}(2)=\dfrac{2^{N_1}-1}{\displaystyle \prod_{d|N_1,d\not=N_1}\Phi_d(2)}\equiv\dfrac{3}{\displaystyle \prod_{d|rad(N_1),d\not=(N_1)}\Phi_d(2)}\equiv3×3^{d(rad(N_1))-1}=3^{2^a}\equiv1\pmod4$$
である.$k=1,2,3,...a-1$に対して$\Phi_{N_k}(2)\equiv1\pmod4$であるならば,$N_k$$1$でない任意の約数$d$は平方因子を持つならば$N_k$より小さいので$\Phi_d(2)\equiv1\pmod4$であり,持たないならば$\Phi_d(2)\equiv3\pmod4 $であるので,$$\Phi_{N_k}(2)=\dfrac{2^{N_k}-1}{\displaystyle \prod_{d|N_k,d\not=N_k}\Phi_d(2)}\equiv\dfrac{3}{\displaystyle \prod_{d|rad(N_k),d\not=(N_k)}\Phi_d(2)}\equiv3×3^{d(rad(N_k))-1}=3^{2^a}\equiv1\pmod4$$
である.以上より帰納的に示された.

この補題を用いて冒頭の問題の解決を試みよう.

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

このように,平方因子というあまり着目されることのない要素を用いて整数に関する命題を示すことができます.あまり実用性はないかもしれませんが,面白いと思っていただければ幸いです.最後まで読んでいただきありがとうございました.



追記:冒頭の問題,$\mod 8$を見るだけで解決できましたね...よりこの補題を効果的に使えるような問題を思い付いたらここに貼り付けようと思います.
さらに追記:色々訂正+変更しました

投稿日:32
更新日:32
OptHub AI Competition

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。
バッチを贈って投稿者を応援しよう

バッチを贈ると投稿者に現金やAmazonのギフトカードが還元されます。

投稿者

W2TZMS
16
2219
初等整数論が好きです

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中