第 9 章 方程式
10.2 有限体の原始根
以上は複素数の話であったが，今度は，有限体の原始根を定義する．pを 素数とし，有限体Fp={0,1,2,· · · , p−1}から0を除いた集合F∗pとかく：
F∗p={1,2,3,· · ·, p−1}.
フェルマの小定理より，任意のa∈F∗pはap−1= 1よりp−1乗根である：
つまりFpにおいて，aは多項式xp−1= 1の根である．
36 第10章 原始根 定義10.1
a∈F∗pに対して，an = 1となる最小のn(1≤n≤p−1)をaの位数と いう．
p= 3,5,7,の場合について，以下，各元のべき乗を少し調べてみよう．F∗3= {1,2}で，12= 1,22= 1である．
F∗5:
a a2 a3 a4
1 1 1 1
2 4 3 1
3 4 2 1
4 1 4 1
F∗7:
a a2 a3 a4 a5 a6
1 1 1 1 1 1
2 4 1 2 4 1
3 2 6 4 5 1
4 2 1 4 2 1
5 4 6 2 3 1
6 1 6 1 6 1
以上の表から観察できること：
• 一番右側の列はすべて1である．（これは「フェルマーの小定理」ap−1= 1 である．）
• どの元a∈F∗pに対してもap−1= 1となるが，1≤n < p−1となるnで an= 1となるものもある．（F∗5では，1,4がそうで，F∗7では，1,2,4,6 がそうである．）しかし，1 ≤n < p−1となるどのnでもan ̸= 1で，
n=p−1で初めてan = 1となるものもある．（F∗5では，2,3がそうで，
F∗7では，3,5がそうである．）
• an= 1となる最小のn(1≤n≤p−1)はp−1の約数になっている．
命題10.2
どんなa∈F∗pに対しても，aの位数はp−1の約数である．
証明: a∈F∗p, a̸= 1に対してaの位数をkとする．すなわち，am̸= 1 (1≤ m ≤k−1), ak = 1とする．k ≤p−1だから，p−1をkで割ってその余 りがrとすると，p−1 = kq+r(0 ≤r < k)と表せる（qは商）．このと き，r= (p−1)−kqなので，ar=a(p−1)−kq=ap−1(ak)−q = 1だから，も
しr̸= 0ならば，0< r < kよりaの位数がkであることに反する．ゆえに，
r= 0，すなわちkはp−1の約数である．
定義10.3
a∈F∗pに対して，aの位数がp−1であるものをFpの原始根という．
合同式を用いると次のようになる：
定義10.3’
pと互いに素な整数aが法pでの原始根であるとは，aがp−1乗して初 めて1と合同になるものをいう．
定理10.4
任意の素数pに対して，Fpの原始根は存在する．（唯一つではない，φ(n) 個ある．）
この定理の証明は長いので，別ノートにする．
命題10.5
Fpの原始根gに対して，gp−12 =−1(=p−1)である．
証明: x=gp−12 とおくと，フェルマの小定理より，x2=gp−1= 1である．ゆえ に，x=±1．しかし，gは原始根であるから，x̸= 1．ゆえに，x=gp−12 =−1.
原始根か否かのチェック方法
任意の素数pに対して，a∈F∗pの原始根か否かのチェックするには，1 とp−1以外のp−1の約数mで，amが1にならないことをチェックす ればよい．
例 26 • 3∈F13が原始根か否かを調べる．3の位数は，p−1 = 13−1 = 12 の約数なので，2,3,4,6乗を調べればよい．32= 9̸= 1,34= 3̸= 1,36=
27 = 1となる．したがって，3の位数は6であり，原始根ではない．
• 4∈F13が原始根か否かを調べる．4の位数は，p−1 = 13−1 = 12の 約数なので，2,3,4,6乗を調べればよい．42= 3̸= 1,44= 9̸= 1,46=
27 = 1となる．したがって，4の位数は6であり，原始根ではない．
5も原始根でないことがすぐ分かる．
• 6∈F13が原始根か否かを調べる．6の位数は，p−1 = 13−1 = 12の 約数なので，2,3,4,6乗を調べればよい．62= 10̸= 1,64= 9̸= 1,66= 12 =−1̸= 1となる．したがって，6の位数は12であり，原始根である．
38 第10章 原始根 演習問題10
1. (1)F11において2は原始根であることを証明せよ．
(2)F13において2は原始根であることを証明せよ．
(3)F17において2は原始根でないことと，3は原始根であることを証 明せよ．
2. (1) 1 + 2 + 22+ 23+· · ·+ 2100を11で割ったあまりを求めよ．
(2) 1 + 2 + 22+ 23+· · ·+ 2100を13で割ったあまりを求めよ．
(3) 1 + 3 + 32+ 33+· · ·+ 3100を17で割ったあまりを求めよ．
3. 問2(1)より定理を1つ作ってみよ．またそれを証明せよ．
4. 有理数 1
17の小数展開を筆算で計算して，小数第何位で循環し始めるか 観察せよ．一方，F17において10は原始根であることを証明せよ．
5. 問4より定理を1つ作ってみよ．証明はしなくて良い．
解法のヒント：例えば，1 (1)では，F11においては，位数はp−1 = 11−1 = 10の約数なので，1,2,5を調べればよい．22̸= 1,25̸= 1ならば，自動的に2 はF11の原始根となる．
例 27 上の乗積表より，F5の原始根は2,3の2つで，F∗5={2,22,23,24}= {3,32,33,34}であり,F7の原始根は3,5の2つで，F∗7={3,32,33,34,35,36}= {5,52,53,54,55,56}であることがわかる．
注意 18 F∗pは自然に群の構造を持つが，上に見たように原始根のべき乗です べての元が表される．そのような群を1つの元で生成された群だから「巡回 群」(cyclic group)といい，今の場合原始根rで生成されるからF∗p =< r >
と書く．F∗p =<2>またF∗5 =<3>でもあり，F∗7 =<3>でF∗7=<5 >
でもある．
第 11 章 指数
（前回の復習）pを素数とし，有限体Fp={0,1,2,· · ·, p−1}から0を除 いた集合F∗pに原始根とよばれる元が存在する（唯一つではなく，複数個）.
a∈F∗p に対して，最初にan= 1となるn >0をaの位数といい，ord(a) で表す．
命題11.1
Fpの一つの原始根をrとすると，F∗pのすべての元はri(0≤i≤p−2) という形に書ける：F∗p ={r0, r, r2, r3,· · · , rp−2}．ただし，r0= 1と約
束する．
証明: 原始根とは位数p−1の元である: ord(r) =p−1．今，1≤i, j < p−1 でri=rjとなったとすると(j≤i)，ri−j= 1だから，i−jはp−1の倍数 である．1≤i, j < p−1よりi=jである．
よって，{r0, r, r2, r3,· · ·, rp−2}は個数がp−1の集合だから，F∗p={r0, r, r2, r3,· · · , rp−2} となる．
定義11.2
a∈F∗pに対して，a=rkとなるk(0≤k≤p−1)が唯一つ定まる．こ れを
indr(a)
と表しa∈F∗pの原始根rに関する指数という．
注意: どんな原始根に関しても1の指数は0である：indr(1) = 0.
F5の原始根は2,3の2つだから，それぞれの原始根に関する1,2,3,4の指 数を求めてみよう．
表
a 2 3
a2 4 4 a3 3 2 a4 1 1
から，以下のようになる：
40 第11章 指数
a 1 2 3 4
ord(a) 1 4 4 2 ind2(a) 0 1 3 2 ind3(a) 0 3 1 2
例 28 F7の原始根は3,5の2つだから，それぞれの原始根に関する1,2,3,4,5,6 の指数を求めてみよう．
a 3 5
a2 2 4 a3 6 6 a4 4 2 a5 5 3 a6 1 1
から，以下のようになる：
a 1 2 3 4 5 6
ord(a) 1 3 6 3 6 2 ind3(a) 0 2 1 4 5 3 ind5(a) 0 4 5 2 1 3
補題
Fpの任意の原始根rに対して，rn= 1ならばnはp−1の倍数である．
合同式の言葉では，rn≡1(modp)ならば，nはp−1の倍数である．
証明: n = q(p−1) +k (0 ≤ k < p−1)とする．1 = rn = rq(p−1)rk = (rp−1)qrk =rkで，0≤k < p−1なので，k= 0でなければならない．
指数indr(a)はその定義の仕方から対数logに似ているが，それを以下の 命題で示す：
命題11.3
Fpの一つの原始根をrを一つ固定する．このとき
• indr(ab)≡indr(a) + indr(b) (modp−1)
• indr(an)≡n×indr(a) (modp−1) が成り立つ．
証明:indr(a) =m,indr(b) =n,indr(ab) =kとおくと，rm=a, rn=b, rk = abである．rk =ab=rmrn=rn+mであるから，rk−(n+m)= 1である．「補 題」より，k−(n+m)はp−1の倍数，すなわち，k≡n+m (modp−1) である．これは，indr(ab)≡indr(a) + indr(b) (modp−1)に他ならない．
注意 19 対数法則log(ab) = log(a) + log(b)の証明も同じである．
定理11.4
Fpにおける原始根rを一つ決めておく．このとき，F∗pの元の位数は p−1
(p−1,indr(a)) で与えられる．
証明: (p−1,indr(a)) =s, p−1 =sk, m= indr(a) =sℓとおく．(k, ℓ) = 1 である．定義から，a=rm=rsℓである．ord(a) =tとおくと，at=rmt= rstℓ = 1でtはそのような最小の正の整数である．mt=sℓtはp−1の倍数 であることと合わせて，t=kである．ゆえに，ord(a) =t =k = p−1
s =
p−1 (p−1,indr(a)).
定理11.5
Fp-係数の方程式xn−1 = 0がFpのなかに1以外の根を持つための必 要十分条件は(n, p−1)>1が成り立つことである．特に，n|p−1のと き，根はn個あり，1つ原始根rを決めておけば，p−1 =nsとしたと き，根は1, rs, r2s,· · ·, r(n−1)sで与えられる．
証明: r∈Fpを原始根とする．xn−1 = 0がFpのなかに1以外の根を持つな らば(n, p−1)>1であることを，対偶の形で示す．そのため，(n, p−1) = 1 と仮定し，∀α ∈ Fp(αn = 1) =⇒ α = 1を示す．(n, p−1) = 1ならば，
nk+ (p−1)ℓ= 1となる, k, ℓ∈Zが存在する．よって，α=αnk+(p−1)ℓ= (αn)k(αp−1)ℓ= 1である．
逆に，(n, p−1) =d >1ならば，xn−1 = 0がFpのなかに1以外の根を持 つことを示す．n=dn′, p−1 =dmとおく．このとき，d >1よりm < p−1 なので，rm̸= 1で，(rm)n=rnm=rn′(p−1)= (rp−1)n′ = 1n′ = 1だから，
rmはxn−1 = 0の解である．
特に，n|p−1ならば，p−1 = nsとするとき，j = 1,2,· · ·, n−1 に 対して，rjsはF∗pの相異なる元で，(xjs)n = xjns = nj(p−1) = 1である．
方程式xn−1 = 0のFp-解は高々n個なので（第7回講義ノート命題3），
1, rs, r2s,· · ·, r(n−1)sが解のすべてである．
例 29 F7-係数の方程式x3−1 = 0の解は上の命題より存在し，p−1 = 3×2 なので，rをF7の任意の原始根とするとき，1, r2, r4が解である，r= 3な らば，1,32 = 2,34 = 4，r= 5ならば，1,52 = 4,54= 2であるから，解は 1,2,4である．
42 第11章 指数 演習問題11
1. F∗pはFpから0を除いたものである．
(1)F11において2は原始根である（演習問題8の1(1)）．各x∈F∗11 の2に関する指数ind2(x)と位数ord(x)を求めよ．
(2)F13において2は原始根である（演習問題8の1(2)）．各x∈F∗13 の2に関する指数ind2(x)と位数ord(x)を求めよ．
2. (1)F11においてx5−1 = 0を解け．
(2)F13においてx4−1 = 0を解け．
(3)F17においてx8−1 = 0を解け．
3. 1から12までの整数のうち，100乗して13で割ると余りが1になるも のをすべて求めよ．
第 12 章 2 項方程式
（今回の目的）Fp-係数の2項方程式xn=aの解がいつ存在し，解がある ときの解の記述が原始根と指数を使って解明できることを示す．
Fp-係数の2項方程式xn−a= 0を「2項方程式」という．前回，a= 1の 場合の解の存在条件と解の記述について調べた．今回は，a∈Fp, a̸= 0とし て方程式を考える．p= 2のときは，a∈F2, a̸= 0 =⇒a= 1なので，方程式 はxn= 1で解はもちろん存在しx= 1である．したがって，以下ではp >2 を奇素数としよう．
まず，F∗p の原始根の一つをrとして固定する．いま，xn = aをみたす x∈Fp, x̸= 0が存在するとしよう．k= indk(x)，x=rkとする．このとき，
indr(xn)≡n·indr(x) =n·k·indr(r) =nk≡indr(a) (modp−1).
したがってxn = aをみたすx ∈ Fp, x = rk が存在すれば，1 次合同式 nX ≡indr(a) (modp−1)に解X =kが存在する．
逆に，もし1次合同式nX ≡indr(a) (modp−1)に解X =kが存在すれ ば，x=rkとおくと，xn=aとなる．実際，nk−indr(a) =m(p−1)とす ると，xn = (rk)n =rnk =rindr(a)+m(p−1)=rindr(a)rm(p−1) =a·1 =aと なるから．
そして，1次合同式nX ≡indr(a) (modp−1)に解が存在するための必要 十分条件は(n, p−1)がindr(a)を割り切ることである．そのとき，1次合同式 nX ≡indr(a) (modp−1)の解は(n, p−1) =d個あり，X =k1, k2,· · · , kd
とすると，rk1, rk2,· · ·, rkdがxn =aのFp-解のすべてである．
44 第12章 2項方程式 Fp-係数の2項方程式xn =aの解法
F∗pの原始根rを一つとっておく．
• d= (n, p−1)を求める．
• indr(a)を求める．
• d|indr(a)ならば解はあり，そうでないなら解はない．
• d|indr(a)ならば，1次合同式nX ≡indr(a) (modp−1)の解をd 個求め，それらをX =k1, k2,· · ·, kdとすると，rk1, rk2,· · ·, rkd がxn=aのFp-解のすべてである．
例 30 F7における2項方程式x4= 2の解を求める．まず，F7の原始根3を とっておこう．このとき，2 = ind3(2)であり，(4,7−1) = 2なので，解は存 在する．次に，1次合同式4x≡2 (mod 6)を解く（解は2個ある）．x= 2,5 とすぐにわかり，x4= 2のF7における解は，32= 2,35 = 5の2つである．
（原始根として5をとってももちろん解は同じ．）
特にn= 2のときは，より簡単に以下のようになる．
Fp-係数の2次の2項方程式x2=aの解法
F∗pの原始根rを一つとっておく．
• (2, p−1) = 2である．（p >2は奇数だから．）
• indr(a)を求める．
• indr(a)が偶数ならば解はあり，奇数なら解はない．
• indr(a)が偶数のとき，1次合同式2x≡indr(a) (modp−1)の解 の1つは，x= indr(a)
2 で, したがって±rindr(a)2 がx2=aのFp -解である．
例 31 F7における2項方程式x2= 2の解を求める．ここでは，F7の原始 根5をとっておこう．このとき，4 = ind5(2)は偶数だから解は存在する．次 に，1次合同式2x≡4 (mod 6)を解く（解は2個ある）．x= 2,5とすぐに わかり，x2= 2のF7における解は，52 = 4,55= 3の2つである．（原始根 として3をとってももちろん解は同じ．）
最後にa=−1の場合を調べよう．Fpにおいてp−1を−1と表す．