平方剩餘

平方剩餘是一個數學概念。假設p是素數，a是整數。 如果存在一個整數x使得x^2≡a(mod p) （即x^2-a可以被p整除）， 那么就稱a在p的剩餘類中是平方剩餘的。

基本介紹

• 中文名：平方剩餘
• 外文名：Quadratic residue
• 性質：數學公式
• 套用：數字計算

假設p是素數，a是整數。 如果存在一個整數x使得x^2≡a(mod p) （即x^2-a可以被p整除）， 那么就稱a在p的剩餘類中是平方剩餘的。

歐拉定理說：如果p是奇素數，則a平方剩餘若且唯若 a^{(p-1)/2}≡1 (mod p).

在{1,2,...,p-1}中恰好有（p-1）/2 個數是平方剩餘的。

勒讓德符號： (a/p)=1 (相應的，-1) 如果 a是平方剩餘(相應的， 如果 a不是平方剩餘）。

高斯著名的二次互反律告訴我們：假設p和q是2個不同的奇素數，則

【q/p】*【p/q】=(-1)^{(p-1)*(q-1)/4}.