平方剰余
数論において、p を法として平方数と合同である整数 q を、p を法とする平方剰余(へいほうじょうよ、英: quadratic residue)と呼ぶ。つまり、q が平方剰余であるとは、q に対し以下の条件を満たす整数 x が存在することを意味する:
x 2 ≡ q ( mod p ) . {\displaystyle x^{2}\equiv q{\pmod {p}}.}
平方剰余でない数を平方非剰余(へいほうひじょうよ、英: quadratic nonresidue)と呼ぶ。
元々、合同算術という数論の一分野からの抽象的な数学的概念であった平方剰余は、現在様々な分野で応用されており、その応用先は音響工学から暗号化、大きな数の素因数分解にまで至る。
p を法とする最小平方剰余は明らかに1である。最小二次非剰余の大きさ n(p) の問題は難しいが、常に素数である。上記ポリア=ヴィノグラードフの不等式は O ( p log  p ) {\displaystyle O({\sqrt {p}}\log p)} を与える。無条件での最良推定値は、任意の θ > 1/4√e に対して n(p) ≪ p というものであり、指標の和(英語版) (character sum) に関するバージェス (Burgess) の推定から得られた。一般化されたリーマン予想の仮定下では、アンケニー (Ankeny) が n(p) ≪ (log p) を得た。リニック (Linnik) は、n(p) > X となる X より小さい p の数は、ε に依存する定数によって制限されることを示した。
奇素数 p を法とする最小二次非剰余は次の通り。
2, 2, 3, 2, 2, 3, 2, 5, 2, 3, 2, 3, 2, 5, 2, 2, 2, 2, 7, 5, 3, 2, 3, 5, 23, 2, 2, 3, 3, 2, 3, 2, 2, 3, 2, 2, 5, 2, 2, 2, 7, 5, 2, 3, 2, 3, 2, 2, 37, 7, 2, 3, 5, 2, 3, 2, 3, 2, 2, 2, 11, 5, 2, 2, 5, 2, 2, 3, 7, 3, 2, 2, ...オンライン整数列大辞典の数列 A053760