平方剰余
フェルマー、オイラー、ラグランジュ、ルジャンドルをはじめとする17〜18世紀の数論者たちはそれぞれ平方剰余についての定理を確立し、予想を打ち立てたが、最初の体系的な扱いはガウスのDisquisitiones ArithmeticaeのIV節 (1801) である。Article 95では、「平方剰余」と「平方非剰余」という用語を導入し、文脈から明らかであれば、形容詞「平方」を削除できると述べている。
与えられた n に対して、n を法とする平方剰余のリストは単に 0, 1, ..., n − 1 を二乗するだけで得られる。a ≡ (n − a) (mod n) であるので、n を法とする平方数のリストは n/2 に対して対称であり、リストアップは n/2 まで続ければ十分である。これは下の表で確認できる。
つまり、n を法とする平方剰余の数は、n/2 + 1(n が偶数)または n + 1/2(n が奇数)を超えることはない。
2つの剰余の積は常に剰余となる。
ただし、n が合成数の場合は平方剰余性問題(英語版) (quadratic residuosity problem) となり、これは素因数分解ほど難しい(英語版)かは分かっていないが、かなり難しいと考えられている。
一方、ある上限値 c より小さい x の解があるかどうかを判定する場合、この問題はNP完全である。ただし、これは c をパラメータとする固定パラメーターの扱いやすい(英語版)問題である。
一般に、合成数 n を法として a が平方剰余であるかどうかを判定するには、次の定理を使用できる:
n > 1とし、gcd(a,n) = 1とする。x ≡ a (mod n) が解けることと以下の条件は同値である:
n のすべての奇数の約数 p について、ルジャンドル記号表現が ( a p ) = 1 {\displaystyle \left({\frac {a}{p}}\right)=1} である。
n が4割り切れるが8で割り切れない場合は a ≡ 1 (mod 4)。または n が8で割り切れる場合は a ≡ 1 (mod 8)。
注:この定理を使うに当たって本質的には n の素因数分解が既知である必要がある。また、gcd(a,n) = m の場合、合同関係は a/m ≡ x/m (mod n/m) に還元することができるが、(m が平方数でない限り)これは平方剰余の問題の範疇を超える。
であり、p ≡ 3 (mod4) の場合、
α 01 = p + 1 4 , α 00 = α 10 = α 11 = p − 3 4 . {\displaystyle \alpha _{01}={\frac {p+1}{4}},\;\alpha _{00}=\alpha _{10}=\alpha _{11}={\frac {p-3}{4}}.}
である。
例:(太字は剰余)
mod 17
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16 A00 = {1,8,15}, A01 = {2,4,9,13}, A10 = {3,7,12,14}, A11 = {5,6,10,11}.
mod 19
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18 A00 = {4、5、6、16}, A01 = {1,7,9,11,17}, A10 = {3,8,10,15}, A11 = {2,12,13,14}.
ガウス (1828)は、p ≡ 1 (mod 4) ならば x ≡ 2 (mod p) という命題が p = a + 64 b と同値であることを証明し、この種の数え上げを導入した。
まず、法 n が素数である場合、ルジャンドル記号 ( a n ) {\displaystyle \left({\frac {a}{n}}\right)} はユークリッドの互除法のバリエーションまたはオイラーの規準を使用して、すばやく計算できる。-1の場合、解は存在しない。
次に ( a n ) = 1 {\displaystyle \left({\frac {a}{n}}\right)=1} と仮定すると、n ≡ 3 (mod 4) の場合 ラグランジュは、解が以下の式によって与えられることを発見した。
x ≡ ± a ( n + 1 ) / 4 ( mod n ) {\displaystyle x\equiv \pm \;a^{(n+1)/4}{\pmod {n}}}
そしてルジャンドルは、n ≡ 5 (mod 8) の場合の同様の解を発見した。
x ≡ { ± a ( n + 3 ) / 8 ( mod n ) if a is a quartic residue modulo n ± a ( n + 3 ) / 8 2 ( n − 1 ) / 4 ( mod n ) if a is a quartic non-residue modulo n {\displaystyle x\equiv {\begin{cases}\pm \;a^{(n+3)/8}{\pmod {n}}&{\text{ if }}a{\text{ is a quartic residue modulo }}n\\\pm \;a^{(n+3)/8}2^{(n-1)/4}{\pmod {n}}&{\text{ if }}a{\text{ is a quartic non-residue modulo }}n\end{cases}}}