設
p
{\displaystyle p}
為奇質數 ,
a
{\displaystyle a}
是一個與
p
{\displaystyle p}
互質 的整數。考慮以下數組:
a
,
2
a
,
3
a
,
…
,
p
−
1
2
a
{\displaystyle a,2a,3a,\dots ,{\frac {p-1}{2}}a}
, 取它們模
p
{\displaystyle p}
的最小非負剩餘 。這些剩餘兩兩不等,因此我們共有
p
−
1
2
{\displaystyle {\frac {p-1}{2}}}
個兩兩不等的介於1和
p
−
1
{\displaystyle p-1}
之間的整數:
t
1
,
t
2
,
t
3
,
…
,
t
p
−
1
2
{\displaystyle t_{1},t_{2},t_{3},\dots ,t_{\frac {p-1}{2}}}
。設其中有
n
{\displaystyle n}
個數比
p
2
{\displaystyle {\frac {p}{2}}}
大,那麼高斯引理聲稱:
(
a
p
)
=
(
−
1
)
n
{\displaystyle \left({\frac {a}{p}}\right)=(-1)^{n}}
上式左邊是勒讓德符號 ,當其值為+1時,表示
a
{\displaystyle a}
是模
p
{\displaystyle p}
的二次剩餘;其值為-1時,表示
a
{\displaystyle a}
是模
p
{\displaystyle p}
的二次非剩餘。
用通俗的語言來說,就是:如果
t
1
,
t
2
,
t
3
,
…
,
t
p
−
1
2
{\displaystyle t_{1},t_{2},t_{3},\dots ,t_{\frac {p-1}{2}}}
裏面比
p
2
{\displaystyle {\frac {p}{2}}}
大的有偶數 個,那麼
a
{\displaystyle a}
是模
p
{\displaystyle p}
的二次剩餘,如果有奇數 個,那麼
a
{\displaystyle a}
是模
p
{\displaystyle p}
的二次非剩餘。
令
p
=
11
{\displaystyle p=11}
,
a
=
7
{\displaystyle a=7}
,則我們考慮的數組是
7
,
14
,
21
,
28
,
35
{\displaystyle 7,14,21,28,35}
。模11之後,就得到
7
,
3
,
10
,
6
,
2
{\displaystyle 7,3,10,6,2}
。其中比
11
2
{\displaystyle {\frac {11}{2}}}
大的有三個:
6
,
7
,
10
{\displaystyle 6,7,10}
。3是奇數,因此由高斯引理得到結論:7是模11的二次非剩餘。
這個結論是正確的,因為模11的全部二次剩餘是
1
,
3
,
4
,
5
,
9
{\displaystyle 1,3,4,5,9}
,不包括7在內。
一個常見的簡單證明[ 3] 用的是一個令人聯想到費馬小定理 之最簡單證明的方法:考慮乘積
Z
=
a
⋅
2
a
⋅
3
a
⋅
⋯
⋅
p
−
1
2
a
{\displaystyle Z=a\cdot 2a\cdot 3a\cdot \cdots \cdot {\frac {p-1}{2}}a}
用兩種方式模p 之後,一方面可以得到:
Z
=
a
p
−
1
2
(
1
⋅
2
⋅
3
⋅
⋯
⋅
p
−
1
2
)
{\displaystyle Z=a^{\frac {p-1}{2}}\left(1\cdot 2\cdot 3\cdot \cdots \cdot {\frac {p-1}{2}}\right)}
另一方面,我們將
t
1
,
t
2
,
⋯
t
p
−
1
2
{\displaystyle t_{1},t_{2},\cdots t_{\frac {p-1}{2}}}
中每一個比
p
2
{\displaystyle {\frac {p}{2}}}
大的數都減去
p
{\displaystyle p}
,這樣我們得到一個新數組
t
1
′
,
t
2
′
,
⋯
t
p
−
1
2
′
{\displaystyle t'_{1},t'_{2},\cdots t'_{\frac {p-1}{2}}}
,其中每個數都介於
−
p
2
{\displaystyle -{\frac {p}{2}}}
與
p
2
{\displaystyle {\frac {p}{2}}}
之間。取絕對值後,我們便得到
p
−
1
2
{\displaystyle {\frac {p-1}{2}}}
個介於1和
p
−
1
2
{\displaystyle {\frac {p-1}{2}}}
之間(含等於
p
−
1
2
{\displaystyle {\frac {p-1}{2}}}
)的整數(這是因為
p
2
{\displaystyle {\frac {p}{2}}}
不是整數,因此比
p
2
{\displaystyle {\frac {p}{2}}}
小的整數必然小於等於
p
−
1
2
{\displaystyle {\frac {p-1}{2}}}
)。
關鍵的一步,是證明這些數兩兩不等。
證明是用反證法 :假設在這些數中有兩個數
|
x
|
{\displaystyle |x|}
和
|
y
|
{\displaystyle |y|}
相等,那麼找出其對應的「原型」:
x
≡
k
⋅
a
mod
p
{\displaystyle x\equiv k\cdot a\mod p}
與
y
≡
l
⋅
a
mod
p
{\displaystyle y\equiv l\cdot a\mod p}
,其中k 和l 是兩個介於1和
p
−
1
2
{\displaystyle {\frac {p-1}{2}}}
之間的整數。分別平方後,就有:
(
k
a
)
2
≡
x
2
≡
y
2
≡
(
l
a
)
2
mod
p
{\displaystyle (ka)^{2}\equiv x^{2}\equiv y^{2}\equiv (la)^{2}\mod p}
因此p 整除兩者之差:
p
|
(
k
a
)
2
−
(
l
a
)
2
=
a
2
⋅
(
k
+
l
)
⋅
(
k
−
l
)
{\displaystyle p|(ka)^{2}-(la)^{2}=a^{2}\cdot (k+l)\cdot (k-l)}
。
但這不可能,因為p 不整除
a
2
{\displaystyle a^{2}}
,並且由於k 和l 是兩個介於1和
p
−
1
2
{\displaystyle {\frac {p-1}{2}}}
之間的整數,它們的和與差的都介於
−
p
+
1
{\displaystyle -p+1}
與
p
−
1
{\displaystyle p-1}
之間,絕對值比
p
{\displaystyle p}
小,不可能被
p
{\displaystyle p}
整除。這導致了矛盾!
因此這
p
−
1
2
{\displaystyle {\frac {p-1}{2}}}
個數都在1和
p
−
1
2
{\displaystyle {\frac {p-1}{2}}}
之間,且兩兩不等。於是它們就是
1
,
2
,
⋯
p
−
1
2
{\displaystyle 1,2,\cdots {\frac {p-1}{2}}}
。這樣,
Z
≡
t
1
t
2
⋯
t
p
−
1
2
{\displaystyle Z\equiv t_{1}t_{2}\cdots t_{\frac {p-1}{2}}}
.
≡
t
1
′
t
2
′
⋯
t
p
−
1
2
′
{\displaystyle .\ \ \equiv t'_{1}t'_{2}\cdots t'_{\frac {p-1}{2}}}
(因為我們知道
t
i
≡
t
i
−
p
mod
p
{\displaystyle t_{i}\equiv t_{i}-p\mod p}
)
.
≡
(
−
1
)
n
⋅
|
t
1
′
|
|
t
2
′
|
⋯
|
t
p
−
1
2
′
|
{\displaystyle .\ \ \equiv (-1)^{n}\cdot |t'_{1}||t'_{2}|\cdots |t'_{\frac {p-1}{2}}|}
(比
p
2
{\displaystyle {\frac {p}{2}}}
大的減去
p
{\displaystyle p}
之後為負數,因此共有
n
{\displaystyle n}
個-1)
.
≡
(
−
1
)
n
(
1
⋅
2
⋅
3
⋅
⋯
⋅
p
−
1
2
)
mod
p
{\displaystyle .\ \ \equiv (-1)^{n}\left(1\cdot 2\cdot 3\cdot \cdots \cdot {\frac {p-1}{2}}\right)\mod p}
總結兩次不同算法的結果,可以得出:
(
−
1
)
n
≡
a
p
−
1
2
mod
p
{\displaystyle (-1)^{n}\equiv a^{\frac {p-1}{2}}\mod p}
(因為
p
{\displaystyle p}
不整除
1
⋅
2
⋅
3
⋅
⋯
⋅
p
−
1
2
{\displaystyle 1\cdot 2\cdot 3\cdot \cdots \cdot {\frac {p-1}{2}}}
)。然而由歐拉判別法 可以得出
(
a
p
)
=
a
p
−
1
2
{\displaystyle \left({\frac {a}{p}}\right)=a^{\frac {p-1}{2}}}
因此有
(
a
p
)
=
(
−
1
)
n
{\displaystyle \left({\frac {a}{p}}\right)=(-1)^{n}}
引理得證。
在很多的二次互反律的證明中都可以見到高斯引理的身影[ 4] [ 5] 。比如艾森斯坦 曾用高斯引理證明了在
p
{\displaystyle p}
為奇質數時,有下式成立
(
a
p
)
=
∏
n
=
1
(
p
−
1
)
/
2
sin
(
2
π
a
n
p
)
sin
(
2
π
n
p
)
,
{\displaystyle \left({\frac {a}{p}}\right)=\prod _{n=1}^{(p-1)/2}{\frac {\sin {({\frac {2\pi an}{p}})}}{\sin {({\frac {2\pi n}{p}})}}},}
並運用這個公式證明二次互反律(並且運用橢圓函數 而不是三角函數 來證明三次以及四次的互反律[ 6] )。
克羅內克 運用高斯引理證明了
(
p
q
)
=
sgn
∏
i
=
1
q
−
1
2
∏
k
=
1
p
−
1
2
(
k
p
−
i
q
)
{\displaystyle \left({\frac {p}{q}}\right)=\operatorname {sgn} \prod _{i=1}^{\frac {q-1}{2}}\prod _{k=1}^{\frac {p-1}{2}}\left({\frac {k}{p}}-{\frac {i}{q}}\right)}
。
翻轉p 和q 後就可立即得到二次互反律。
令
G
{\displaystyle G}
為Z /p Z 中全體非零的二次剩餘類組成的乘法群 ,令
H
{\displaystyle H}
為此群的子群
{
+
1
,
−
1
}
{\displaystyle \{+1,-1\}}
。考慮如下的
G
{\displaystyle G}
中
H
{\displaystyle H}
的陪集 代表:
1
,
2
,
3
,
…
,
p
−
1
2
{\displaystyle 1,2,3,\dots ,{\frac {p-1}{2}}}
。
在這些陪集上應用遷移 ,就可以得到遷移同態:
ϕ
:
G
→
H
{\displaystyle \phi :G\to H}
,將
a
{\displaystyle a}
射到
(
−
1
)
n
{\displaystyle (-1)^{n}}
,其中
a
{\displaystyle a}
與
n
{\displaystyle n}
為高斯引理中所定義的。高斯引理可以被看做一個清楚地將這個同態等同到二次剩餘特徵的計算。
^ "Neuer Beweis eines arithmetischen Satzes"; pp 458-462 of Untersuchungen uber hohere Arithmetik
^ "Neue Beweise und Erweiterungen des Fundalmentalsatzes in der Lehre von den quadratischen Reste"; pp 496-501 of Untersuchungen uber hohere Arithmetik
^ 在一般的初等數論教材或相關著作中都可以看到這個證明,這裏引用的是高斯的Untersuchungen uber hohere Arithmetik ,pp 458-462
^ Lemmermeyer, ch. 1
^ Lemmermeyer, p. 9 "like most of the simplest proofs [ of QR], [Gauss's] 3 and 5 rest on what we now call Gauss's Lemma
^ Lemmermeyer, ch. 8
Gauss, Carl Friedrich; Maser, H.(translator into German), Untersuchungen uber hohere Arithmetik(Disqusitiones Arithemeticae & other papers on number theory)(Second edition), New York: Chelsea, 1965, ISBN 0-8284-0191-8