直感でわかる！平方剰余とルジャンドル記号の仕組み

1. 平方剰余とは何か？

正の整数 \( m \) に対し、ある整数 \( x \) が存在して \[ x^2 \equiv a \pmod{m} \] を満たすとき、\( a \) は法 \( m \) における平方剰余 (quadratic residue)といいます。そうでなければ平方非剰余と呼びます。

例：法 \( 7 \) の場合

\( 0^2 \equiv 0 \)
\( 1^2 \equiv 1 \)
\( 2^2 \equiv 4 \)
\( 3^2 \equiv 2 \)
\( 4^2 \equiv 2 \)
\( 5^2 \equiv 4 \)
\( 6^2 \equiv 1 \)

このとき、平方剰余は \( 0,1,2,4 \)、平方非剰余は \( 3,5,6 \) となります。

法が奇素数 \( p \) のとき、平方剰余の個数はちょうど \[ \frac{p + 1}{2} \] です。これは \(\pm x\) を同一視することでわかります（\( x^2 = (-x)^2 \)）。

また、平方剰余の集合は対称性を持ちます。例えば法11では \( 1^2 = 1 \), \( 2^2 = 4 \), \( 3^2 = 9 \), \( 4^2 = 5 \), \( 5^2 = 3 \) など、平方剰余は 1, 3, 4, 5, 9。

奇素数 \( p \) に対して、\( p \) と互いに素な整数 \( a \) に対し、 ルジャンドル記号 \( \left( \frac{a}{p} \right) \) は次のように定義されます：

これは数論の判定法や合同式の整理に役立ちます。

オイラーの定理により、次が成り立ちます： \[ \left( \frac{a}{p} \right) \equiv a^{(p-1)/2} \pmod{p} \] この式を用いると平方剰余かどうかを簡単に判定できます。

例： \( a = 2, p = 7 \)

\( 2^3 = 8 \equiv 1 \pmod{7} \) よって \( \left( \frac{2}{7} \right) = 1 \)

積に関する性質： \[ \left( \frac{ab}{p} \right) = \left( \frac{a}{p} \right)\left( \frac{b}{p} \right) \]
平方数は常に平方剰余： \[ \left( \frac{a^2}{p} \right) = 1 \]

これにより、複雑な計算も分解して簡単に行えるようになります。

問題： \( \left( \frac{10}{13} \right) \) を計算せよ。

オイラーの判定法を使う： \[ 10^6 \bmod 13 \] \( 10^2 = 100 \equiv 9 \), \( 10^4 = 81 \), \( 10^6 = 9 \cdot 81 \equiv 729 \equiv 1 \pmod{13} \) よって答えは 1（平方剰余）。