高斯引理

關於多項式的「高斯引理」，請見「高斯引理 (多項式)」。

在數論中，高斯引理給出了一個整數是模另一個整數的二次剩餘的條件。儘管高斯引理沒有實際計算上的意義，但作為二次互反律的證明中的一環，高斯引理有着理論上的重要性。

高斯引理最早出現在高斯1808年發表的二次互反律的第三個證明中^[1]，並在第五個證明中再次用到^[2]。

敍述

設${\displaystyle p}$為奇質數，${\displaystyle a}$是一個與${\displaystyle p}$互質的整數。考慮以下數組：${\displaystyle a,2a,3a,\dots ,{\frac {p-1}{2}}a}$, 取它們模${\displaystyle p}$的最小非負剩餘。這些剩餘兩兩不等，因此我們共有${\displaystyle {\frac {p-1}{2}}}$個兩兩不等的介於1和${\displaystyle p-1}$之間的整數：${\displaystyle t_{1},t_{2},t_{3},\dots ,t_{\frac {p-1}{2}}}$。設其中有${\displaystyle n}$個數比${\displaystyle {\frac {p}{2}}}$大，那麼高斯引理聲稱：

${\displaystyle \left({\frac {a}{p}}\right)=(-1)^{n}}$

上式左邊是勒讓德符號，當其值為+1時，表示${\displaystyle a}$是模${\displaystyle p}$的二次剩餘；其值為-1時，表示${\displaystyle a}$是模${\displaystyle p}$的二次非剩餘。

用通俗的語言來說，就是：如果${\displaystyle t_{1},t_{2},t_{3},\dots ,t_{\frac {p-1}{2}}}$裏面比${\displaystyle {\frac {p}{2}}}$大的有偶數個，那麼${\displaystyle a}$是模${\displaystyle p}$的二次剩餘，如果有奇數個，那麼${\displaystyle a}$是模${\displaystyle p}$的二次非剩餘。

例子

令${\displaystyle p=11}$，${\displaystyle a=7}$，則我們考慮的數組是${\displaystyle 7,14,21,28,35}$。模11之後，就得到${\displaystyle 7,3,10,6,2}$。其中比${\displaystyle {\frac {11}{2}}}$大的有三個：${\displaystyle 6,7,10}$。3是奇數，因此由高斯引理得到結論：7是模11的二次非剩餘。

這個結論是正確的，因為模11的全部二次剩餘是${\displaystyle 1,3,4,5,9}$，不包括7在內。

證明

一個常見的簡單證明^[3]用的是一個令人聯想到費馬小定理之最簡單證明的方法：考慮乘積

${\displaystyle Z=a\cdot 2a\cdot 3a\cdot \cdots \cdot {\frac {p-1}{2}}a}$

用兩種方式模p之後，一方面可以得到：

${\displaystyle Z=a^{\frac {p-1}{2}}\left(1\cdot 2\cdot 3\cdot \cdots \cdot {\frac {p-1}{2}}\right)}$

另一方面，我們將${\displaystyle t_{1},t_{2},\cdots t_{\frac {p-1}{2}}}$中每一個比${\displaystyle {\frac {p}{2}}}$大的數都減去${\displaystyle p}$，這樣我們得到一個新數組${\displaystyle t'_{1},t'_{2},\cdots t'_{\frac {p-1}{2}}}$，其中每個數都介於${\displaystyle -{\frac {p}{2}}}$與${\displaystyle {\frac {p}{2}}}$之間。取絕對值後，我們便得到${\displaystyle {\frac {p-1}{2}}}$個介於1和${\displaystyle {\frac {p-1}{2}}}$之間（含等於${\displaystyle {\frac {p-1}{2}}}$）的整數（這是因為${\displaystyle {\frac {p}{2}}}$不是整數，因此比${\displaystyle {\frac {p}{2}}}$小的整數必然小於等於${\displaystyle {\frac {p-1}{2}}}$）。

關鍵的一步，是證明這些數兩兩不等。

證明是用反證法：假設在這些數中有兩個數${\displaystyle |x|}$和${\displaystyle |y|}$相等，那麼找出其對應的「原型」：${\displaystyle x\equiv k\cdot a\mod p}$與${\displaystyle y\equiv l\cdot a\mod p}$，其中k和l是兩個介於1和${\displaystyle {\frac {p-1}{2}}}$之間的整數。分別平方後，就有：

${\displaystyle (ka)^{2}\equiv x^{2}\equiv y^{2}\equiv (la)^{2}\mod p}$

因此p整除兩者之差：${\displaystyle p|(ka)^{2}-(la)^{2}=a^{2}\cdot (k+l)\cdot (k-l)}$。

但這不可能，因為p不整除${\displaystyle a^{2}}$，並且由於k和l是兩個介於1和${\displaystyle {\frac {p-1}{2}}}$之間的整數，它們的和與差的都介於${\displaystyle -p+1}$與${\displaystyle p-1}$之間，絕對值比${\displaystyle p}$小，不可能被${\displaystyle p}$整除。這導致了矛盾！

因此這${\displaystyle {\frac {p-1}{2}}}$個數都在1和${\displaystyle {\frac {p-1}{2}}}$之間，且兩兩不等。於是它們就是${\displaystyle 1,2,\cdots {\frac {p-1}{2}}}$。這樣，

${\displaystyle Z\equiv t_{1}t_{2}\cdots t_{\frac {p-1}{2}}}$

${\displaystyle .\ \ \equiv t'_{1}t'_{2}\cdots t'_{\frac {p-1}{2}}}$ (因為我們知道${\displaystyle t_{i}\equiv t_{i}-p\mod p}$)

${\displaystyle .\ \ \equiv (-1)^{n}\cdot |t'_{1}||t'_{2}|\cdots |t'_{\frac {p-1}{2}}|}$ (比${\displaystyle {\frac {p}{2}}}$大的減去${\displaystyle p}$之後為負數，因此共有${\displaystyle n}$個-1)

${\displaystyle .\ \ \equiv (-1)^{n}\left(1\cdot 2\cdot 3\cdot \cdots \cdot {\frac {p-1}{2}}\right)\mod p}$

總結兩次不同算法的結果，可以得出：${\displaystyle (-1)^{n}\equiv a^{\frac {p-1}{2}}\mod p}$（因為${\displaystyle p}$不整除${\displaystyle 1\cdot 2\cdot 3\cdot \cdots \cdot {\frac {p-1}{2}}}$）。然而由歐拉判別法可以得出

${\displaystyle \left({\frac {a}{p}}\right)=a^{\frac {p-1}{2}}}$

因此有

${\displaystyle \left({\frac {a}{p}}\right)=(-1)^{n}}$

引理得證。

應用

在很多的二次互反律的證明中都可以見到高斯引理的身影^[4][5]。比如艾森斯坦曾用高斯引理證明了在${\displaystyle 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]）。

克羅內克運用高斯引理證明了

${\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後就可立即得到二次互反律。

與群論中遷移的關係

令${\displaystyle G}$為Z/pZ中全體非零的二次剩餘類組成的乘法群，令${\displaystyle H}$為此群的子群${\displaystyle \{+1,-1\}}$。考慮如下的${\displaystyle G}$中${\displaystyle H}$的陪集代表：

${\displaystyle 1,2,3,\dots ,{\frac {p-1}{2}}}$。

在這些陪集上應用遷移，就可以得到遷移同態：${\displaystyle \phi :G\to H}$，將${\displaystyle a}$射到${\displaystyle (-1)^{n}}$，其中${\displaystyle a}$與${\displaystyle n}$為高斯引理中所定義的。高斯引理可以被看做一個清楚地將這個同態等同到二次剩餘特徵的計算。

參見

• 同餘
• 二次剩餘
• 勒讓德符號
• 二次互反律
• 歐拉判別法
• 佐羅塔列夫引理