文献あり

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

190

はじめに

この記事では合同方程式$x^k\eq1\p{p^e}$の$\gcd(k,p-1)\leq2$における解を求めます。
具体的には以下の結果が得られます。

$p$を素数、$k,e,e'\;(0\leq e'\leq e-1)$を自然数とし$k'=\gcd(k,p^{e-1}(p-1))=p^\e,2p^\e$とする。
ただし$p=2$のときは$1\leq e'\leq e-2,k'=\gcd(k,2^{e-2})=2^{e'}$とする。
このとき合同方程式$x^k\eq1\p{p^e}$は$x^{k'}\eq1\p{p^e}$と同値で、その解は以下のように求められる。

$p=2$のとき
$x^{2^{e'}}\eq1\p{2^e}$の解は$x\eq\pm(1+2^{e-e'}j)\p{2^e}\;(0\leq j<2^{e'})$で尽くされる。
$p\geq3$のとき
$x^{p^\e}\eq1\p{p^e}$の解は$x\eq1+p^{e-e'}j\p{p^e}\;(0\leq j< p^\e)$で尽くされ、
$x^{2p^\e}\eq1\p{p^e}$の解は$x\eq\pm(1+p^{e-e'}j)\p{p^e}\;(0\leq j< p^\e)$で尽くされる。

(なお原始根の公式でもない限り$\gcd(k,p-1)\geq3$のときの一般的な結果については得られないものと思われます。)
そしてこの系として以下の事実が成り立ちます。

$p\nmid a$なる任意の整数$a$に対して法$p^e$において$a^{k''}$が取りうる値を考えると

$p=2$のとき($0\leq e'< e-2$とする)
$a^{2^{e-e'-2}}\eq1+2^{e-e'}j\p{2^e}\;(0\leq j<2^{e'})$が成り立つ。
$p\geq3$のとき
$a^{p^{e-e'-1}(p-1)}\eq1+p^{e-e'}j\p{p^e}\;(0\leq j< p^\e)$が成り立ち、
$a^{p^{e-e'-1}\frac{p-1}{2}}\eq\pm(1+p^{e-e'}j)\p{p^e}\;(0\leq j< p^\e)$が成り立つ。

この系はなかなか面白いもので、
例えば$p=2,e=5,e'=2$とすると、任意の奇数$x$に対して
$x^2\eq1,1+8,1+16,1+24\eq1,9,17,25\p{32}$
が成り立つことがわかり、例えば$p=3,e=3,e'=1$とすると$3$の倍数でない任意の整数$x$に対して
$x^3\eq\pm1,\pm(1+9),\pm(1+18)\eq\pm1,\pm10,\pm8\p{27}$
が成り立つことがわかります。
これらの剰余関係が一々$x$に$1$から$p^e-1$までの値を代入して確かめなくても簡単にわかるというのは楽なもので、例えば以下のような応用が思い付きます。

$x,y,z$を$0$でない正数とし、もしも等式$x^3+y^3=z^3$が成立しているならば、$x,y,z$のうち少なくとも一つは$3$の倍数であることを示せ。(1998 信州大)

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

導出のあらすじ

まず合同方程式$x^k\eq1\p{p^e}$と$x^{k'}\eq1\p{p^e}$の同値性を示し、その解の個数を求めます。
そして上で示した値が実際に合同方程式を満たすことと、それぞれが異なる剰余であることを示します。
最後にその剰余の数と解の個数が一致することを確認することで主張を得ます。

$x^k\eq1\p{p^e}$の解の個数

整数$x$が合同方程式$x^k\eq1\p{p^e}$を満たすことと$x^{k'}\eq1\p{p^e}$を満たすことは同値である。

乗法群の一般論より$x\in\ZZ{p^e}$が$x^k=1$満たすとき$x$の位数は$k$を割り切るということと、ラグランジュの定理より$x$の位数は$|\ZZ{p^e}|=p^{e-1}(p-1)$を割り切るということから$x^{\gcd(k,p^{e-1}(p-1))}=x^{k'}=1$を得る。
($p=2$のときは下の命題3で触れるように$\ZZ{2^e}$の元の最大位数は$2^{e-2}$であることから同様にしてわかる。)

$\ZZ{p^e}$の構造について

$p=2$のとき
ある位数$2^{e-2}$の元$r\in\ZZ{2^e}$があって任意の$x\in\ZZ{2^e}$に対して
$x=\pm r^{n}\;(0\leq n<2^{e-2})$の形に一意的に表せれる。
$p\geq3$のとき
ある位数$p^{e-1}(p-1)$の元$r\in\ZZ{p^e}$があって任意の$x\in\ZZ{p^e}$に対して
$x=r^n\;(0\leq r< p^{e-1}(p-1))$の形に一意的に表せれる。

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

合同方程式$x^{k'}\equiv1\p{p^e}$の解の個数は以下のようになる。

$p=2$のとき$2^{e'+1}$個
$p\geq3,k'=p^{e'}$のとき$p^{e'}$個
$p\geq3,k'=2p^{e'}$のとき$2p^{e'}$個

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

$x^k\eq1\p{p^e}$の解

$p=2$のとき
$x\eq\pm(1+2^{e-e'}j)\p{2^e}\;(0\leq j<2^{e'})$は合同方程式$x^{2^{e'}}\eq1\p{2^e}$を満たす。
$p\geq3$のとき
$x\eq1+p^{e-e'}j\p{p^e}\;(0\leq p^{e'})$は合同方程式$x^{p^{e'}}\eq1\p{p^e}$を満たす。
$x\eq\pm(1+p^{e-e'}j)\p{p^e}\;(0\leq p^{e'})$は合同方程式$x^{2p^{e'}}\eq1\p{p^e}$を満たす。

$\dis(1+p^{e-e'}j)^{p^{e'}}=1+\sum^{p^{e'}}_{n=1}\binom{p^{e'}}{n}p^{(e-e')n}$なので$\dis\binom{p^{e'}}{n}p^{(e-e')n}\eq1\p{p^e}$を示せばよい。

ルジャンドルの公式から
$\dis\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$であることに注意すると
$\dis\ord_p(\binom{p^{e'}}{n}p^{(e-e')n})=\ord_p(\frac{p^\e(p^\e-1)(p^\e-2)\cdots(p^\e-n+1)}{n!}p^{(e-e')n}) \\\geq\ord_p(p^\e)-\ord_p(n!)+\ord_p(p^{(e-e')n})=\e-(n-1)+(e-e')n \\=\e+(e-\e)+(e^\e-1)(n-1)\geq\e+(e-\e')=e$
を得る。

$\pm(1+p^{e-e'}j)\;(0\leq j< p^{e'})$は法$p^e$においてそれぞれ異なる剰余を持つ。

$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$は法$p^e$において異なる剰余を持つ。
また$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$であったので矛盾。
以上より主張を得る。

命題4と補題6から5で挙げた解の個数と方程式の解の個数が一致することがわかるので定理1を得る。

$a^{p^{e-e'-1}(p-1)},a^{p^{e-e'-1}\frac{p-1}{2}}$の剰余

定理 1

$p\nmid a$なる任意の整数$a$に対して法$p^e$において$a^{k''}$が取りうる値を考えると

$p=2$のとき($0\leq e'< e-2$とする)
$a^{2^{e-e'-2}}\eq1+2^{e-e'}j\p{2^e}\;(0\leq j<2^{e'})$が成り立つ。
$p\geq3$のとき
$a^{p^{e-e'-1}(p-1)}\eq1+p^{e-e'}j\p{p^e}\;(0\leq j< p^\e)$が成り立ち、
$a^{p^{e-e'-1}\frac{p-1}{2}}\eq\pm(1+p^{e-e'}j)\p{p^e}\;(0\leq j< p^\e)$が成り立つ。

$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)$が成り立ち、逆に命題4の証明から任意の$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=2$のとき
上と同様にしてある$j$があって$a^{2^{e-e'-2}}=\pm(1+2^{e-e'}j)$が成り立つが、$a^{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{p^e}$が成り立つが$(r^{j'})^{2^{e-e'-2}}\eq1\p{2^{e-e'}}$なので符号は正となることから主張を得る。