勒讓德符號
法國數學家勒讓德 (Adrien Marie Legendre 1752-1833 )
(照片取自「The MacTutor History of Mathematics Achieve」http://www-gap.dcs.st-and.ac.uk/~history/ )
勒讓德符號 (Legendre Symbol) 在數論 (Number Theory) 中,等別是二次剩餘 (Quadratic Residue) 中很常用。現在讓我們認識多一點。
首先我們記 (a/p)為 1 若 a 是 p 的二次剩餘;反之,記作 - 1,即 a 是 p 的二次非剩餘 (Quadratic Non-residue)。
二次剩餘的意思是 x2=a (mod p) 有解,反之若無解便是二次非剩餘。
現在讓我們認識一些勒讓德符號的性質吧!
(1/p) = 1,
(a2/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。(二次互反律, Quadratic Reciprocity)
看看一些例子吧!
(12/17) =
(3/17) * (22/17) = (3/17) = 3(17-1)/2 (mod 17) = -1
(2/19) =
(-1)(19^2-1)/8 = -145 = -1
(219/383)
= (3/383) * (73/383) 其中 383 是奇素數。
式中的 (3/383) * (383/3) = (-1)(383-1)/2 * (3-1)/2 = (-1)191 = -1,
即 (3/383) = - (383/3) = -(2/3) = +1
及 (73/383) * (383/73) = (-1)(383-1)/2 * (73-1)/2 = (-1)6876 = +1,
即 (73/383) = (383/73) = (18/73) = (2/73) * (32/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 為正整數。
相信大定家看罷也會對這符號多認識。