勒讓德符號

法國數學家勒讓德 (Adrien-Marie Legendre 1752 - 1833 )

(照片取自「The MacTutor History of Mathematics Achieve」http://www-gap.dcs.st-and.ac.uk/~history/ )

勒讓德符號 (Legendre Symbol) 在數論 (Number Theory) 中，等別是二次剩餘中很常用。現在讓我們認識多一點。

首先我們記 (a/p)為 1 若 a 是 p 的二次剩餘 (Quadratic Residue)；反之，記作 - 1，即 a 是 p 的二次非剩餘 (Quadratic Non-residue)。

二次剩餘的意思是 x²=a (mod p) 有解，反之若無解便是二次非剩餘。

現在讓我們認識一些勒讓德符號的性質吧！

(1/p) = 1，

(a²/p) = 1，對任何 a，

若 a = b (mod p) 則 (a/p) = (b/p)，

若 p 為奇素數，且 a 與 p 互素 (Coprime)，則 (a/p) = a^(p-1)/2 (mod p)，

(ab/p) = (a/p) * (b/p)

(2/p) = (-1)^{(p^2-1)/8}，

若 p 、q 是兩個不同的奇素數，則 (p/q) * (q/p) = (-1)^{(p-1)/2 * (q-1)/2}或 (p/q) = (q/p) * (-1)^{(p-1)/2
* (q-1)/2}。(互反律)

看看一些例子吧！

(12/17) = (3/17) * (2²/17) = (3/17) = 3^(17-1)/2 (mod 17) = -1

(2/19) = (-1)^{(19^2-1)/8} = -1⁴⁵ = -1

(219/383) = (3/383) * (73/383) 其中 383 是奇素數。

式中的 (3/383) * (383/3) = (-1)^{(383-1)/2 * (3-1)/2} = (-1)¹⁹¹ = -1，

即 (3/383) = - (383/3) = -(2/3) = +1

及 (73/383) * (383/73) = (-1)^{(383-1)/2 * (73-1)/2} = (-1)⁶⁸⁷⁶ = +1，

即 (73/383) = (383/73) = (18/73) = (2/73) * (3²/73) = (2/73) = +1

所以 (219/383) = (3/383) * (73/383) = +1

求以 3 為二次剩餘的奇素數。

由互反律可知 (3/p) = (p/3) * (-1) ^(p-1)/2，即若要 (3/p) = 1 唯有 (p/3) 和 (-1) ^(p-1)/2 同號。顯然當 (p-1)/2 為偶數時即 p = 1 (mod 4) ，若 (p-1)/2 為奇數時即 p = -1 (mod 4)。再看若 p = 1 (mod 3) 則有 (p/3) = (1/3) = 1，反之若 p = -1 (mod 3) ，則會使 (p/3) = -1。

故我們有若 (3/p) =1 即

1. (p-1)/2 為偶數時即 p = 1 (mod 4) 及 p = 1 (mod 3) 或

2. (p-1)/2 為奇數時即 p = -1 (mod 4) 及 p = -1 (mod 3)

所以唯有 p = ± 1 (mod 12) 才可使 (3/p) = 1，即以 3 為二次剩餘的奇素數是 12 k ± 1，式中 k 為正整數 (Positive Integer)。

相信大定家看罷也會對這符號多認識。