Security Akademeia

目次 †

目次
はじめに
平方剰余
平方剰余と指数
平方剰余の性質
- 平方剰余の乗法性
- 原始根と平方剰余
ルジャンドル記号
ヤコビ記号
オイラー規準
ガウスの補題
補充法則
平方剰余の相互法則
参考文献

↑

はじめに †

　x2≡a (mod p)という2次合同方程式には、解があるときとないときがある。

　この事実を数値例で考察するために、p=7（奇素数）のときを考えてみる。

　まず乗法表を書く。乗法表なので0は除外され、それ以外の1～6の掛け算の表になる。　mod 7で考えるので、7で割った余りが書かれている。

×	1	2	3	4	5	6
1	1	2	3	4	5	6
2	2	4	6	1	3	5
3	3	6	2	5	1	4
4	4	1	5	2	6	3
5	5	3	1	6	4	2
6	6	5	4	3	2	1

　この表からわかることとして、すべての行は1～6の値が1回出ている。これはp=7と素数を選択したからである。もし、pが合成するなら、こうはいかない。0が登場したり、同じ値が登場したりするのである。

　ここで重要なのは、対角線の部分である。1列目の部分と対角線の部分だけを抽出しておく。

x	x2
1	1
2	4
3	2
4	2
5	4
6	1

　この表に注目すると、x2の部分が上下対象になっていることがわかる。
　これを直観的に理解するためには、xの列のところを書き換えればよい。mod7の世界では、4≡-3、5≡-2、6≡-1なので、次のように書き換えられる。

x	x2
1	1
2	4
3	2
-3	2
-2	4
-1	1

　こう書き換えてみれば自明であろう。xの列には、1,2,3にマイナスをつけて逆順にした3,2,1が登場している。
　 $\mathbb{Z}_p^*$ の任意のbにおいて、b2=(-b)2 (mod p)が成り立つ。つまり、2つのbと-bが2乗の世界では一致するということである。

　この表から2次合同方程式x2≡a (mod 7)の解が存在するときのa、解が存在しないときのaが判明する。x2の列に登場する数は、ある整数xの平方をmod pの世界で考えた値である。つまり、a=1,4,2のときにx=1,2,3という解があることがわかる。

　一方、残りのa=3,5,6には解がない。なぜならば、x2の列のところに登場しないからである。

↑

平方剰余 †

　ここで2次合同方程式の解の有無によって、aの呼び名を変えておく。

[定義]ある整数xの平方にmod pで合同な整数を（mod pの）平方剰余と呼ぶ。一方、そうでない整数を（mod pの）平方非剰余と呼ぶ。

　p=7の例でいえば、p=7の平方剰余は1,4,2であり、p=7の平方非剰余は3,5,6である。

　pの値が一般の場合（p=N）でも平方剰余という概念は成り立つが、まずはpを奇素数としてスタートする。

　平方剰余をきちんと定義すると次のようになる。

[定義]p（≠2）：素数、pはaを割り切らないとする。
「aがpを法とする平方剰余」
⇔def「x2≡a (mod p)が解を持つ」
⇔「∃b∈Z,b2≡a (mod p)」

　さらに、平方剰余・平方非剰余の集合を定義する。

[定義]mod pの平方剰余の集合をQRp、mod pの平方非剰余の集合をQNRpと表記する。

　言い換えると次のようになる。

$QR_p~=~\{~a~|~a~\in~\mathbb{Z}_N^*~\wedge~~(\exists~x~\in~\mathbb{Z}_p^*~\,~s.t.~\,~a~\equiv~x^2~\pmod{p})~\}$
$QNR_p~=~\{~a~|~a~\in~\mathbb{Z}_N^*~\wedge~~(\exists~x~\in~\mathbb{Z}_p^*~\,~s.t.~\,~a~\not{\equiv}~x^2~\pmod{p})~\}$

[例]p=3のときを考察すると、QR3={1}、QNR3={2}である。

[例]p=5のときは、QR5={1,4}、QNR5={2,3}である。

[例]p=7の例でいえば、QR7={1,2,4}、QNR7={3,5,6}である。

[定理]pがいずれの場合も、（QRpに含まれる値の数）＝（QNRpに含まれる値の数）、即ち|QRp|=|QNRp|という関係になる。
そして、|QRp|=(p-1)/2である。

　一般の素数pを法とした場合を考える。ただし、p=2のときは自明なので、以降はp≠2とする。すると、pを奇素数なので、p=2s+1と書ける。

　このとき、pを法とする平方剰余は、12,22,…,(p-1)2をpで割ったときの余りである。

　ところが、p=2s+1≡0により、s+1≡-s,s+2≡-(s-1),s+3≡-(s-2),…,2s≡-1 (mod p)であるため、12,22,…,s2まで考えれば十分である。

　これを定理としてまとめると、次のようになる。

[定理]素数p=2s+1を法とする平方剰余は、12,22,…,s2をpで割ったときの余りとして得られる。
特に、平方剰余はs個ある。

[証明]12,22,…,s2をpで割ったときの余りがすべて相異なることを示す必要がある。

1≦m＜n≦sとしたときに、 $m^2~\equiv~n^2~\,~\pmod{p}$ と仮定して矛盾を導く。

$m^2~\equiv~n^2~\,~\pmod{p}$
$n^2~-~m^2~\equiv~0~\,~\pmod{p}$
$(n~+~m)(n~-~m)~\equiv~0~\,~\pmod{p}$

よって、(n+m)(n-m)はpで割り切れる。
つまり、n+m or n-mの少なくとも一方がpで割り切れる。

ここで、1≦m＜n≦sより、0＜n-m＜s、2＜n+m＜2sである。
そのため、n-mもn+mもp(=2s+1)の倍数ではないので、矛盾が生じた。　□

[定理]pを奇素数（p=2s+1)とする。
(1)1は常にpを法として平方剰余である。
(2)aとbがpを法として平方剰余ならば、積abも平方剰余である。
（ab＞pのときは、abをpで割った余りが平方剰余になるということである）
(3)aがpを法として平方剰余ならば、ab≡1 (mod p)となるような平方剰余bがちょうど1つだけ存在する。

[証明]

(1)12=1なので、明らかに平方剰余である。

(2)「aとbがpを法として平方剰余」
⇒「a≡α2,b≡β2 (mod p)と書ける」
⇒「ab≡(αβ)2 (mod p)が成り立つ」
⇒「abがpを法として平方剰余」

(3)フェルマーの小定理より、 $a~\cdot~a^{p-2}~=~a^{p-1}~\equiv~1~\,~\pmod{p}$

b=ap-2とおけば、次が得られる。

ab≡1 (mod p)　←(*)

仮定より、aは平方剰余である。
よって、a自身で積を考えれば、(2)により、ap-2も平方剰余である。

また、次を満たす平方剰余cが存在するものとする。

ac≡1 (mod p)　←(**)

そこで、(*)(**)との差を取ると、a(b-c)=ab-ac≡0 (mod p)となり、pはa(b-c)を割り切る。
しかし、pとaは互いに素であるから、pはb-cを割り切らなければならない。
つまり、b≡c (mod p)　□

　p=2s+1のとき、pを法とする平方剰余の個数はs個であることはすでに証明済みである。

[定理]p=2s+1を奇素数、pを法とする平方剰余をa1,…,asとすると、次の合同式が成り立つ。
$x^s~-~1~\equiv~(x-a_1)(x-a_2)\cdots(x-a_s)~\,~\pmod{p}$

　この合同式の意味は、左辺と右辺の多項式の係数が互いに合同ということである。

[証明]通常の多項式の因数分解と同様にして証明する。

$f(x)=x^s~-~1$ と置く。

aiはpを法として、平方剰余なので、 $a_i~\equiv~{\alpha_i}^2$ と書ける。

$f(a_i)$
$=~{a_i}^s~-~1$
$\equiv~({\alpha_i}^2)^s~-~1~\,~\pmod{p}$ 　（∵ $a_i~\equiv~{\alpha_i}^2$ ）
$=~\alpha^{2s}~-~1$
$=~\alpha^{p-1}~-~1$ 　（∵p=2s+1より、2s=p-1であるから）
$\equiv~1~-~1~\,~\pmod{p}$ 　（∵フェルマーの小定理）
$=0$

よって、f(x)をx-a1で割って、次のように書く。

$f(x)=f_1(x)(x-a_1)~+~c_1$

ここで、f1(x)は次数s-1の多項式で、係数は整数である（x-a1においてxの係数が1、そしてa1が整数であるということを使った）。

x=a1と置くと、 $f(a_1)=c_1$ となるが、 $f(a_1)~\equiv~0~\,~\pmod{p}$ だから、 $c_1~\equiv~0~\,~\pmod{p}$ である。

よって、次のように書き直せる。

$f(x)~\equiv~f_1(x)(x-a_1)~\,~\pmod{p}$ 　←(*)

次に、x=a2と置いてみると、次が成り立つ。

$f(a_2)~\equiv~f_1(a_2)(a_2~-~a_1)~\,~\pmod{p}$
$f_1(a_2)(a_2~-~a_1)~\equiv~0~\,~\pmod{p}$ 　（∵ $f(a_2)~\equiv~0~\,~\pmod{p}$ ）

即ち、整数f1(a2)と(a2-a1)の積がpで割り切れる。
しかし、 $a_2~-~a_1~\not{\equiv}~0~\,~\pmod{p}$ だから、 $f_1(a_2)~\equiv~0~\,~\pmod{p}$ でなければならない。

今度はf1(x)をx-a2で割って、次のように書ける。

$f_1(x)=f_2(x)(x-a_2)~+~c_2$

前とまったく同様にして、 $c_2~\equiv~0~\,~\pmod{p}$ となり、次のように書き直せる。

$f(x)~\equiv~f_2(x)(x-a_2)(x-a_1)~\,~\pmod{p}$

同様の議論を繰り返すことで、題意が成り立つ。　□

[定理]整数aと素数p=2s+1が互いに素とする。
そのとき、aがpを法として平方剰余であるかないかは、次によって定まる。
(1) $a^s~\equiv~1~\,~\pmod{p}$ ⇒aは(pを法とする）平方剰余
(2) $a^s~\equiv~-1~\,~\pmod{p}$ ⇒aは(pを法とする）平方非剰余

[証明][定理]「p=2s+1を奇素数、pを法とする平方剰余をa1,…,asとすると、次の合同式が成り立つ。
$x^s~-~1~\equiv~(x-a_1)(x-a_2)\cdots(x-a_s)~\,~\pmod{p}$ 」によれば、合同方程式 $x^s~-1~\equiv~0~\,~\pmod{p}$ の解はちょうどs個あり、それらはpを法とする平方剰余aSUB{1},…,asである。　□

↑

平方剰余と指数 †

　各素数pに対して、原始元g（正整数）が存在する。このとき、1～(p-1)までの整数をgのべきで表すことができた。

　aの指数をtとすると、指数の定義よりIndg(a)=tが存在する。つまり、a≡gt (mod p)が成り立つ。　もし、tが偶数、即ちt=2sならば、a≡g2s≡(gs)2 (mod p)である。

　この(gs)2≡a (mod p)と2次方程式x2≡a (mod p)を比較すると、gsはxの解である。
　つまり、aは平方剰余である。

　これは逆も成り立つ。

　以上をまとめて、定理としておこう。

「整数aのmod pの指数：偶数」⇔「aはmod pの平方剰余」
「整数aのmod pの指数：奇数」⇔「aはmod pの平方非剰余」

[例]例えば、p=7のときにおける最小の原始根はg=3である。このときの指数tを計算して、指数表を作る（指数表が手元にあれば計算の手間は省ける）。

a=1のとき、t=Indg(a)=Ind3(1)=0となる。
- なぜならば、g=3をt=0乗すれば、mod 7の世界でa=1になるからである。
a=2のとき、t=Indg(a)=Ind3(2)=2となる。
- なぜならば、g=3をt=2乗すれば、mod 7の世界でa=2になるからである。
a=3のとき、t=Indg(a)=Ind3(3)=1となる。
- なぜならば、g=3をt=1乗すれば、mod 7の世界でa=3になるからである。
a=4のとき、t=Indg(a)=Ind3(4)=4となる。
- なぜならば、g=3をt=4乗すれば、mod 7の世界でa=4になるからである。
a=5のとき、t=Indg(a)=Ind3(5)=5となる。
- なぜならば、g=3をt=5乗すれば、mod 7の世界でa=5になるからである。
a=6のとき、t=Indg(a)=Ind3(6)=3となる。
- なぜならば、g=3をt=3乗すれば、mod 7の世界でa=6になるからである。

　これでp=7かつg=3の指数表を書く準備ができた。

a	t
1	0
2	2
3	1
4	4
5	5
6	6

　指数t=偶数、即ちt=0,2,4のとき、aはそれぞれ1,2,4である。これらはp=7の平方剰余であった。
　また、指数t=奇数、即ちt=1,3,5のとき、aはそれぞれ3,6,5である。これらはp=7の平方非剰余であった。

　以上により、確かに定理が成り立つことが確認できた。　◇

↑

平方剰余の性質 †

↑

平方剰余の乗法性 †

　a,bを平方剰余とすると、x2≡a、y2≡b (mod p)を満たすx,yが存在する。
　よって、(xy)2=x2・y2=ab (mod p)となり、abも平方剰余であることがわかる。

　つまり、「（平方剰余）×（平方剰余）＝（平方剰余）」が成り立つ。これを指数の言葉を使って言い換えれば、「（aの指数が偶数）×（bの指数が偶数）⇒（abの指数が偶数）」となる。
　なぜならば、次のように計算できるからである。

Ind(ab)
=Ind(a)+Ind(b)　（∵Indの性質）
=偶数＋偶数
=偶数

　こうした平方剰余・平方非剰余の関係性は、乗法表から直観的に理解できる。
　ずっとp=7の場合を考えてきたので、ここでもp=7の乗法表を用いることにするので、再び引用する。

×	1	2	3	4	5	6
1	1	2	3	4	5	6
2	2	4	6	1	3	5
3	3	6	2	5	1	4
4	4	1	5	2	6	3
5	5	3	1	6	4	2
6	6	5	4	3	2	1

　演算対象の部分（1行目・1列目）の部分を平方剰余と平方非剰余の部分にまとめた形に書き直す。
　つまり、1,2,3,4,5,6という部分を1,4,2,3,5,6（前半3つが平方剰余QR7の元、後半3つが平方非剰余QNR7の元）とするのである。

×	1	4	2	3	5	6
1	1	4	2	3	5	6
4	4	2	1	5	6	3
2	2	1	4	6	3	5
3	3	5	6	2	1	4
5	5	6	3	1	4	2
6	6	3	5	4	2	1

　この表は次のような表に帰着していることがわかる。

×	平方剰余	平方非剰余
平方剰余	平方剰余	平方非剰余
平方剰余	平方非剰余	平方剰余

　さらに、QR7={1,2,4}は乗法群を成すこともわかる。
　なぜならば、任意の元に対して逆元が存在し、さらに単位元も存在しているからである。

×	1	4	2
1	1	4	2
4	4	2	1
2	2	1	4

　以上の観察により、次の関係式が直観的に得られる。

（平方剰余）×（平方剰余）＝（平方剰余）
（平方剰余）×（平方非剰余）＝（平方非剰余）
（平方非剰余）×（平方非剰余）＝（平方非剰余）

[定理]素数p=2s+1を法として、次が成り立つ。
(1)整数a,bが共に平方剰余 or 共に平方非剰余ならば、積abは平方剰余である。 (2)a,bの一方が平方剰余、他方が平方非剰余ならば、積abは平方非剰余である。

[証明](ab)s=asbsより、[定理]「整数aと素数p=2s+1が互いに素とする。
そのとき、aがpを法として平方剰余であるかないかは、次によって定まる。
(1) $a^s~\equiv~1~\,~\pmod{p}$ ⇒aは(pを法とする）平方剰余
(2) $a^s~\equiv~-1~\,~\pmod{p}$ ⇒aは(pを法とする）平方非剰余」から、題意が成り立つ。　□

↑

原始根と平方剰余 †

[定理]pは奇素数、gはpを法とする原始根とする。
[1] $g^{\frac{p-1}{2}~\equiv~-1~\,~(mod~\,~p)}$
[2]pが1型の素数であるとき、 $x=g^{\frac{p-1}{4}}$ とすれば、x2≡-1 (mod p)が成り立つ。

[補講]どんな素数pについても、pを法とする原始根が存在する。　◇

↑

ルジャンドル記号 †

　p=2の平方剰余は1だけなので、以下はpを奇素数とする。

　pが小さいときは1から(p-1)/2まで順に調べれば平方剰余であるか平方非剰余であるかがわかる。さらに、それを与える解x、即ちmod pについての平方根もわかる。

　それでは本題であるルジャンドル記号（(○/△)という表記）を定義する。

[定義]p=2s+1を奇素数とする。
整数aに対して、記号 $(\frac{a}{p})$ を次のように定義する。

aがpを法として平方剰余の場合、 $(\frac{a}{p})~=~1$
aがpの倍数の場合、 $(\frac{a}{p})~=~0$
aがpを法として平方非剰余の場合、 $(\frac{a}{p})~=~-1$ この記号をルジャンドルの記号と呼ぶ。

　平方剰余・平方非剰余と呼ぶときは、aはpの倍数ではないことを仮定する。

[例]例えば、p=7のとき、QR7={1,2,4}であったので、ルジャンドル記号を使えば次のようになる。

(1/7)=(2/7)=(4/7)=1
(3/7)=(5/7)=(6/7)=-1

　先ほど見た平方剰余・平方非剰余の関係式とも一致している。例えば、(2/7)×(3/7)=1×(-1)=-1、また(6/7)=-1で一致する。　◇

　ルジャンドルの記号を使うと、平方剰余の性質を簡潔に述べることができる。

[定理]p=2s+1を素数、a,bを整数とする。
(1) $a~\equiv~b~\pmod{p}$ ⇒ $(\frac{a}{p})~=~(\frac{b}{p})$
(2) $(\frac{ab}{p})~=~(\frac{a}{p})(\frac{b}{p})$
(3) $(\frac{a^2}{p})=1$
特に、 $(\frac{1}{p})=1$
(4) $(\frac{a}{p})~\equiv~a^s~\pmod{p}$
特に、 $(\frac{-1}{p})~=~(-1)^s$

[証明]

(1)平方剰余の定義から、証明はほとんど自明だが、きちんと書くと次のようになる。

（左辺）＝(a/p)＝1 or -1で、どちらが選ばれるかはx2≡a (mod p)が解を持つかどうかに依存する。

　一方、（右辺）＝(b/p)＝1 or -1で、どちらが選ばれるかはx2≡b (mod p)が解を持つかどうかに依存する。仮定より、a≡b (mod p)なので、右辺の値はx2≡a (mod p)が解を持つかどうかに依存するといえる。これは、左辺の話とまったく同じ状況である。

　よって、状況に依存する結果も一致するのは明らかである。

(2)[定理]「素数p=2s+1を法として、次が成り立つ。
(1)整数a,bが共に平方剰余 or 共に平方非剰余ならば、積abは平方剰余である。 (2)a,bの一方が平方剰余、他方が平方非剰余ならば、積abは平方非剰余である。」をルジャンドルの記号で書き直しただけである。

(3)a2はpを法とする平方剰余なので、ルジャンドルの記号の定義より題意が成り立つ。

(4)[定理]「整数aと素数p=2s+1が互いに素とする。
そのとき、aがpを法として平方剰余であるかないかは、次によって定まる。
(1) $a^s~\equiv~1~\,~\pmod{p}$ ⇒aは(pを法とする）平方剰余
(2) $a^s~\equiv~-1~\,~\pmod{p}$ ⇒aは(pを法とする）平方非剰余」をルジャンドルの記号で書き直しただけである。

特に、a=-1のとき、合同の記号が等号になるのは、左辺が常に±1であり、それが(-1)sに合同ということは等しいことと同じであるからである。　□

[別証](3)を示す。

(2)の結果でa=bを代入すればよい。　□

[補講](1)の結果により、ルジャンドル記号の分子を分母で割った余りに置き換えても問題ないことが保障された。

例えば、(72/7)=(2/7)=(-5/7)と計算できる。　◇

[定理]

「整数aのmod pの指数：偶数」⇔「aはmod pの平方剰余」
「整数aのmod pの指数：奇数」⇔「aはmod pの平方非剰余」

[証明]すでに証明済みである。　□

[定理] $(\frac{a}{p})~=~(-1)^{Ind(a)}$

[証明]aが $\mathbb{Z}_p^*~=~\{~1,~\cdots,~p-1~\}$ 上を走ると、指数Ind(a)は{0,…,p-2}のいずれか1つに重複せずに該当する。
pは奇数（かつ素数）なので、集合{0,…,p-2}に含まれる元は偶数個ある。

つまり、そのうち半分は偶数であり、残りの半分は奇数である。

よって、平方剰余の個数は全体の半分である。

$|QR_p|~=~|QNR_p|~=~\frac{|\mathbb{Z}_p^*|}{2}~=~\frac{p-1}{2}$ が成り立つ。　□

[別証](2)を示す。

場合分けする。

[1] $a~|~p$ または $b~|~p$ のとき

　ルジャンドル記号の定義により両辺とも0である。

[2] $a~\not{|}~p$ かつ $b~\not{|}~p$ のとき

（左辺）
=(a/p)(b/p)
=(-1)Ind(a)×(-1)Ind(b)
=(-1)SUP{Ind(a)+Ind(b)}:
=(-1)Ind(ab)
=(ab/p)
=（右辺）　□

　この証明は平方剰余の乗法性の証明とほとんど同じであっただろう。単に表現が違うだけである。

　この定理により、合成数nに対する(n/p)を求めるときは、nを素因数分解すればよい。そうすれば、最終的に(-1/p) or (2/p) or (奇素数）の積に帰着できる。

　nが大きいときは、nを素因数分解できない。そのため、ルジャンドル記号だけでは困るので、拡張版のヤコビ記号というものが存在する。

↑

ヤコビ記号 †

↑

オイラー規準 †

[定理]オイラー規準
$(\frac{a}{p})~\equiv~a^{\frac{p-1}{2}}~\pmod{p}$

[証明]左辺の(a/p)が0,1,-1であるかにより、場合分けする。

[1]（左辺）＝(a/p)=0のとき

　ルジャンドル記号の定義よりp|aである。

（右辺）
$a^{\frac{p-1}{2}}~\pmod{p}$
$0^{\frac{p-1}{2}}~\pmod{p}$ 　（∵aはpで割り切れるので、mod pの世界でaはもちろん0になる）
≡0

　よって、左辺と右辺が一致する。

[2]（左辺）＝(a/p)=1のとき

∃x∈Z;a≡x2 (mod p)

（右辺）
$a^{\frac{p-1}{2}}~\pmod{p}$
$x^{p-1}~\pmod{p}$ 　（∵a≡x2）
≡1 (mod p)　（∵フェルマーの小定理）

　よって、左辺と右辺が一致する。

[3]（左辺）＝(1/p)=-1のとき

　pの原始元をgとすると、Indg(a)=2m+1が成り立つ。

（右辺）
$a^{\frac{p-1}{2}}~\pmod{p}$
$\equiv~(~a^{2m+1}~)^{\frac{p-1}{2}}~\pmod{p}$ 　（∵Indg(a)=2m+1より、a=g2m+1）
$\equiv~(~g^{p-1}~)^m~\cdot~g^{\frac{p-1}{2}})$
$\equiv~g^{\frac{p-1}{2}}$ 　（∵原始元の定義より、gp-1≡1）
≡-1　（∵logg(-1)=(p-1)/2)

　よって、左辺と右辺が一致する。

　したがって、[1]～[3]より、定理が成り立つ。　□

[補講]この定理は(a,p)=1であっても、(a,p)≠1でも成り立つ。　◇

[例]p=7,a=4のときで観察してみる。

$(\frac{a}{p})$
$\equiv~a^{\frac{p-1}{2}}~\pmod{p}$ 　（∵オイラー規準より）
$\equiv~4^{\frac{7-1}{2}}~\pmod{7}$
$\equiv~4^3~\pmod{7}$
$\equiv~64~\pmod{7}$
$\equiv~1~\pmod{7}$

すでに見たように4∈QR7より $(\frac{4}{7})=1$ であり、互いが一致する。　◇

↑

ガウスの補題 †

　いきなり定理を記述するのではなく、数値例で観察してみる。

　p=11,a=7とする。aの1倍から5倍（=(p-1)/2=10/2)までの数列を作る。

a×1, a×2, a×3, a×4, a×5
↓
7×1, 7×2, 7×3, 7×4, 7×5
↓
7, 14, 21, 28, 35
↓	mod pを取る。
7, 3, 10, 6, 2
↓	p/2=11/2=5.5より大きい数から11を引く。即ち、マイナスで表記する。
-4, 3, -1, -5, 2	この数列を絶対値最小剰余と呼ぶ。
↓	マイナス符号を取り除く。
4, 3, 1, 5, 2	1,2,3,4,5が1通り現れている。

　このとき、ルジャンドル記号 $(\frac{a}{p})$ を計算する。

$(\frac{a}{p})$
$=(\frac{7}{11})$
$\equiv~7^{\frac{11-1}{2}}~\pmod{11}$
$=7^5$
$\equiv~-1~\pmod{11}$

　一方、(-1)^(絶対値最小剰余の中の負の数の個数)を計算する。負の数の個数は3個なので、(-1)3=-1になる。この値-1は $(\frac{a}{p})$ の値と一致している。

　以上はp=11,a=7の場合の議論であったが、一般の場合でも成り立つ。これをガウスの補題という。

[定理]ガウスの補題
p：奇素数、r=(p-1)/2、(a,p)=1とする。
このとき、aのr倍までの倍数を並べる。= 1a, 2a, …, ra
これらのmod pの絶対値最小剰余をa1, a2, …, a_rとする。
この数列の中の負数の個数をtとすれば、(a/p)=(-1)^tである。

　上記の表記では絶対値最小剰余という言葉を使っているが、数列1a,2a,…,raをpで割った余りの中でp/2より大きい数の個数がtと言い換えることもできる。

　このガウスの補題について、数直線上で考えてみる。

　xは1から(p-1)/2までのいずれかの数とする。これをa倍して、mod pを取れば範囲Aか範囲Bに含まれる。このうち、範囲Bに含まれる個数をtとすると、pを法とするaの平方剰余、即ち(a/p)はtの偶奇に依存するということである。

[証明](a,p)=1のとき、aの(p-1)/2個（=rとおく）の倍数を作る。

1a, 2a, …, ra ←(*) （aは添え字ではない。1a＝1×a）

　そして、絶対最小剰余を

a1, a2, …, a_r ←(**)　（1,2,…,rは添え字）

とする。

　(**)の”絶対値”はすべてmod pで異なる。これを示す。

(i)ai=aj（1≦i,j≦r、i≠j）と仮定する。

ai≡aj (mod p)
a(i-j)≡0 (mod p)
i≡j (mod p)　（∵(a,p)=1よりaで両辺を割った）

仮定と矛盾。

(ii)次に、ai=-aj（1≦i,j≦r、i≠j）と仮定する。

ai≡-aj (mod p)
a(i+j)≡0 (mod p)
i+j≡0 (mod p)　（∵(a,p)=1よりaで両辺を割った）

一方、r=(p-1)/2であったので、i+j=2rであったとしてもせいぜいp-1と一致。

よって、i+j≦p-1であり、i+j＜pになる。

i+j≡0 (mod p)とi+j＜pは明らかに矛盾。

　以上の(i)(ii)より、(**)の”絶対値”はすべてmod pで異なることがわかる。

　次に、(**)の数列における符号を無視すると、1,2,…,rが1通り現れる。これを示す。

　(**)の中の負数の個数をtとすると、a1×a2×…×a_r=(-1)^t・r!　←(***)が成り立つ。

　また、(*)より、(1a)(2a)…(ra)=a^r・r!　←(****)が成り立つ。

　mod pで(***)と(****)は合同なので、次が成り立つ（右辺に注目した）。

$(-1)^t~\cdot~r!~\equiv~a^r~\cdot~r!~\pmod{p}$
$(-1)^t~\equiv~a^r$ 　（∵(r!,p)=1より、両辺からr!を割った）
$(-1)^t~\equiv~a^{\frac{p-1}{2}}$ 　（∵r=(p-1)/2）
$(-1)^t~\equiv~(\frac{a}{p})$ 　（∵オイラー規準）　□

↑

補充法則 †

　合成数nに対する(n/p)を求めるときは、ルジャンドル記号は乗法性を持つので、nを素因数分解すればよい。そうすれば、(n/p)は(-1/p) or (2/p) or (奇素数/p)の積に帰着される。つまり、(-1/p) or (2/p) or (奇素数/p)が1か-1か判定する道具（定理）が必要である。

[定理]第1補充法則
p：奇素数とする。
$(\frac{-1}{p})~=~(-1)^{\frac{p-1}{2}}$

[証明]オイラー規準である(a/p)=a^{(p-1)/2}に、a=-1を代入。　□

[別証]ガウスの補題でa=-1として、aの倍数を並べる。

1,-2,…,-r

これらはすべて絶対値最小剰余になっているので、次が成り立つ。

(-1/p)=(-1)t　∧　t=(p-1)/2　□

[系]

p≡1 (mod 4)のとき⇒(-1/p)=1
p≡3 (mod 4)のとき⇒(-1/p)=-1

[証明]mが奇数のとき、4を法とするとm=4n±1の2パターンになる。

「m=4n+1」⇔「(m-1)/2=2n」⇔「(m-1)/2：偶数」
「m=4n-1」⇔「(m-1)/2=2n-1」⇔「(m-1)/2：奇数」

p≡1 (mod 4)のとき、(p-1)/2=偶数より、(-1)^{(p-1)/2}はいつも1になる。

一方、p≡3 (mod 4)のとき、(p-1)/2=奇数より、(-1)^{(p-1)/2}はいつも-1になる。　□

[定理]第2補充法則
p：奇素数とする。
$(\frac{2}{p})~=~(-1)^{\frac{p^2~-~1}{8}}$

[（直観的な）証明]a=2としてガウスの補題を適用する。

p-1は偶数なので、p-1は2で割れる。
その結果のr=(p-1)/2の偶奇によって、場合分けをする。ここでは直観的に理解できるようにpを具体的な値で観察してみる。

[1]rが偶数のとき

・例えば、p=13（8を法としてとき5）とすると、p/2=6.5、r=(p-1)/2=6＝偶数となり、1から6までの数の倍数の数列を作る。

a×1, a×2, a×3, a×4, a×5, a×6	6個の数で構成される。
↓	a=2
2×1, 2×2, 2×3, 2×4, 2×5, 2×6
↓
2, 4, 6, 8, 10, 12

この数列の中で、p/2=6.5より大きいものの個数はt=3個（=r/2=(p-1)/4）である。

・例えば、p=17（8を法としてとき1）とすると、p/2=8.5、r=8＝偶数となり、1から8までの数の倍数の数列を作る。

a×1, a×2, a×3, a×4, a×5, a×6, a×7, a×8	8個の数で構成される。
↓	a=2
2×1, 2×2, 2×3, 2×4, 2×5, 2×6, 2×7, 2×8
↓
2, 4, 6, 8, 10, 12, 14, 16

この数列の中で、p/2=8.5より大きいものの個数はt=4個（=r/2=(p-1)/4）である。

[2]rが奇数のとき

・例えば、p=15（8を法としてとき7）とすると、p/2=7.5、r=7＝奇数となり、1から7までの数の倍数の数列を作る。

a×1, a×2, a×3, a×4, a×5, a×6, a×7	7個の数で構成される。
↓	a=2
2×1, 2×2, 2×3, 2×4, 2×5, 2×6, 2×7
↓
2, 4, 6, 8, 10, 12, 14

この数列の中で、p/2=7.5より大きいものの個数はt=4個（=(r+1)/2=(p+1)/4）である。

・例えば、p=19（8を法としてとき3）とすると、p/2=9.5、r=(p-1)/2=9＝奇数となり、1から9までの数の倍数の数列を作る。

a×1, a×2, a×3, a×4, a×5, a×6, a×7, a×8, a×9	9個の数で構成される。
↓	a=2
2×1, 2×2, 2×3, 2×4, 2×5, 2×6, 2×7, 2×8, 2×9
↓
2, 4, 6, 8, 10, 12, 14, 16, 18

この数列の中で、p/2=9.5より大きいものの個数はt=5個（=(r+1)/2=(p+1)/4）である。

以上の議論は一般に成立するから、次が成り立つ。

[1]「(p-1)/2：偶数」⇒「(p+1)/2：奇数」のとき、t1=(p-1)/4
[2]「(p-1)/2：奇数」のとき、t2=(p+1)/4

このとき、次のような式を考える。

[1] $\frac{p+1}{2}~t_1~=~\frac{p^2~-~1}{8}$
[2]
- $\frac{p-1}{2}$ は奇数である。

これらの2つの式の偶奇はt1 or t2の偶奇に依存する。
なぜならば、奇数×偶数＝偶数、奇数×奇数＝奇数であるから。

ゆえに、 $\frac{p^2~-~1}{8}$ は主張の式における右辺の(-1)の累乗に対応する。　□

[例]この第2補充法則により、例えば(2/13)を容易に解くことができる。

p=13のときであり、(p^2-1)/8=(169-1)/8=168/8=21=奇数

よって、(2/13)=(-1)^(奇数)=-1になる。　◇

[系]

p≡1 or 7 (mod 8)のとき⇒(2/p)=1
p≡3 or 5 (mod 8)のとき⇒(2/p)=-1

[証明]8を法とすると、奇数はm=8n±1 or 8n±5（n∈Z）の4パターンだけになる。

m=8n±1のとき、(m2-1)/8=8n2±2n＝偶数
m=8n±5のとき、(m2-1)/8=8n2±10n+3＝奇数

ところで、第2補充法則の $(\frac{2}{p})~=~(-1)^{\frac{p^2~-~1}{8}}$ が1か-1かは、 $\frac{p^2~-~1}{8}$ の偶奇に依存する。

pは奇素数、mが奇数なので、 $\frac{p^2~-~1}{8}$ の偶奇は $\frac{m^2~-~1}{8}$ の偶奇と一致する。　□

[補講]この系の便利さを実感してみる。第2補充法則で(2/13)を計算するときは、132の計算が必要であった。ところが、この系を使えばp=13≡5 (mod 8)より、すぐに(2/13)=-1とわかる。　◇

↑

平方剰余の相互法則 †

　残りは(奇素数/p)を調べる術のみである。これは（平方剰余の）相互法則と呼ばれる定理を用いることで実現できる。この相互法則は整数論のひとつの山場と言われており、相互法則を出発点として近代の整数論が展開された。

　この相互法則はオイラーにより帰納的に示され、完全な証明はガウスによって与えられた。相互法則の証明はたくさん存在し、本1冊になっているほどである。

　それではまず相互法則の主張を紹介する。

[定理]平方剰余の相互法則
p,q：相異なる奇数
$(\frac{p}{q})(\frac{q}{p})~=~(-1)^{{\frac{p-1}{2}}{\frac{q-1}{2}}}$
これは次のようにも言い換えられる。

p≡1 ∨ q≡1 (mod 4)のとき、(p/q)(q/p)=1
p≡3 ∧ q≡3 (mod 4)のとき、(p/q)(q/p)=-1

[証明]ガウスの補題(a/p)=(-1)^tにおいて、a=qとする。

数列{1・q, 2・q, …, {(p-1)/2}q}

x∈{1,2,…,(p-1)/2}とし、xq mod p＞p/2を満たすxの個数がtに対応する。
よって、xの偶奇がわかれば十分である。

「xq (mod p) ＞ p/2」
⇔「（(q/p)xの分数部分）＞1/2」　（∵「xq mod p＞p/2」⇔「xq=ap+r (a∈Z,0≦a＜r) ∧ r＞p/2」⇔「r/p=(q/p)x-ap ∧ r/p＞1/2」より）　←(*)

ここで原点OとD(p/2,q/2)を通る直線（Y=(q/p)X）を、y軸の方向に1/2だけ平行移動した直線をEFとする。
各Xにおいて直線Y=(q/p)Xに一番近い格子点は、Yの上か下にある。
しかもその格子点は必ず(q/p)X-(1/2)と(q/p)X+(1/2)の間に存在する。

X=xを0～p/2まで走らせたときに、直線の上に存在する一番近い格子点の個数をt1とすると次が成り立つ。

t1
=（(*)を満たすxの個数）
=#{x|x∈{1,2,…,(p-1)/2} ∧ xq (mod p) ＞ p/2}
=□OEFD内の格子点の数

同様にして、直線の下に存在する一番近い格子点の個数をt2とすると次が成り立つ。

t2
=#{y|y∈{1,2,…,(q-1)/2} ∧ yp (mod q) ＞ q/2}
=□ODHG内の格子点の数

t1+t2
=□OEFD内の格子点の数＋□ODHG内の格子点の数
=□OEFD内の格子点の数＋□ODHG内の格子点の数＋□DFBH内の格子点の数　（∵□DFBH内には必ず格子点が存在しない）
=六角形OEFBHG
=□OADC-△EFF'-△GHH'
={(p-1)/2}{(q-1)/2}-2△EFF'

（2△EFF'は偶数である）

よって、次のように主張が成り立つ。

$(\frac{q}{p})~(\frac{p}{q})$
$=(-1)^{t_1~+~t_2}$
$=(-1)^{\frac{p-1}{2}~\frac{q-1}{2}~-~\triangle~2EFF'}$
$=(-1)^{\frac{p-1}{2}~\frac{q-1}{2}}$

これで前半が証明された。

次は後半を示す。六角形OEFBHGは点M((p+1)/4,(q+q)/4)で点対称である。

[1](p+1)/4が整数∧(q+1)/4が整数、即ちp≡-1≡3 (mod 4)∧q≡3 (mod 4)のとき

　中心点Mは格子点になるためt1+t2は奇数になる。よって、(q/p)(p/q)=-1

[2]Mが格子点でなければ、t1+t2は偶数になる。よって、(q/p)(p/q)=1　□

[例]この相互法則を使えばルジャンドル記号の計算が容易になることを確認する。

(15/71) =(3/71)(5/71)　（∵15=3・5、乗法性）
=-(71/3)・(71/5) 　（∵相互法則＋「71,5：異なる素数、素数71≡3 (mod 4), 3≡3 (4)」より(3/71)=-(71/3)、「71,5：異なる素数、71≡3 (mod 4), 5≡1 (mod 4)」より(5/71)=(71/5)）
=-(2/3)(1/5)　（∵71≡2 (mod 3)、71≡1 (mod 5)）
=-(-1)・1　（∵第2補充法則の系）
=1　◇

↑

参考文献 †

『なっとくするオイラーとフェルマー』

Top / 平方剰余平方剰余

目次 †

はじめに †

平方剰余 †

平方剰余と指数 †

平方剰余の性質 †

平方剰余の乗法性 †

原始根と平方剰余 †

ルジャンドル記号 †

ヤコビ記号 †

オイラー規準 †

ガウスの補題 †

補充法則 †

平方剰余の相互法則 †

参考文献 †

Top / 平方剰余
平方剰余