ルジャンドルの記号の性質について

ルジャンドルの記号の性質について
風あざみ
2016/02/06
目次
1
用語の説明編
2
2
証明の準備編
2
3
ルジャンドルの記号の性質編
3
4
ルジャンドルの記号の値編
6
1
1
用語の説明編
[x] を x を超えない最大の整数を意味する。
p を素数、a を p で割り切れないな正の整数とする。
ah ≡ 1 (mod p) をみたす正の整数 h のうち、最小になる整数 e のことを、
法 p に関する a の位数と呼び、e = ordp (a) と書くことにする。
とくに ordp (a) = p − 1 となるとき、a を p に関する原始根ということにする。
2
証明の準備編
命題１：素数 p と p で割り切れない正の整数 a を任意にとるとき、以下が
成り立つ。
ap−1 ≡ 1 (mod p)
証明：下記サイトを参照
http://puit578.web.fc2.com/flt.pdf
a, n を互いに素な正の整数 (ただし、n ≥ 2) とするとき、整数 ϵ(a, n) を以下
にように定義する。
a を n で割ったときの絶対値最小の余りが正のとき、ϵ(a, n) = 1
a を n で割ったときの絶対値最小の余りが負のとき、ϵ(a, n) = −1
以降簡単のため、ϵ(a, n) を ϵ(a) と書くことにする。
命題２：奇数の素数 p と p で割り切れない正の整数 a を任意にとるとき、以
下が成り立つ。
a
p−1
2
≡ ϵ(a)ϵ(2a) · · · ϵ(
p−1
a) (mod p)
2
証明：下記サイトを参照
http://puit578.web.fc2.com/gauss.pdf
命題３：p を奇数の素数とする。p に関する原始根は必ず存在する。
証明：下記サイトの定理８を参照
http://puit578.web.fc2.com/opr.pdf
2
ルジャンドルの記号の性質編
3
命題４：奇数の素数 p と p で割り切れない正の整数 a に対して以下が言
える。
x2 ≡ a
(mod p) が解を持つ ⇐⇒ a
p−1
2
≡ 1 (mod p)
証明：x2 ≡ a
(mod p) が整数解 x0 を持つとき
このとき、x0 > 0 と考えて問題はないので、以後そうする。
明らかに、x0 は p で割り切れないので、命題１より
a
p−1
2
≡ xp−1
≡ 1 (mod p)
0
がいえる。
p−1
a 2 ≡ 1 (mod p) となるとき
g を p に関する原始根とする。このとき g i ≡ a
(mod p) をみたす正の整数
i の存在が言える。このとき
g i·
p−1
2
≡a
p−1
2
ここで、ordp (g) = p − 1 より、i ·
≡ 1 (mod p)
p−1
2
= (p − 1) · j をみたす正の整数 j の存
在が言える。
よって、i = 2j がいえる。したがって、x = g j とおくと
(g j )2 ≡ g i ≡ a
(mod p)
がいえる。以上より、命題４はいえた。
□
命題５：奇数の素数 p と p で割り切れない正の整数 a に対して以下が言える。
a
p−1
2
̸≡ 1
(mod p) ⇐⇒ a
p−1
2
≡ −1 (mod p)
p−1
2
̸ 1 (mod p) となるとき
≡
命題１より以下が言える。
証明：a
(a
ここで、a
p−1
2
p−1
2
− 1)(a
a
p−1
a 2
+ 1) ≡ ap−1 − 1 ≡ 0
− 1 は素数 p で割り切れないから、a
p−1
2
(mod p)
p−1
2
+ 1 が素数 p で割り切
≡ −1 (mod p) であることがいえた。
≡ −1 (mod p) となるとき
p−1
− 1 ≡ −2 ̸≡ 0 (mod p) だから、a 2 ̸≡ 1 (mod p) であることがい
れる。したがって、a
p−1
2
p−1
2
3
えた。
□
命題５より素数 p と p で割り切れない正の整数 a に対して以下が言える。
x2 ≡ a
(mod p) が解を持たない ⇐⇒ a
p−1
2
≡ −1 (mod p)
したがって命題４と合わせて以下が言える。
素数 p と p で割り切れない正の整数 a に対して
x2 ≡ a
(mod p) が解を持つとき
a
x ≡a
2
p−1
2
≡ 1 (mod p)
(mod p) が解を持たないとき
a
p−1
2
≡ −1 (mod p)
ここでルジャンドルの記号を、以下のように定義する。
奇数の素数 p と p で割り切れない正の整数 a に対して
x2 ≡ a
x2 ≡ a
(mod p) が解を持つとき
a
( )=1
p
(mod p) が解を持たないとき
a
( ) = −1
p
このとき、以下の命題６がいえる。
命題６：p を奇数の素数、a, b を p で割り切れない正の整数とするとき、以下
が言える。
a
b
( )≡( )
p
p
証明：( ap ) ≡ ( pb )
a
b
(mod p) ならば、( ) = ( )
p
p
(mod p) がいえるとき、( ap ) = ±1, ( pb ) = ∓1(複号同順)
とはなり得ない、よって ( ap ) = ( pb ) = ±1 がいえる。
したがって、命題６がいえた。
□
再び上記のルジャンドル記号の定義より、以下が言える。
素数 p と p で割り切れない正の整数 a に対して
p−1
a
( )≡a 2
p
(mod p) · · · (R)
4
したがって、以下の命題７がいえる。
命題７：p を奇数の素数、a, b を p で割り切れない正の整数とするとき、以下
が言える。
(
a b
ab
) = ( )( )
p
p p
a≡b
a
b
(mod p) ならば、( ) = ( )
p
p
a b
証明：( ab
p ) = ( p )( p ) であること
(R) より
(
p−1
p−1 p−1
a b
ab
) ≡ (ab) 2 ≡ a 2 b 2 ≡ ( )( )
p
p p
(mod p)
a b
よって、命題６より ( ab
p ) = ( p )( p ) がいえる。
a≡b
(mod p) ならば、( ap ) = ( pb ) であること
(R) より
p−1
p−1
b
a
( ) ≡ a 2 ≡ b 2 ≡ ( ) (mod p)
p
p
よって、命題６より ( ap ) = ( pb ) がいえる。
したがって命題７はいえた。
□
命題８：奇数の素数 p と p で割り切れない正の整数 a を任意にとるとき、以
下が成り立つ。
a
p−1
( ) = ϵ(a)ϵ(2a) · · · ϵ(
a)
p
2
証明：命題２より
a
p−1
2
≡ ϵ(a)ϵ(2a) · · · ϵ(
p−1
a) (mod p)
2
また、(R) より
p−1
a
( )≡a 2
p
(mod p)
よって、以下が言える。
p−1
a
a) (mod p)
( ) ≡ ϵ(a)ϵ(2a) · · · ϵ(
p
2
( ap ) = ±1, ϵ(a)ϵ(2a) · · · ϵ( p−1
2 a) = ∓1(複号同順) とはなり得ない、よって
a)
=
±1 がいえる。
( ap ) = ϵ(a)ϵ(2a) · · · ϵ( p−1
2
したがって、命題８がいえた。
□
5
ルジャンドルの記号の値編
4
命題９：奇数の素数 p を任意にとるとき、以下が成り立つ。
(
p−1
p−1
) = (−1) 2
p
証明：命題８より以下が言える。
(
p−1
2
p−1
p−1
) = ϵ(p − 1)ϵ(2(p − 1) ) · · · ϵ(
(p − 1) )
p
2
以下の任意の正の整数 r に対して、(p − 1)r ≡ −r
(mod p) がいえるか
ら、(p − 1)r の絶対値最小の余りは負の値になる。よって以下が言える
ϵ(p − 1)ϵ(2(p − 1) ) · · · ϵ(
p−1
p−1
(p − 1) ) = (−1) 2
2
したがって、命題９はいえた。
□
命題１０：奇数の素数 p を任意にとるとき、以下が成り立つ。
p2 −1
2
( ) = (−1) 8
p
証明：命題８より以下が言える。
2
( ) = ϵ(2)ϵ(4) · · · ϵ(p − 1)
p
p ≡ 1 (mod 4) のとき
p−1
4
以下の任意の正の整数 r に対して、0 < 2r ≤
p−1
2
がいえるから、2r の
絶対値最小の余りは正の値になる。
p+3
4
以上
p−1
2
以下の整数 r に対して、 p−1
2 < 2r ≤ p − 1
(mod p) がいえる
から、2r の絶対値最小の余りは負の値になる。
このとき
p+1
2
が奇数であるので
ϵ(2)ϵ(4) · · · ϵ(p − 1) = (−1)
p−1
4
= (−1)
p2 −1
8
がいえる。
p ≡ 3 (mod 4) のとき
p−3
4 以下の任意の正の整数 r に対して、0 < 2r ≤
p−3
2
がいえるから、2r の
絶対値最小の余りは正の値になる。
p+1
4
以上
p−1
2
以下の整数 r に対して、 p−3
2 < 2r ≤ p − 1
から、2r の絶対値最小の余りは負の値になる。
このとき
p−1
2
が奇数であるので
ϵ(2)ϵ(4) · · · ϵ(p − 1) = (−1)
6
p+1
4
= (−1)
p2 −1
8
(mod p) がいえる
がいえる。したがって、命題１０はいえた。
□
命題１１：奇数の素数 p を任意にとるとき、以下が成り立つ。
(
p2 +4p−5
p−2
) = (−1) 8
p
証明：(p − 1) · 2 ≡ p − 2
(mod p) がいえるから命題７より
(
p−2
p−1 2
)=(
)( )
p
p
p
ここで命題９、命題１０より
(
p−1
p2 −1
p2 +4p−5
p−1 2
)( ) = (−1) 2 · (−1) 8 = (−1) 8
p
p
となる。したがって、命題１１はいえた。
□
命題１２：5 以上の素数 p を任意にとるとき、以下が成り立つ。
p+1
3
( ) = (−1)[ 6 ]
p
証明：命題８より以下が言える。
3
p−1
( ) = ϵ(3)ϵ(6) · · · ϵ(3
)
p
2
p ≡ 1 (mod 6) のとき
p−1
6 以下の任意の正の整数 r に対して、0 < 3r ≤
p−1
2
がいえるから、3r の
絶対値最小の余りは正の値になる。
p+5
6
以上
p−1
3
以下の整数 r に対して、 p−1
2 < 3r ≤ p − 1
(mod p) がいえる
から、3r の絶対値最小の余りは負の値になる。
p+2
3
以上
p−1
2
以下の整数 r に対して、p < 3r ≤ p − 1 +
p−1
2
(mod p) がい
えるから、3r の絶対値最小の余りは正の値になる。
したがって
ϵ(3)ϵ(6) · · · ϵ(3(p − 1) ) = (−1)
p−1
6
= (−1)[
p+1
6 ]
がいえる。
p≡5
p−5
6
(mod 6) のとき
以下の任意の正の整数 r に対して、0 < 3r ≤
p−5
2
がいえるから、3r の
絶対値最小の余りは正の値になる。
p+1
6
以上
p−2
3
以下の整数 r に対して、 p−1
2 < 2r ≤ p − 2
(mod p) がいえる
から、2r の絶対値最小の余りは負の値になる。
p+1
3
以上
p−1
2
以下の整数 r に対して、p < 2r ≤ p − 1 +
7
p−1
2
(mod p) がい
えるから、2r の絶対値最小の余りは正の値になる。
したがって
ϵ(3)ϵ(6) · · · ϵ(3(p − 1) ) = (−1)
p+1
6
= (−1)[
p+1
6 ]
がいえる。したがって、命題１２はいえた。
□
命題１３：5 以上の素数 p を任意にとるとき、以下が成り立つ。
(
証明：(p − 1) · 3 ≡ p − 3
p−1
p−3
) = (−1)[ 3 ]
p
(mod p) がいえるから命題７より
(
p−1 3
p−3
)=(
)( )
p
p
p
ここで命題９、命題１０より
(
p≡1
p+1
p−1
p−1 3
)( ) = (−1) 2 · (−1)[ 6 ]
p
p
(mod 6) のとき
(−1)
p−1
2
· (−1)[
p+1
6 ]
= (−1)
2p−2
3
= 1 = (−1)[
p−1
3 ]
p ≡ 5 (mod 6) のとき
(−1)
p−1
2
· (−1)[
p+1
6 ]
= (−1)
2p−1
3
となる。したがって、命題１３はいえた。
8
= −1 = (−1)[
p−1
3 ]
□

Download Report