インテジャーズ

インテジャーズ

数、特に整数に関する記事。

指数持ち上げ補題

次の補題を証明します:

指数持ち上げ補題 pを奇素数とし、pで割り切れない相異なる整数x, yx\equiv y \pmod{p}なる関係を満たすとき、任意の正整数nに対して
\mathrm{ord}_p(x^n-y^n) = \mathrm{ord}_p(x-y)+\mathrm{ord}_p(n)
が成り立つ。

ただし、0 \neq r \in \mathbb{Z}_{(p)}の一意的な表示r=p^km \ (m \in \mathbb{Z}_{(p)}^{\times})に対して、\mathrm{ord}_p(r):=kと定める。

証明. \mathrm{ord}_p(n)=kとして、n=p^kmと表す(p \nmid m)。因数分解

\displaystyle x^n-y^n=(x^{p^k}-y^{p^k})((x^{p^k})^{m-1}+(x^{p^k})^{m-2}y^{p^k}+\cdots +x^{p^k}(y^{p^k})^{m-2}+(y^{p^k})^{m-1})

の右辺の右側の因数を☆とする。Fermatの小定理により、x^{p^k} \equiv x \pmod{p}およびy^{p^k} \equiv y \pmod{p}が成り立つが、今 x \equiv y \pmod{p}なので、

\text{☆} \equiv mx^{m-1} \not \equiv 0 \pmod{p}

が成り立つ。すなわち、

\mathrm{ord}_p(x^n-y^n) = \mathrm{ord}_p(x^{p^k}-y^{p^k})

である。このように指数をpの冪のみにした上で、逐次的にk回素因数分解する:

\displaystyle {\small x^{p^k}-y^{p^k} = (x^{p^{k-1}}-y^{p^{k-1}})((x^{p^{k-1}})^{p-1}+(x^{p^{k-1}})^{p-2}y^{p^{k-1}}+\cdots + x^{p^{k-1}}(y^{p^{k-1}})^{p-2}+(y^{p^{k-1}})^{p-1})}

\displaystyle {\small x^{p^{k-1}}-y^{p^{k-1}} = (x^{p^{k-2}}-y^{p^{k-2}})((x^{p^{k-2}})^{p-1}+(x^{p^{k-2}})^{p-2}y^{p^{k-2}}+\cdots + x^{p^{k-2}}(y^{p^{k-2}})^{p-2}+(y^{p^{k-2}})^{p-1})}

\cdots

x^{p^2}-y^{p^2}=(x^p-y^p)((x^p)^{p-1}+(x^p)^{p-2}y^p+\cdots +x^p(y^p)^{p-2}+(y^p)^{p-1})

x^p-y^p=(x-y)(x^{p-1}+x^{p-2}y+\cdots +xy^{p-2}+y^{p-1})

これより、次の主張を証明すれば十分であることがわかる(X=x, x^p, \dots, x^{p^k}Y=y, y^p, \dots, y^{p^k}として適用すればよい):

主張 X \equiv Y\pmod{p}を満たすようなpで割れない整数X, Yに対して、
\mathrm{ord}_p(X^{p-1}+X^{p-2}Y+\cdots +XY^{p-2}+Y^{p-1}) = 1
が成り立つ。

しかし、pで割れない数Y^{p-1}で割ってやれば、次の主張'を証明すれば十分であることがわかる:

主張' X \equiv 1\pmod{p}を満たすような整数Xに対して
\mathrm{ord}_p(X^{p-1}+X^{p-2}+\cdots +X+1) = 1
が成り立つ。

f(X):=X^{p-1}+X^{p-2}+\cdots +X+1としよう。X \equiv 1 \pmod{p}なので、X=1+ptと整数tを用いて表せば

\begin{equation}\begin{split}f(X) &=(1+pt)^{p-1}+(1+pt)^{p-2}+\cdots +(1+pt)+1 \\ &\equiv p+\{(p-1)+(p-2)+\cdots +1\}pt \pmod{p^2} \\ &\equiv p+\frac{(p-1)t}{2}p^2 \pmod{p^2} \\ &\equiv p \pmod{p^2} \end{split}\end{equation}

を得る。ここで、p \neq 2であることを使った。これで、証明は完了している。 Q.E.D.