|
６ 体Ｆp上の2次方程式［Fpにおける解］ | |
| f-denshi.com 最終更新日： | ||
有限体Fq上の2項方程式： xn－a ＝ 0 の一般的な解法を得ることがこの章の目的です。その第一歩として、q ＝ p （素数） の場合について考えましょう。すなわち体Fp上（p：素数）の2項方程式、xn－a ＝ 0 の解法について詳しく調べ、次章で、一般的な有限体上の代数方程式を解きます。
［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 のときは、
x2 ＝ a （ a∈F7 ） の解
a ＝ 0、1、2、4 → x は F7 に根をもち、
x2 ＝ 0 → 根は 0
x2 ＝ 1 → 根は 1 と 6
x2 ＝ 2 → 根は 3 と 4
x2 ＝ 4 → 根は 2 と 5a ＝ 3、5、6 → x は F7 に根をもたない
ということがわかります。次にこの結果をふまえてシラミつぶしによらない一般的な解法を考えましょう。
［３］ まず、原始根 r に関する指数[#]に着目します。 F7に おける原始根の一つ r＝3 に関する a∈F7* の指数を下に示します。
|
⇒ |
|
ind 3（a) と a とは1対1で対応しているので、
x2＝a
を解く代わりに、この両辺の指数が等しいとおいて
2×ind 3（x) ＝ind 3（a) （mod 6)
を解くことに問題を置き換えられます。 この合同式の解法の中に出てくる解の存在条件は、そのままいま考えている2項方程式の解の存在条件にもなるので、先に進む前に必ずこちらで勉強して下さい。 ⇒ ［Appendix3］
［４］ では、実際にこの方針で
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｝
が F7 上の根として求まりました。
［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 個の解が得られる。
問題： n＝2、p＝7、r＝3、 a＝2 で上の定理を確かめてください
［1］ a ＝ 1 の特殊な場合ですが、Fp 上にかならず1つは解が存在するという点でユニークなので特別に調べておきましょう
| （1） Fp 上の方程式 xn－1＝0
が、Fp において1以外の根をもつための必要十分条件は、 （p－1、n） ＞ 1 つまり、p と n の最大公約数が 1 より大きいことである。 （2） 特に n が p-1の約数で、 p-1 ＝ sn、 s ： 正整数 と表せるとき、解は原始根のひとつを r とすれば、 1、ｒs、r2s、・・・、r(n-1)s の n 個である。 |
［2］ （1）の証明
［必要性］ 背理法を使います。
Fp の1以外の元をα（ つまりαn＝1 ）とし、（ p、n ） ＝ 1 が成り立っているとする。
このとき、
（p－1）x＋nＹ ＝ 1
をみたす、整数 x、Ｙ が存在します。したがって、
α1＝α（p－1）x＋nＹ
＝（α（p－1））x（αn）Ｙ
＝1 （フェルマーの定理 αp－1＝ 1 を用いた[#]）
となって矛盾します。すなわち、（ p、n ）＞1
［３］ ［十分性］ （ p-1、n ）＞ 1 より、整数 s、t、d が存在して、
p－1 ＝ sd、 n ＝ td、 s と t は互いに素、d ＞ 1 ・・・・・・・・・・・・・・・・・・・ [*]
とおくことができる。このとき、s＜p－1 (＝sd) なので原始根を r とすると
ｒs≠1
かつ、
（ｒs）n＝ｒstd＝（ｒsd）t＝（ｒp-1）t＝1 (原始根→[#])
したがって、ｒs は方程式 xn－1＝0 の1以外の根である。
すなわち、（ p-1、n ） ＞ 1 ならば、方程式 xn－1 ＝ 0 は 1 以外の根をもつ
［４］ （2）の証明
さらに[*]で t ＝ 1 のとき （ d ＝ n ）は、
p-1 ＝ sn 、（ もちろん、s ＜ p-1、 n ＜ p-1 ）
なので 、r が原始根で、p-1乗して（つまり、sn乗して）初めて1 になる(**) ことに注意すれば、
［Ⅰ］ ｒs 、ｒ2s、ｒ3s、・・・・、ｒ(n-1）s はすべて1ではない。
また、（ｒks）n ＝ （ｒsn）k ＝ （ｒp-1）k ＝ 1、 （ k＝1、2、・・・、n-1 ） より、
［Ⅱ］ ｒs 、ｒ2s、ｒ3s、・・・・、ｒ(n-1）s は、すべて xn－1＝0 の根になっている。
さらに、もし、ｒ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 は互いにすべて異なる。
また、定理 [#] より
［Ⅳ］ n次方程式の根の数はn個以下である
以上より、（2）が証明されました。