合同方程式 x^k≡1 (mod p^e)の解

　上の系において$p=3,e=2,e'=0$とすると$3$の倍数でない任意の整数$a$に対して
$$a^3\eq\pm1\p{9}$$
が成り立つので$3\nmid xyz$とすると
\begin{align} x^3+y^3 &\eq\pm1\pm1\\ &=0,2,-2\\ &\not\eq\pm1\eq z^3\p{9} \end{align}
となって矛盾。よって$3|xyz$を得る。

　群の一般論より$x\in\ZZ{p^e}$が$x^k=1$を満たすとき$x$の位数は$k$を割り切るということと、$|\ZZ{p^e}|=p^{e-1}(p-1)$より任意の$x\in\ZZ{p^e}$に対して$x^{p^{e-1}(p-1)}=1$が成り立つことから
\begin{align} x^k=1 &\iff\ord x\mid\gcd(k,p^{e-1}(p-1))\\ &\iff x^{k'}=1 \end{align}
を得る($p=2$のときは(下の命題からもわかるように)任意の$x\in\ZZ{2^e}$に対して$x^{2^{e-2}}=1$が成り立つことが知られているので$k'=\gcd(k,2^{e-2})$とできることがわかる)。

　 (Z/nZ)*の群構造 - INTEGERS 等を参照されたい。

• $p=2$のとき
  命題4のような$r$に対し、$x=\pm r^n$が$x^{2^{e'}}=r^{2^{e'}n}=1$を満たすことと$2^{e-2}\mid2^{e'}n$つまり$2^{e-e'-2}\mid n$を満たすことは同値である。そしてそのような$0\leq n<2^{e-2}$の取り方は
  $$n=2^{e-e'-2}j\quad(0\leq j<2^{e'})$$
  の$2^{e'}$通りあるので符号の取り方もあわせて$x$の取り方は$2^{e'+1}$通りあることになる。
• $p\geq3$のとき
  上と同様にして$x=r^n$が
  ・$x^{p^\e}=1$を満たすとき$n$の取り方は$n=p^{e-e'-1}(p-1)j\quad(0\leq j< p^{e'})$の$p^{e'}$通り
  ・$x^{2p^\e}=1$を満たすとき$n$の取り方は$n=p^{e-e'-1}\frac{p-1}2j\quad(0\leq j<2p^{e'})$の$2p^{e'}$通りあることになる。

　二項定理より
$$(1+p^{e-e'}j)^{p^{e'}}=1+\sum^{p^{e'}}_{n=1}\binom{p^{e'}}{n}p^{(e-e')n}$$
と表せるので
$$\binom{p^{e'}}{n}p^{(e-e')n}\eq1\p{p^e}$$
が成り立つことを示せばよい。
　いまルジャンドルの公式から
$$\ord_p(n!)=\sum^{\infty}_{i=1}\left\lfloor\frac{n}{p^i}\right\rfloor <\sum^{\infty}_{i=1}\frac{n}{p^i}=\frac{n}{p-1}\leq n$$
特に$\ord_p(n!)\leq n-1$が成り立つことに注意すると
\begin{align} \ord_p(\binom{p^{e'}}{n}p^{(e-e')n}) &=\ord_p\l(\frac{p^\e(p^\e-1)(p^\e-2)\cdots(p^\e-n+1)}{n!}p^{(e-e')n}\r)\\ &\geq\ord_p(p^\e)-\ord_p(n!)+\ord_p(p^{(e-e')n})\\ &\geq\e-(n-1)+(e-e')n\\ &=\e+(e-\e)+(e^\e-1)(n-1)\\ &\geq\e+(e-\e)=e \end{align}
を得る。

　$0\leq i< j< p^\e$において
$$0\leq1+p^{e-e'}i<1+p^{e-e'}j\leq1+p^{e-e'}(p^\e-1)< p^e$$
なので$1+p^{e-e'}i$と$1+p^{e-e'}j$は異なる剰余を持つ。
　また
$$1+p^{e-e'}i\eq-(1+p^{e-e'}j)\p{p^e}$$
が成り立つとすると、この両辺に$p^{e'}$を掛けることで
$$2p^{e'}\eq0\p{p^e}$$
となるので$e'\leq e-1$より$p=2,e'=e-1$でなければならないが$p=2$のときは$e'\leq e-2$としていたので矛盾。
　以上より主張を得る。

• $p\geq3$のとき
  $$x=a^{p^{e-e'-1}(p-1)},a^{p^{e-e'-1}\frac{p-1}2}$$
  は$x^{e'}\eq1$や$x^{2p^{e'}}\eq1$を満たすのである$j$を用いて
  $$x\eq\pm(1+p^{e-e'}j)\p{p^e}$$
  と表せ、逆に命題5の証明から任意の$j$に対しある$j'$が存在して
  $$\pm(1+p^{e-e'}j)\eq(r^{j'})^{p^{e-e'-1}(p-1)},(r^{j'})^{p^{e-e'-1}\frac{p-1}2}\p{p^e}$$
  が成り立つことから主張を得る。
• $p=2$のとき
  上と同様にある$j$が存在して
  $$a^{2^{e-e'-2}}\eq\pm(1+2^{e-e'}j)\p{2^e}$$
  と表せるが任意の奇数$x$に対し
  $$x^{2^{e-e'-2}}\eq1\p{2^{e-e'}}$$
  が成り立つことに注意すると符号は正となる。また任意の$j$にある$j'$が存在して
  $$1+2^{e-e'}j\eq\pm (r^{j'})^{2^{e-e'-2}}\p{2^e}$$
  が成り立つが
  $$(r^{j'})^{2^{e-e'-2}}\eq1\p{2^{e-e'}}$$
  なので符号は正となることから主張を得る。