ルジャンドル記号の乗法的性質の証明
📂整数論 ルジャンドル記号の乗法的性質の証明 定義 QRとNRはそれぞれ二次剰余と二次非剰余 を意味する。ルジャンドル記号 legendre Symbol は、p p p 自然数 a a a ( a p ) = { 1 a : QR − 1 a : NR
\left( { a \over p } \right) =
\begin{cases}
1 & a \text{: QR}
\\ -1 & a \text{: NR}
\end{cases}
( p a ) = { 1 − 1 a : QR a : NR ( x y ) \displaystyle \left( {{x} \over {y}} \right) ( y x ) ルジャンドル記号 legendre Symbol と呼ばれ、素数でない自然数に対して一般化すると、記法は同じであるがヤコビ記号 jacobi Symbol と称される。
定理 2 2 2 素数 p p p ( a b p ) = ( a p ) ( b p )
\left( { ab \over p } \right) = \left( { a \over p } \right) \left( { b \over p } \right)
( p ab ) = ( p a ) ( p b )
説明 例えばp = 7 p=7 p = 7 1 , 2 , 4 1,2,4 1 , 2 , 4 3 , 5 , 6 3,5,6 3 , 5 , 6 ( 1 7 ) = ( 2 7 ) = ( 4 7 ) = 1
\left( { 1 \over 7 } \right) = \left( { 2 \over 7 } \right) = \left( { 4 \over 7 } \right) = 1
( 7 1 ) = ( 7 2 ) = ( 7 4 ) = 1 ( 3 7 ) = ( 5 7 ) = ( 6 7 ) = − 1
\left( { 3 \over 7 } \right) = \left( { 5 \over 7 } \right) = \left( { 6 \over 7 } \right) = -1
( 7 3 ) = ( 7 5 ) = ( 7 6 ) = − 1 f ( a b ) = f ( a ) f ( b ) f(ab) = f(a)f(b) f ( ab ) = f ( a ) f ( b )
証明に入る前に、QRとNRが以下の性質を持つという事実から話そう。
QR x QR = QR QR x NR = NR NR x NR = QR p = 7 p=7 p = 7 1 1 1 − 1 -1 − 1
証明 パート 1. QR x QR = QR
( a b p ) = ( a p ) ( b p ) \displaystyle \left( { ab \over p } \right) = \left( { a \over p } \right) \left( { b \over p } \right) ( p ab ) = ( p a ) ( p b ) ( a b p ) = ( a p ) \displaystyle \left( { ab \over p } \right) = \left( { a \over p } \right) ( p ab ) = ( p a ) ( b p ) = 1 \displaystyle \left( { b \over p } \right) = 1 ( p b ) = 1 q 1 = a q_{1} = a q 1 = a q 2 = b q_{2} = b q 2 = b q 1 ≡ m 1 2 ( m o d p ) q_{1} \equiv {m_{1}}^2 \pmod{p} q 1 ≡ m 1 2 ( mod p ) q 2 ≡ m 2 2 ( m o d p ) q_{2} \equiv {m_{2}}^2 \pmod{p} q 2 ≡ m 2 2 ( mod p ) m 1 {m_{1}} m 1 m 2 {m_{2}} m 2 q 3 = q 1 q 2 q_{3} = q_{1} q_{2} q 3 = q 1 q 2 q 3 ≡ q 1 q 2 ≡ m 1 2 m 2 2 ≡ ( m 1 m 2 ) 2 ( m o d p )
q_{3} \equiv q_{1} q_{2} \equiv {m_{1}}^2 {m_{2}}^2 \equiv (m_{1} m_{2})^2 \pmod{p}
q 3 ≡ q 1 q 2 ≡ m 1 2 m 2 2 ≡ ( m 1 m 2 ) 2 ( mod p ) q 3 q_{3} q 3
パート 2. QR x NR = NR
( a b p ) = ( a p ) ( b p ) \displaystyle \left( { ab \over p } \right) = \left( { a \over p } \right) \left( { b \over p } \right) ( p ab ) = ( p a ) ( p b ) ( a b p ) = − 1 \displaystyle \left( { ab \over p } \right) = -1 ( p ab ) = − 1 ( a p ) \displaystyle \left( { a \over p } \right) ( p a ) ( b p ) \displaystyle \left( { b \over p } \right) ( p b ) 1 1 1 − 1 -1 − 1
q = a q = a q = a n = b n = b n = b q ≡ m 2 ( m o d p ) q \equiv m^2 \pmod{p} q ≡ m 2 ( mod p ) m m m r = q n r=qn r = q n
すると、r ≡ k 2 ( m o d p ) r \equiv k^2 \pmod{p} r ≡ k 2 ( mod p ) k k k q n ≡ r ( m o d p )
qn \equiv r \pmod{p}
q n ≡ r ( mod p ) ( m ) 2 n ≡ ( k ) 2 ( m o d p ) (m)^2 n \equiv (k)^2 \pmod{p} ( m ) 2 n ≡ ( k ) 2 ( mod p )
合同式での乗法逆元 ：素数 p p p gcd ( p , a ) = 1 \gcd(p,a) = 1 g cd( p , a ) = 1 a x ≡ 1 ( m o d p ) a x \equiv 1 \pmod{p} a x ≡ 1 ( mod p ) 0 < x < p 0<x<p 0 < x < p
両辺に( m − 1 ) 2 (m^{-1})^2 ( m − 1 ) 2 n ≡ ( m − 1 k ) 2 ( m o d p )
n \equiv (m^{-1}k)^2 \pmod{p}
n ≡ ( m − 1 k ) 2 ( mod p ) n n n m − 1 k m^{-1} k m − 1 k r = q n r=qn r = q n
パート 3. NR x NR = QR
( a b p ) = ( a p ) ( b p ) \displaystyle \left( { ab \over p } \right) = \left( { a \over p } \right) \left( { b \over p } \right) ( p ab ) = ( p a ) ( p b ) ( a b p ) = 1 \displaystyle \left( { ab \over p } \right) = 1 ( p ab ) = 1 ( a p ) = ( b p ) = − 1 \displaystyle \left( { a \over p } \right) = \left( { b \over p } \right) = -1 ( p a ) = ( p b ) = − 1
n = a n = a n = a 素数 p p p 1 , 2 , ⋯ ( p − 1 ) 1,2, \cdots (p-1) 1 , 2 , ⋯ ( p − 1 ) ちょうど半分がQR、ちょうど半分がNR である。フェルマーの小定理を証明するときと同様に、n , 2 n , ⋯ ( p − 1 ) n n, 2n, \cdots (p-1)n n , 2 n , ⋯ ( p − 1 ) n
パート 2で、QR x NR = NRであることを示したので、n n n 1 , 2 , ⋯ ( p − 1 ) 1,2, \cdots (p-1) 1 , 2 , ⋯ ( p − 1 ) n , 2 n , ⋯ ( p − 1 ) n n, 2n, \cdots (p-1)n n , 2 n , ⋯ ( p − 1 ) n p − 1 2 \displaystyle {{p-1} \over 2} 2 p − 1 p − 1 2 \displaystyle {{p-1} \over 2} 2 p − 1
パート1~3をまとめてルジャンドル記号で表すと、以下のようになる。
( a b p ) = ( a p ) ( b p )
\left( { ab \over p } \right) = \left( { a \over p } \right) \left( { b \over p } \right)
( p ab ) = ( p a ) ( p b )
■
一方で、ルジャンドル記号の乗法的性質とガウスの二次相互法則 を使用すると、次の系が得られる。これはいわゆる「分母」に対してもルジャンドル記号の乗法的性質が適用されることを意味する。
系 2 2 2 a a a ( a p q ) = ( a p ) ( a q )
\left( { a \over pq } \right) = \left( { a \over p } \right) \left( { a \over q } \right)
( pq a ) = ( p a ) ( q a )
系の証明 ガウスの二次相互法則 : ( q p ) = { ( p q ) p ≡ 1 ( m o d 4 ) ∨ q ≡ 1 ( m o d 4 ) − ( p q ) p ≡ 3 ( m o d 4 ) ∧ q ≡ 3 ( m o d 4 ) \left( {{ q } \over { p }} \right) = \begin{cases} \left( {{ p } \over { q }} \right) & p \equiv 1 \pmod{4} \lor q \equiv 1 \pmod{4} \\ - \left( {{ p } \over { q }} \right) & p \equiv 3 \pmod{4} \land q \equiv 3 \pmod{4} \end{cases} ( p q ) = ⎩ ⎨ ⎧ ( q p ) − ( q p ) p ≡ 1 ( mod 4 ) ∨ q ≡ 1 ( mod 4 ) p ≡ 3 ( mod 4 ) ∧ q ≡ 3 ( mod 4 )
ケース 1. a ≡ 1 ( m o d 4 ) ∨ p q ≡ 1 ( m o d 4 ) a \equiv 1 \pmod{4} \lor pq \equiv 1 \pmod{4} a ≡ 1 ( mod 4 ) ∨ pq ≡ 1 ( mod 4 )
( a p q ) = ( p q a ) = ( p a ) ( q a )
\left( {{ a } \over { pq }} \right) = \left( {{ pq } \over { a }} \right) = \left( {{ p } \over { a }} \right) \left( {{ q } \over { a }} \right)
( pq a ) = ( a pq ) = ( a p ) ( a q ) a ≡ 1 ( m o d 4 ) a \equiv 1 \pmod{4} a ≡ 1 ( mod 4 ) ( p a ) ( q a ) = ( a p ) ( a q )
\left( {{ p } \over { a }} \right) \left( {{ q } \over { a }} \right) = \left( {{ a } \over { p }} \right) \left( {{ a } \over { q }} \right)
( a p ) ( a q ) = ( p a ) ( q a )
ケース 2. a ≡ 3 ( m o d 4 ) ∧ p q ≡ 3 ( m o d 4 ) a \equiv 3 \pmod{4} \land pq \equiv 3 \pmod{4} a ≡ 3 ( mod 4 ) ∧ pq ≡ 3 ( mod 4 )
( a p q ) = − ( p q a ) = − ( p a ) ( q a )
\left( {{ a } \over { pq }} \right) = - \left( {{ pq } \over { a }} \right) = - \left( {{ p } \over { a }} \right) \left( {{ q } \over { a }} \right)
( pq a ) = − ( a pq ) = − ( a p ) ( a q ) p q ≡ 3 ( m o d 4 ) pq \equiv 3 \pmod{4} pq ≡ 3 ( mod 4 ) p ≡ ± 1 ≡ − q ( m o d 4 ) p \equiv \pm 1 \equiv - q \pmod{4} p ≡ ± 1 ≡ − q ( mod 4 ) − ( p a ) ( q a ) = ( a p ) ( a q )
- \left( {{ p } \over { a }} \right) \left( {{ q } \over { a }} \right) = \left( {{ a } \over { p }} \right) \left( {{ a } \over { q }} \right)
− ( a p ) ( a q ) = ( p a ) ( q a )
いずれの場合も、以下が成り立つ。
( a p q ) = ( a p ) ( a q )
\left( { a \over pq } \right) = \left( { a \over p } \right) \left( { a \over q } \right)
( pq a ) = ( p a ) ( q a )
■
