平方剰余記号の定理 - 名前のない定理

$n$ を自然数とする. $p = 9n + 16$ が素数のとき, $\left( \dfrac{n^2-n}{p} \right)=1$ が成り立つ.ここで括弧はルジャンドル記号である.

実例: $n = 3$ のとき $9n + 16 = 43$ , $\left( \dfrac{6}{43} \right) = 1$ .
$n = 5$ のとき $9n + 16 = 61$ , $\left( \dfrac{20}{61} \right) = 1$ .
$n = 7$ のとき $9n+16 = 79$ , $\left( \dfrac{42}{79} \right) = 1$ .

証明: $9 + 16 = 25$ に $n$ を掛ける.法 $p$ の合同式を考えると, $9n + 16n \equiv -16 + 16n \equiv 25n \pmod{p}$ .
$n(n-1) \equiv 4^{-2}(5n)^2 \pmod{p}$ よって $\left( \dfrac{n^2-n}{p} \right) = 1$ が成り立つ.(証明終わり)