初等整数論/べき剰余

p {\displaystyle p} を奇素数、 a {\displaystyle a} を p {\displaystyle p} で割り切れない数、 x 2 ≡ a ( mod p ) {\displaystyle x^{2}\equiv a{\pmod {p}}} としたときに解を持つ、持たないにしたがって a {\displaystyle a} を p {\displaystyle p} の平方剰余、平方非剰余 という。
a ≢ 0 {\displaystyle a\not \equiv 0} のとき a {\displaystyle a} が平方剰余、非剰余にしたがって
( a p ) = 1 , − 1 {\displaystyle \left({\frac {a}{p}}\right)=1,\,-1} とする。また、便宜上 ( k p p ) = 0 {\displaystyle \left({\frac {kp}{p}}\right)=0} とする。これをルジャンドル記号と呼ぶ。
したがって ( a p ) {\displaystyle \left({\frac {a}{p}}\right)} は a {\displaystyle a} の属する剰余類にのみ依存する。そして ( a p ) = − 1 {\displaystyle \left({\frac {a}{p}}\right)=-1} ならば k p + a {\displaystyle kp+a} の形の平方数は存在しない。
例 ( 2 3 ) = ( 3 4 ) = ( 3 5 ) = − 1 , ( 4 5 ) = 1 {\displaystyle \left({\frac {2}{3}}\right)=\left({\frac {3}{4}}\right)=\left({\frac {3}{5}}\right)=-1,\left({\frac {4}{5}}\right)=1} である。
補題 1 r {\displaystyle r} を p {\displaystyle p} の原始根とする。定理 2.3.4 から x 2 ≡ a ( mod p ) {\displaystyle x^{2}\equiv a{\pmod {p}}} が解を持つのと I n d r a {\displaystyle {\rm {Ind}}_{r}\,a} が ( 2 , p − 1 ) = 2 {\displaystyle (2,p-1)=2} で割り切れるというのは同値である。したがって
( a p ) = ( − 1 ) I n d r a . {\displaystyle \left({\frac {a}{p}}\right)=(-1)^{{\rm {Ind}}_{r}\,a}.}
a ≡ a ′ ( mod p ) {\displaystyle a\equiv a'{\pmod {p}}} ならば ( a p ) = ( a ′ p ) {\displaystyle \left({\frac {a}{p}}\right)=\left({\frac {a'}{p}}\right)}
証明 合同の推移性、または補題 1 によって明白。
( a b c ⋯ p ) = ( a p ) ( b p ) ( c p ) ⋯ {\displaystyle \left({\frac {abc\cdots }{p}}\right)=\left({\frac {a}{p}}\right)\left({\frac {b}{p}}\right)\left({\frac {c}{p}}\right)\cdots }
証明 補題 1 より ( a b c ⋯ p ) = ( − 1 ) I n d r a b c ⋯ {\displaystyle \left({\frac {abc\cdots }{p}}\right)=(-1)^{{\rm {Ind}}_{r}\,abc\cdots }}
定理 2.3.4 より 、これは
に等しい。ここで再び補題 1 より、これは
= ( a p ) ( b p ) ( c p ) ⋯ {\displaystyle =\left({\frac {a}{p}}\right)\left({\frac {b}{p}}\right)\left({\frac {c}{p}}\right)\cdots }
に等しい。
( a p ) ≡ a p − 1 2 ( mod p ) {\displaystyle \left({\frac {a}{p}}\right)\equiv a^{\frac {p-1}{2}}{\pmod {p}}}
証明 1 定理 2.3.4 から x 2 ≡ a ( mod p ) {\displaystyle x^{2}\equiv a{\pmod {p}}} が解を持つ、つまり ( a p ) = 1 {\displaystyle \left({\frac {a}{p}}\right)=1} のとき、
f = p − 1 ( 2 , p − 1 ) , a f ≡ 1 ( mod p ) . {\displaystyle f={\frac {p-1}{(2,p-1)}},\ \ a^{f}\equiv 1{\pmod {p}}.}
ここで、 ( 2 , p − 1 ) = 2 {\displaystyle (2,p-1)=2} より、 a p − 1 2 ≡ 1 ( mod p ) {\displaystyle a^{\frac {p-1}{2}}\equiv 1{\pmod {p}}}
したがって ( a p ) ≡ 1 ( mod p ) . {\displaystyle \left({\frac {a}{p}}\right)\equiv 1{\pmod {p}}.}
逆に ( a p ) = − 1 {\displaystyle \left({\frac {a}{p}}\right)=-1} 、つまり x 2 ≡ a ( mod p ) {\displaystyle x^{2}\equiv a{\pmod {p}}} が解を持たないとき、再び定理 2.3.4 から
a p − 1 2 ≢ 1 ( mod p ) . {\displaystyle a^{\frac {p-1}{2}}\not \equiv 1{\pmod {p}}.} このときフェルマーの小定理より
( a p − 1 2 ) 2 = a p − 1 ≡ 1 ( mod p ) . {\displaystyle (a^{\frac {p-1}{2}})^{2}=a^{p-1}\equiv 1{\pmod {p}}.}
よって a p − 1 2 ≡ − 1 ≡ ( a p ) ( mod p ) . {\displaystyle a^{\frac {p-1}{2}}\equiv -1\equiv \left({\frac {a}{p}}\right){\pmod {p}}.}
以上より定理は証明される。
証明 2 定理 1.8 より、 A = { 0 , a , 2 a , ⋯ , ( p − 1 ) a } {\displaystyle A=\{0,a,2a,\cdots ,(p-1)a\}} は剰余系をなすので、この中の任意の数 r {\displaystyle r} について r s ≡ a ( mod p ) {\displaystyle rs\equiv a{\pmod {p}}} となる s ∈ A {\displaystyle s\in A} がただ一つ存在する。これを r {\displaystyle r} の配偶と呼ぶことにする。
ここで ( a p ) = 1 {\displaystyle \left({\frac {a}{p}}\right)=1} のとき r {\displaystyle r} を x 2 ≡ a ( mod p ) {\displaystyle x^{2}\equiv a{\pmod {p}}} の解とすれば、 r {\displaystyle r} の配偶はそれ自身である。また、
( p − r ) 2 = p 2 − 2 p r + r 2 ≡ r 2 ( mod p ) {\displaystyle (p-r)^{2}=p^{2}-2pr+r^{2}\equiv r^{2}{\pmod {p}}} より p − r {\displaystyle p-r} も方程式の解である。このとき r = p − r {\displaystyle r=p-r} とすると p = 2 r {\displaystyle p=2r} となり、奇素数であるという仮定に反する。したがって r ≠ p − r . {\displaystyle r\neq p-r.}
合同方程式の基本定理から、上の方程式の解を満たすもの、すなわち配偶が自身であるものは r , p − r {\displaystyle r,p-r} の2つであり、他の p − 3 {\displaystyle p-3} 個の数は2個ずつ配偶があって、それらの積は
≡ a p − 3 2 ( mod p ) {\displaystyle \equiv a^{\frac {p-3}{2}}{\pmod {p}}}
であるから、
( p − 1 ) ! ≡ r ⋅ ( p − r ) ⋅ a p − 3 2 ≡ − r 2 ⋅ a p − 3 2 ≡ − a ⋅ a p − 3 2 = − a p − 1 2 ( mod p ) . {\displaystyle {\begin{aligned}(p-1)!&\equiv r\cdot (p-r)\cdot a^{\frac {p-3}{2}}\\&\equiv -r^{2}\cdot a^{\frac {p-3}{2}}\\&\equiv -a\cdot a^{\frac {p-3}{2}}=-a^{\frac {p-1}{2}}{\pmod {p}}.\\\end{aligned}}}
以上より ( a p ) = 1 ⇒ ( p − 1 ) ! ≡ − a p − 1 2 ( mod p ) {\displaystyle \left({\frac {a}{p}}\right)=1\Rightarrow (p-1)!\equiv -a^{\frac {p-1}{2}}{\pmod {p}}}
次に ( a p ) = − 1 {\displaystyle \left({\frac {a}{p}}\right)=-1} のときは上の r , p − r {\displaystyle r,p-r} のような数はないので配偶が p − 1 2 {\displaystyle {\frac {p-1}{2}}} ペアできて
( p − 1 ) ! ≡ a p − 1 2 ( mod p ) {\displaystyle (p-1)!\equiv a^{\frac {p-1}{2}}{\pmod {p}}}
a = 1 {\displaystyle a=1} は自明に前に属すので ( p − 1 ) ! ≡ − 1 ( mod p ) {\displaystyle (p-1)!\equiv -1{\pmod {p}}} (すなわちウィルソンの定理)。したがって、
これがオイラーの規準である。
p , q {\displaystyle p,q} を相異なる奇素数としたときに
2, 3 をそれぞれ第一補充法則、第二補充法則という。まずはそれぞれの意味を説明する。
1 は、 p , q {\displaystyle p,q} のどちらかが 4 n + 1 {\displaystyle 4n+1} の形のとき ( p q ) = ( q p ) {\displaystyle \left({\frac {p}{q}}\right)=\left({\frac {q}{p}}\right)} で、どちらとも 4 n + 3 {\displaystyle 4n+3} の形のときに限り ( p q ) = − ( q p ) {\displaystyle \left({\frac {p}{q}}\right)=-\left({\frac {q}{p}}\right)} である、という意味である。
2 は、 x 2 ≡ − 1 ( mod p ) {\displaystyle x^{2}\equiv -1{\pmod {p}}} に解がある ⟺ p ≡ 1 ( mod 4 ) {\displaystyle \iff p\equiv 1{\pmod {4}}}
3 は、 p = 8 n + 1 , 8 n + 7 {\displaystyle p=8n+1,\,8n+7} のとき ( p q ) = 1 {\displaystyle \left({\frac {p}{q}}\right)=1} で、 p = 8 n + 3 , 8 n + 5 {\displaystyle p=8n+3,\,8n+5} のとき ( p q ) = − 1 {\displaystyle \left({\frac {p}{q}}\right)=-1} である。つまり x 2 ≡ 2 ( mod p ) {\displaystyle x^{2}\equiv 2{\pmod {p}}} に解がある ⟺ p ≡ 1 , 7 ( mod 8 ) . {\displaystyle \iff p\equiv 1,7{\pmod {8}}.}
証明 2 から証明する。
オイラーの規準より、 ( − 1 p ) ≡ ( − 1 ) p − 1 2 ( mod p ) . {\displaystyle \left({\frac {-1}{p}}\right)\equiv (-1)^{\frac {p-1}{2}}{\pmod {p}}.}
どちらも ± 1 {\displaystyle \pm 1} の値を取り、 p {\displaystyle p} は奇素数なので ( − 1 p ) = ( − 1 ) p − 1 2 . {\displaystyle \left({\frac {-1}{p}}\right)=(-1)^{\frac {p-1}{2}}.}
さて、3 であるが、これにはガウスの補題を用いる。
gcd ( a , p ) = 1 {\displaystyle \gcd(a,p)=1} のとき、 A = { a , 2 a , 3 a , ⋯ , p − 1 2 a } {\displaystyle A=\left\{a,2a,3a,\cdots ,{\frac {p-1}{2}}a\right\}} をそれぞれ p {\displaystyle p} で割ったときの余りが p 2 {\displaystyle {\frac {p}{2}}} より大きい数が n {\displaystyle n} 個あったとき、
( a p ) = ( − 1 ) n . {\displaystyle \left({\frac {a}{p}}\right)=(-1)^{n}.}
証明 ある数を p {\displaystyle p} で割った余りが p 2 {\displaystyle {\frac {p}{2}}} よりも大きいならば、それから p {\displaystyle p} を引くと − p 2 {\displaystyle -{\frac {p}{2}}} よりも大きい負の余りを得る。つまり、絶対最小剰余である。上の n {\displaystyle n} というのは負の絶対最小剰余の個数である。
A {\displaystyle A} の任意の2つの数 a x , a y ( x ≠ y ) {\displaystyle ax,ay\ (x\neq y)} について、
( a , p ) = 1 , 1 − p 2 ≦ x ± y ≦ p + 1 2 {\displaystyle (a,p)=1,\ {\frac {1-p}{2}}\leqq x\pm y\leqq {\frac {p+1}{2}}} であり、 x ± y ≠ 0 {\displaystyle x\pm y\neq 0} より、 A {\displaystyle A} の中には絶対最小剰余として等しいもの、また絶対最小剰余として符号が逆なものも存在しない。すなわち全体として符号を無視すれば
{ 1 , 2 , 3 , ⋯ , p − 1 2 } {\displaystyle \left\{1,2,3,\cdots ,{\frac {p-1}{2}}\right\}} に合同で、そのうち負の数の個数が n {\displaystyle n} である。したがって
a ⋅ 2 a ⋅ 3 a ⋯ p − 1 2 a ≡ ( − 1 ) n ⋅ 1 ⋅ 2 ⋅ 3 ⋯ p − 1 2 {\displaystyle a\cdot 2a\cdot 3a\cdots {\frac {p-1}{2}}a\equiv (-1)^{n}\cdot 1\cdot 2\cdot 3\cdots {\frac {p-1}{2}}}
だが、 1, 2, ..., p − 1 2 {\displaystyle {\frac {p-1}{2}}} はいずれも p {\displaystyle p} と互いに素なので
a p − 1 2 ≡ ( − 1 ) n {\displaystyle a^{\frac {p-1}{2}}\equiv (-1)^{n}}
を得る。オイラーの規準によって
( a p ) ≡ ( − 1 ) n ( mod p ) . {\displaystyle \left({\frac {a}{p}}\right)\equiv (-1)^{n}{\pmod {p}}.}
どちらも ± 1 {\displaystyle \pm 1} に等しく、 p {\displaystyle p} は奇素数なので
( a p ) = ( − 1 ) n . {\displaystyle \left({\frac {a}{p}}\right)=(-1)^{n}.}
さて 3 の証明だが、
2 , 4 , 6 , ⋯ , p − 1 {\displaystyle 2,4,6,\cdots ,p-1}
の中で p 2 {\displaystyle {\frac {p}{2}}} より多いものの個数が n {\displaystyle n} である。
(i) p = 8 n + 1 {\displaystyle p=8n+1} のとき
p 2 = 4 n + 1 2 , p − 1 = 8 n {\displaystyle {\frac {p}{2}}=4n+{\frac {1}{2}},\ p-1=8n} なので、この間にある偶数の数は 8 n − 4 n 2 = 2 n {\displaystyle {\frac {8n-4n}{2}}=2n} であり、 ( 2 p ) = ( − 1 ) 2 n = 1 {\displaystyle \left({\frac {2}{p}}\right)=(-1)^{2n}=1}
また p 2 − 1 8 = 8 n 2 + 2 n {\displaystyle {\frac {p^{2}-1}{8}}=8n^{2}+2n} より、 ( − 1 ) p 2 − 1 8 = 1 {\displaystyle (-1)^{\frac {p^{2}-1}{8}}=1} で、
( 2 p ) = ( − 1 ) p 2 − 1 8 . {\displaystyle \left({\frac {2}{p}}\right)=(-1)^{\frac {p^{2}-1}{8}}.}
(ii) p = 8 n + 3 {\displaystyle p=8n+3} のとき
p 2 = 4 n + 3 2 , p − 1 = 8 n + 2 {\displaystyle {\frac {p}{2}}=4n+{\frac {3}{2}},\ p-1=8n+2} なので、この間にある偶数の数は ( 8 n + 2 ) − ( 4 n + 2 ) 2 + 1 = 2 n + 1 {\displaystyle {\frac {(8n+2)-(4n+2)}{2}}+1=2n+1} であり、 ( 2 p ) = ( − 1 ) 2 n + 1 = − 1. {\displaystyle \left({\frac {2}{p}}\right)=(-1)^{2n+1}=-1.}
また p 2 − 1 2 = 8 n 2 + 6 n + 1 {\displaystyle {\frac {p^{2}-1}{2}}=8n^{2}+6n+1} より、 ( − 1 ) p 2 − 1 8 = − 1 {\displaystyle (-1)^{\frac {p^{2}-1}{8}}=-1} で、
( 2 p ) = ( − 1 ) p 2 − 1 8 . {\displaystyle \left({\frac {2}{p}}\right)=(-1)^{\frac {p^{2}-1}{8}}.}
(iii) p = 8 n + 5 {\displaystyle p=8n+5} のとき
p 2 = 4 n + 5 2 , p − 1 = 8 n + 4 {\displaystyle {\frac {p}{2}}=4n+{\frac {5}{2}},\ p-1=8n+4} なので、この間にある偶数の数は ( 8 n + 4 ) − ( 4 n + 2 ) 2 = 2 n + 1 {\displaystyle {\frac {(8n+4)-(4n+2)}{2}}=2n+1} であり、 ( 2 p ) = ( − 1 ) 2 n + 1 = − 1. {\displaystyle \left({\frac {2}{p}}\right)=(-1)^{2n+1}=-1.}
また p 2 − 1 2 = 8 n 2 + 10 n + 3 {\displaystyle {\frac {p^{2}-1}{2}}=8n^{2}+10n+3} より、 ( − 1 ) p 2 − 1 8 = − 1 {\displaystyle (-1)^{\frac {p^{2}-1}{8}}=-1} で、
( 2 p ) = ( − 1 ) p 2 − 1 8 . {\displaystyle \left({\frac {2}{p}}\right)=(-1)^{\frac {p^{2}-1}{8}}.}
(iv) p = 8 n + 7 {\displaystyle p=8n+7} のとき
p 2 = 4 n + 7 2 , p − 1 = 8 n + 6 {\displaystyle {\frac {p}{2}}=4n+{\frac {7}{2}},\ p-1=8n+6} なので、この間にある偶数の数は ( 8 n + 4 ) − ( 4 n + 4 ) 2 = 2 n {\displaystyle {\frac {(8n+4)-(4n+4)}{2}}=2n} であり、 ( 2 p ) = ( − 1 ) 2 n = − 1. {\displaystyle \left({\frac {2}{p}}\right)=(-1)^{2n}=-1.}
また p 2 − 1 2 = 8 n 2 + 14 n + 3 {\displaystyle {\frac {p^{2}-1}{2}}=8n^{2}+14n+3} より、 ( − 1 ) p 2 − 1 8 = − 1 {\displaystyle (-1)^{\frac {p^{2}-1}{8}}=-1} で、
( 2 p ) = ( − 1 ) p 2 − 1 8 . {\displaystyle \left({\frac {2}{p}}\right)=(-1)^{\frac {p^{2}-1}{8}}.}
以上により 3 が証明される。
最後に相互法則であるが、初等整数論/平方剰余の相互法則の証明に譲る。
例 1 ( 31 103 ) {\displaystyle \left({\frac {31}{103}}\right)} を求めよ。
相互法則より
( 31 103 ) = ( − 1 ) 15 ⋅ 51 ( 103 31 ) = − ( 10 31 ) = − ( 2 31 ) ( 5 31 ) {\displaystyle \left({\frac {31}{103}}\right)=(-1)^{15\cdot 51}\left({\frac {103}{31}}\right)=-\left({\frac {10}{31}}\right)=-\left({\frac {2}{31}}\right)\left({\frac {5}{31}}\right)}
となる。ここで、第二補充法則と相互法則を用いて
( 2 31 ) = 1 , ( 5 31 ) = ( 31 5 ) = ( 1 5 ) = 1 {\displaystyle \left({\frac {2}{31}}\right)=1,\left({\frac {5}{31}}\right)=\left({\frac {31}{5}}\right)=\left({\frac {1}{5}}\right)=1}
を得るから
( 31 103 ) = − 1 {\displaystyle \left({\frac {31}{103}}\right)=-1}
とわかる。
例 2 p {\displaystyle p} が奇素数のとき
( 5 p ) = ( p 5 ) = { 1 ( p ≡ 1 , 4 ( mod 5 ) ) , − 1 ( p ≡ 2 , 3 ( mod 5 ) ) {\displaystyle \left({\frac {5}{p}}\right)=\left({\frac {p}{5}}\right)={\begin{cases}1(p\equiv 1,4{\pmod {5}}),\\-1(p\equiv 2,3{\pmod {5}})\end{cases}}}
が成り立つ。