|
６ 体Ｆp上の2項方程式［Fpにおける解］ | |
| f-denshi.com 最終更新日： 21/08/02 | ||
| ［目次へ］ | ||
| サイト検索 | ||
有限体 Fq上の2項方程式 ： xn−a ＝ 0 のFp上の根を求める一般的な方法を得ることがこのページの目的です。ここでは，p （素数） の場合について，体 Fp上 の2項方程式，xn−a ＝ 0 の Fp上の解を求める方法について調べます。
［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乗を計算します。
ｐ ＝ 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次方程式の解は，下記の原始根表を見れば，すべて見つけることができます。
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| F7の rn の計算結果 (原始根は3，5) | r＝3 の指数 |
次に，この結果（上表）をふまえてシラミつぶしによらない一般的な解法を考えましょう。
［３］ F7* は原始根 r を生成元とする巡回群となっています。すなわち，F7* ＝＜3＞＝＜5＞。そこで，原始根 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) で考える
を解くこと （１次合同式を解くこと） に問題を置き換えられます。
この合同式の解法の中に出てくる解の存在条件は，そのまま今考えている2項方程式の解の存在条件にもなるので，先に進む前に必ずこちらで勉強して下さい。 ⇒ ［Appendix3］
［４］ では，実際にこの方針で，F7上の２項方程式
x2＝2 ［問題］
を解いて見ましょう。 a＝2 ⇒ ind 3（2)＝2 に注意して指数の方程式で表すと，
2×ind 3（x) ＝2 ( mod 6 )
これを Appendix3 の方法（ aX＝c で a=2，n=6 の最大公約数＝2，n’＝3 ）で解くと，ind 3（x)＝1，4 を得ます。すなわち，
x ＝｛31，34｝ ＝ ｛3，4｝ (mod 7)
が F7 上の根として求まりました。
問題
F7上の方程式 x5＝2 を Appendix3 の方法でもとめよ。（解はx＝4）
［1］ 2項方程式の場合，n＝2 より大きい場合にも簡単に一般化できます。
| 定理 ［ xn−a ＝ 0 の一般的な解法 ］ Fp 上の方程式 xn−a＝0 ・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・（1） が，Fp において根をもつための必要十分条件は， a，x の原始根 ｒ に関する指数を， α＝indr（a)， χ＝indr（x) とするとき， （ n，p−1 ）＝d がαの約数であることである。このとき，合同式， nχ ≡ α （ mod p−1 ） の解を χ1，χ2，・・・，χd とすれば，もとの方程式の解は， ｒχ1，ｒχ2，・・・，ｒχd の d 個である。 |
説明
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 個の解が得られる。
［1］ a＝1 の特殊な場合です。
| 定理 （1） Fp 上の方程式 xn−1＝0 が，Fp において1以外の根をもつための必要十分条件は， （n，p−1） ＞ 1 つまり，n と p -1 の最大公約数が 1 より大きいことである。 （2） 特に n が p-1の約数で， p−1 ＝ sn， s ： 正整数 と表せるとき，解は原始根のひとつを r とすれば， 1，ｒs，r2s，・・・，r(n-1)s の n 個である。 |
［2］ 定理-（1）の証明
［必要性］ 背理法を使います。
(1) Fp の 1 以外の元をα（ つまりαn＝1 ，α≠1） とし，（ p−1，n ） ＝ 1 が成り立っているとする。
(2) そのとき，
（p−1）x＋nＹ ＝ 1
を満たす整数 x，Ｙ が存在する[#]。したがって，
α1＝α（p−1）x＋nＹ
＝（α（p−1））x（αn）Ｙ
↓（フェルマーの定理 αp−1＝ 1 [#]）
＝1
となって矛盾する。よって，（ p，n ）＞1 である。
［３］ ［十分性］
(3) （ p-1，n ）＞ 1 より，整数 s，t，d が存在して，
p−1 ＝ sd， n ＝ td， s と t は互いに素，d ＞ 1 ・・・・・・・・・・・・・・・・・・・ [*]
とすることができる。
(4) このとき，s＜p−1 (＝sd) なので原始根を r とすると
ｒs≠1 ←原始根はp-1乗して初めて1となるので
かつ，
（ｒs）n ＝ｒstd ＝（ｒsd）t ＝（ｒp-1）t ＝1 (原始根→[#])
したがって，ｒs は方程式 xn−1＝0 の 1 以外の根である。
すなわち，（ p-1，n ） ＞ 1 ならば，方程式 xn−1 ＝ 0 は 1 以外の根をもつ。(終)
［４］ 定理-（2）の証明
(1) さらに，[*] で t＝1 のとき （ d＝n ） に相当し，
p−1＝ns ，（ もちろん，s＜p−1， n＜p−1 ）
なので ，
「原始根 r は，p-1乗して，つまり，ns乗して初めて1 になる (**) 」
ことに注意すれば，
ｒs ，ｒ2s，ｒ3s，・・・・，ｒ(n-1）s はすべて 1 ではない。
(2) また，（ｒks）n ＝ （ｒsn）k ＝ 1， （ k＝1，2，・・・，n-1 ） より，
ｒs ，ｒ2s，ｒ3s，・・・・，ｒ(n-1）s はすべて xn−1＝0 の根になっている。
(3) さらに，もし，ｒis ＝ ｒjs （ 1 ≦ i ＜ j ≦ n-1 ） ならば，
0 ＝ ｒjs−ｒis ＝ ｒis（ｒ（j-i）s−1）
より，ｒ（j-i）s ＝ 1，（ 1≦j-i≦n-2 ） でなければならないが，これは (**) に矛盾する。 したがって，
ｒs ，ｒ2s，ｒ3s，・・・・，ｒ(n-1）s は互いにすべて異なる。
(4) また，定理 [#] より
n次方程式の根の数はn個以下である。
以上より，xn−1＝0 の根は，
ｒs ，ｒ2s，ｒ3s，・・・・，ｒ(n-1）s と 1
ですべてであることが証明された。 (終)
問題
F7上の方程式 x3＝1 の解をもとめよ。 （ 答え 1，2，4 ）