LTEの補題とその応用

早速$n=kp^{v_p(n)}$の表示を用います.$n=kp^{v_p(n)},m=lp^{v_(m)}$とします.
$(1)$ $nm=kl\ p^{v_p(n)+v_p(m)}$であり,$kl$は$p$で割り切れないので,$v_p(nm)=e_p+f_p=v_p(n)+v_p(m)$となる.
$(2)$ 対称性から$v_p(n)\geq v_p(m)$としてよい.このとき$n+m=p^{v_p(m)}(kp^{v_p(n)-v_p(m)}+l) $となる.$()$の中身は整数なので$ap^e$($a,e$はそれぞれ$p$と互いに素な整数,非負整数)と書ける.よって$v_p(n+m)=v_p(m)+e\geq v_p(m)$となる.

まずは一般化の際に用いる方法を紹介する.
$x\equiv y\ (\mathrm{mod}\ p)$より,$x-y=kp^e$とする($k$は$p$で割り切れない)と,$e>0$であり,$v_p(x-y)=e$なので
\begin{align*}v_p(x^n-y^n)=&v_p(x^n-(x-kp^e)^n))\\ =&v_p(nkp^ex^{n-1}-{}_n\mathrm{C}_2k^2p^{2e}x^{n-2}+...-(-kp^e)^n)\\ =&v_p(kp^e)+v_p(nx^{n-1}-{}_n\mathrm{C}_2kp^ex^{n-2}+...+(-kp^e)^{n-1})\qquad(\because \text{補題1})\\ =&e+v_p(nx^{n-1}-{}_n\mathrm{C}_2kp^ex^{n-2}+...+(-kp^e)^{n-1}) \end{align*}
となる.
従って,$v_p(n)=v_p(nx^{n-1}-{}_n\mathrm{C}_2kp^ex^{n-2}+...+(-kp^e)^{n-1})$を示せば良いが,補題$1$の注意から$2$以上$n$以下の整数$l$に対して$v_p({}_n\mathrm{C}_l(kp^e)^{l-1}x^{n-l})>v_p(n)$を示せば良く, また$k,x$は$p$と互いに素なので,$v_p({}_n\mathrm{C}_lp^{e(l-1)})>v_p(n)$を示せば良い.ここでは整数の範囲で議論したいので少し不思議な変形をする.
\begin{align*} v_p({}_n\mathrm{C}_lp^{e(l-1)})+v_p(l)=&v_p(l{{}_n\mathrm{C}_lp^{e(l-1)}})\\ =&v_p(n{}_{n-1}\mathrm{C}_{l-1}p^{e(l-1)})\\ \geq&v_p({p^{l-1}})+v_p(n)=l-1+v_p(n) \end{align*}よってこれを移項すれば,$l-1>v_p(l)$を示せば良い.$b=v_p(l),l=ap^{b}$と置くと,$l\geq2$と$p>2$より$$ap^b-1\geq p^b-1>2^b-1=(1+1)^b-1\geq1+b-1=b$$最後から$2$番目の変形は$b\geq1$と二項定理を用いている.よって$v_p({}_n\mathrm{C}_l(kp^e)^{l-1})>v_p(n)$がわかったので補題$1$の$(2)$とその注意から,
\begin{align*} v_p(x^n-y^n)=&e+v_p(nx^{n-1}-{}_n\mathrm{C}_2kp^ex^{n-2}+...+(-kp^e)^{n-1})\\=&v_p(x-y)+v_p(n) \end{align*}

帰納法で証明する.証明$(1)$の様に二項定理を使うことも可能だが別の方法を使ってみる.まずはStep$1,2$で帰納法の準備をする.

Step1 $n$が$p$で割り切れないとき

$$v_p(x^n-y^n)=v_p(x-y)+v_p(x^{n-1}+x^{n-2}y+...+y^{n-1}) $$なので$v_p(x^{n-1}+x^{n-2}y+...+y^{n-1})=v_p(n)=0$すなわち,$x^{n-1}+x^{n-2}y+...+y^{n-1}$が$p$で割り切れないことを示せば良い.これは条件$x\equiv y\ (\mathrm{mod}\ p)$より$x^{n-1}+x^{n-2}y+...+y^{n-1}\equiv nx^{n-1}\not\equiv 0\ (\mathrm{mod}\ p)$であることから示される.

Step2 $n=p$のとき

Step$1$と同様な方針だが少しだけ異なってくる.
$$\begin{align}v_p(x^p-y^p)=&v_p(x-y)+v_p(x^{p-1}+x^{p-2}y+...+y^{p-1})\\ =&v_p(x-y)+v_p((x-y)(x^{p-2}+2x^{p-3}y+...+(p-1)y^{p-2})+py^{p-1}) \end{align}$$ここで補題$1$の注意より,$y$は$p$で割り切れないので,$(x-y)(x^{p-2}+2x^{p-3}y+...+(p-1)y^{p-2})$が$p$で$2$回以上割り切れることを示せば良い.これは$x-y$が$p$で$1$回以上割り切れることと$p$が奇素数であること,$x\equiv y\ (\mathrm{mod}\ p)$より,$$\begin{align}x^{p-2}+2x^{p-3}y+...+(p-1)y^{p-2}\equiv&x^{p-2}(1+2+...+(p-1))\\ \equiv&x^{p-2}\frac{p(p-1)}2\equiv0\ (\mathrm{mod}\ p) \end{align}$$であることから従う.

Step3 帰納法

$n=mp^{v_p(n)}$とし,$v_p(n)$の帰納法で.$v_p(x^n-y^n)=v_p(x-y)+v_p(n)...(1)$を示す.
$v_p(n)=0$すなわち,$n$と$p$が互いに素なとき.Step$1$より$(1)$は成り立つ.
$v_p(n)=k$のとき$(1)$が成立すると仮定する.$v_p(n)=k+1$のとき$n=mp^{k+1}$と書ける.従ってStep$2$と帰納法の仮定から$$\begin{align}v_p(x^n-y^n)=v_p((x^{mp^k})^p-(y^{mp^k})^p)=&v_p(x^{mp^k}-y^{mp^k})+1\\=&v_p(x-y)+k+1\\=&v_p(x-y)+v_p(n) \end{align}$$となり$v_p(n)=k+1$のときも$(1)$が成立する.以上より数学的帰納法から$v_p(x^n-y^n)=v_p(x-y)+v_p(n)$が示された.