原子根の存在証明

この前話題に上がったので, 初等的証明を書いておきます. はてなブログで数式を扱う練習も兼ねて.

以下では p素数とします. フェルマーの小定理より a^{p-1}\equiv 1\pmod{p} というのが ap の倍数でなければ成り立つわけですが, ここで a^{d}\equiv 1\pmod{p} となるような最小の正の整数 da の mod p における位数と呼びます. \(a^{e}\equiv 0\) のとき \(e\) が \(d\) の倍数になることに注意. 位数がちょうど p-1 になるような a を原始根と呼び, このような原始根は各 p について存在することが知られています.

存在を証明しましょう. まずは簡単な補題から.

補題 a, bp の倍数でなく, ab の位数が互いに素のとき, ab の位数はその積である.

証明: a の位数を m, b の位数を n とする. ab の位数を cm+d (  0 \leq d\lt m ) とする. \[ 1 \equiv (ab)^{n(cm+d)}\equiv a^{nd} \pmod {p} \] であり, nm と互いに素なので, d=0 で \(ab\) の位数は \(m\) の倍数. 同様に \(n\) の倍数にもなる. \((ab)^{mn}\equiv 1\) は明らか. \(\square\)

この補題より, \(p-1\) の素因数分解の各項 (素べき) について, それを位数に持つ数がとれれば十分ですね.

\(s=q^{e}\) を \(p-1\) を割り切る素べき, \(t=\frac{p-1}{s}\) とする. \(x=1, 2, \ldots, p-1\) について, \({x^{t}}^{s}\equiv 1 \) である. ところで, 定数 \(k\) について \(x^{t}\equiv k\) なる \(x\) は高々 \(t\) 個しか存在しない (剰余の定理から従う) ので, \(x^{s}\equiv 1\) となる \(1\leq x\leq p-1\) は \(s\) 個以上存在する. これらの \(x\) の位数が \(q^{e}\) でないとすると \(q^{e-1}=s/q\) の約数なので, \(x^{s/q}\equiv 1\) でなければいけないが, この解は高々 \(s/q \lt s\) 個なので, 位数がちょうど \(q^{e}\) であるような \(x\) が存在する.

ということで示せました. 初等的ですね.

にしてもはてなブログに数式書くの面倒ですね.