いくつか命題を証明していきたい. 奇素数pを法とすると平方剰余の個数は(p-1)/2個となる \(A := \{x^{2} \, mod \, p \mid x \in GF(p) \} \) としたときに, \( \#A = \frac{p-1}{2} \) となることを示したい. まず\(GF(p) = \{1, 2, ..., p-1 \}\), \(\#GF(…

整数論において奇素数\(p\)をModulusとしたとき, \(a \in GF(p)\)について $$ x^{2} \equiv a \, mod \, p $$ となる \(x\)が存在するとき\(a\)を\(p\)の平方剰余であるという. \(a\)が平方剰余であるかどうか(上式で解を持つかどうか)を判定するのに使われ…