6 体Fp上の2次方程式[Fpにおける解]
f-denshi.com  最終更新日:

 有限体Fq上の2項方程式: xn−a = 0 の一般的な解法を得ることがこのページの目的です。ここでは,q = p (素数) の場合について,体Fp上(p:素数)の2項方程式,xn−a = 0 のFp上の解法について調べます。

1.体Fp上( p:素数≠2)の2次の2項方程式: x2=a 

[1] p = 2 のときは自明なので,p:素数≠2 として話を進めます。
    (↑ p=2のとき,体F2の元は,0と1だけで,2項方程式の解は,x2=0⇒x=0, x2=1 ⇒x=1 )

Fp上( p : 2以外の素数 ) の2次2項方程式,

x2 = a ; ( a∈Fp )                 ・・・・・・・・・・・・・・・・・・・・・・・・・・・ (1)

を解くことを考えます。まず,小さな p についてFp の元とその2乗の値を調べて,この方程式がどのようなときに解を持つのかシラミ潰しに調べてみましょう。  ↓クドイかもしれませんが怠慢は代数の大敵です

まず,体Fp のすべての元の2乗を計算します。

 p = 3のとき
a = 0 1 2
a2= 0 1 1
 p = 5 のとき
a = 0 1 2 3 4
a2= 0 1 4 4 1
 p = 7 のとき
a = 0 1 2 3 4 5 6
a2= 0 1 4 2 2 4 1

[2] このような表を作れば,方程式(1)に根が存在する場合を拾い出すことができます。例えば,p=7 のときは,f(x)=x2−a として,

 x2=a ( a∈F7 ) の解は, 

(1) a = 0,1,2,4  → f(x) は F7 に根をもち,
      x2 = 0   →  根は 0
      x2 = 1   →  根は 1 と 6
      x2 = 2   →  根は 3 と 4
      x2 = 4   →  根は 2 と 5

(2) a = 3,5,6  → f(x) は F7 に根をもたない 

ということがわかります。同様にF7上の2項n次方程式の解は,下記の原始根表を見れば,すべて見つけることができます。

n= 0 1 2 3 4 5 6
r=0 * 0 0 0 0 0 0
1 1 1 1 1 1 1 1
2 1 2 4 1 2 4 1
3 1 3 2 6 4 5 1
4 1 4 2 1 4 2 1
5 1 5 4 6 2 3 1
6 1 6 1 6 1 6 1
n = 0 1 2 3 4 5 6
3n 1 3 2 6 4 5 1
a  = 1 2 3 4 5 6
ind 3(a) = 0 2 1 4 5 3
F7の rn の計算結果 (原始根は3,5) r=3 の指数

次に,この結果をふまえてシラミつぶしによらない一般的な解法を考えましょう。

[3] まず,原始根 r に関する指数[#]に着目します。 F7に おける原始根の一つ r=3 に関する a∈F7* の指数を上(右赤字)に示します。

 ind 3(a) と a とは1対1で対応していることが分かるので,

x2=a 

を解く代わりに,この両辺の指数が等しいとおいて

2×ind 3(x) ind 3(a)    ( mod 6 )   ←Fpの積は mod p-1 で考える

を解くこと(1次合同式)に問題を置き換えられます。 この合同式の解法の中に出てくる解の存在条件は,そのまま今考えている2項方程式の解の存在条件にもなるので,先に進む前に必ずこちらで勉強して下さい。 ⇒ [Appendix3]

[4] では,実際にこの方針で

x2=2  

を解いて見ましょう。 a=2 ⇒ ind 3(2)=2 に注意して指数の方程式で表すと,

2×ind 3(x) =2    ( mod 6 )

これをAppendix3の方法で解くと,ind 3(x)=1,4 を得ます。すなわち,

x ={31,34} = {3,4}  (mod 7)

F7 上の根として求まりました。

問題
F7上の方程式 x5=2 を上記2通りの方法でもとめよ。(解はx=4)


2.体Fp上( p:素数≠2 ) のn次の2項方程式: xn = a 

[1] 2項方程式の場合,n=2 より大きい場合にも簡単に一般化できるので,その結果を示します。 

定理  [ xn−a = 0 の一般的な解法 ]

Fp 上の方程式
xn−a=0   ・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・(1)

が,Fp において根をもつための必要十分条件は,

a,x の原始根 r に関する指数を,α=indr(a),χ=indr(x) とするとき,

( n,p-1 )=d

がαの約数であることである。このとき,合同式,

nχ ≡ α  ( mod p-1 )

の解を χ1,χ2,・・・,χd とすれば,もとの方程式の解は,

χ1,rχ2,・・・,rχd

の d 個である。

説明  (Appendix3を理解していれば自明です。)

 xn = a の両辺について r に関する指数をとると

ind r(xn) = ind r(a )   ( mod p-1 )
              ↓
n ×ind r(x ) ≡ ind r(a ) ( mod p-1 ) 

ここで,χ=ind r(x),α=ind r(a)とおくと,

n×χ≡α        (mod p-1)

この方程式を Apendix3 の解法で解くと,(n,p-1) = d  が αの約数ならば解は存在する。それを

α1,α2,・・・,αd

とすると,xn−a = 0  の解として

x=rα1,rα2,・・・,rαd

の d 個の解が得られる。


問題: n=2,p=7,r=3, a=2 で上の定理を確かめてください。


3.xn−1=0 の解法

[1] a=1 の特殊な場合です。

定理
(1) Fp 上の方程式 xn−1=0 

が,Fp において1以外の根をもつための必要十分条件は,

  (p−1,n) > 1

つまり,p -1と n の最大公約数が 1 より大きいことである。

(2) 特に n が p-1の約数で,

  p−1 = sn,    s : 正整数

と表せるとき,解は原始根のひとつを r とすれば,

  1,rs,r2s,・・・,r(n-1)s

の n 個である。

[2] (1)の証明
[必要性] 背理法を使います。

Fp の1以外の元をα( つまりαn=1 )とし,( p,n ) = 1 が成り立っているとする。
このとき,

(p−1)x+nY = 1

をみたす,整数 x,Y が存在します。したがって,

  α1=α(p−1)x+nY
    =(α(p−1)x(αn
    =1          (フェルマーの定理 αp−1= 1 を用いた[#]

となって矛盾します。すなわち,( p,n )>1

[3] [十分性] ( p-1,n )> 1 より,整数 s,t,d が存在して,

  p−1 = sd, n = td, s と t は互いに素,d > 1 ・・・・・・・・・・・・・・・・・・・ [*]

とおくことができる。このとき,s<p−1 (=sd) なので原始根を r とすると

  rs≠1

かつ,

  (rsn =rstd =(rsdt =(rp-1t =1   (原始根→[#])

したがって,rs は方程式 xn−1=0 の1以外の根である。
すなわち,( p-1,n ) > 1 ならば,方程式 xn−1 = 0 は 1 以外の根をもつ

[4] (2)の証明
 さらに[*]で t=1 のとき ( d=n )は,

  p−1=sn ,( もちろん,s<p−1, n<p−1 )

なので ,r が原始根で,p-1乗して(つまり,ns乗して)初めて1 になる(**) ことに注意すれば,

  [T] rs ,r2s,r3s,・・・・,r(n-1)s はすべて1ではない。

また,(rksn = (rsnk = (rp-1k = 1, ( k=1,2,・・・,n-1 ) より,

  [U] rs ,r2s,r3s,・・・・,r(n-1)s は,すべて xn−1=0 の根になっている。

さらに,もし,ris = rjs ( 1 ≦ i < j ≦ n-1 ) ならば,

   0 = rjs−ris = ris(r(j-i)s−1)

より,r(j-i)s = 1,( 1≦j-i≦n-2<p-1 ) となり,(**) に矛盾する。 したがって,

  [V] rs ,r2s,r3s,・・・・,r(n-1)s は互いにすべて異なる。

また,定理 [#] より

  [W] n次方程式の根の数はn個以下である

以上より,(2)が証明されました。


問題

F7上の方程式 x3=1 の解をもとめよ。  ( 答え 1,2 (=32=54),4 (=34=52) )

 



 [目次へ]