0803786
2018/04/29(日) 18:36:40.20ID:daW9MuG1e を 2 以上の整数とする。
このとき、Z/(3^e)Z において 2 は原始根である。
証明
2 の位数を d とおく。
2^d≡1 (mod 3^e) より 2^d≡1 (mod 3)
したがって、d は偶数である。
また、d は φ(3^e)=2*3^(e-1) の約数である。
ここで、前補題より
2^(2*3^(e-2)) = 4^(3^(e-2)) ≡ 1+3^(e-1) ≠ 1 (mod 3^e)
(≠は「≡でない」を表すとする)
なので、d=2*3^(e-1) となるしかない。
したがって、2 は原始根である。□
定理
T を木、e を 2 以上の整数、k を 任意の自然数とする。
このとき、ある a∈T が存在して a≡k (mod 3^e) が成り立つ。
証明
・ k が 3 の倍数でない場合
3 の倍数でない b∈T を任意に取る。
2 が Z/(3^e)Z の原始根であることから、
b*2^d≡k (mod 3^e)
を満たす d∈N が存在する。
a=b*2^d とすればよい。
・ k が 3 の倍数である場合
3 の倍数でない b∈T を任意に取る。
2 が Z/(3^(e+1))Z の原始根であることから、
b*2^d≡3k+1 (mod 3^(e+1))
を満たす d∈N が存在する。
このとき、a=(b*2^d-1)/3 とおくと、
a∈T かつ a≡k (mod 3^e) となる。□