整数論の問題

$a$ が法 $103$ の平方剰余であることは、ルジャンドル記号 $\left(\frac{a}{103}\right)=1$ と同値である（$a$ は $103$ と互いに素）。平方剰余の相互法則とその第 2 補充法則を用いて順に計算する。なお $103\equiv 3(\mathrm{mod}4)$、$103\equiv 7(\mathrm{mod}8)$ である。

$a=2$: 第 2 補充法則より $\left(\frac{2}{p}\right)=1⟺p\equiv \pm 1(\mathrm{mod}8)$。$103\equiv 7\equiv -1(\mathrm{mod}8)$ なので $\left(\frac{2}{103}\right)=1$。

$a=3$: $3$ と $103$ はともに $4$ で割って $3$ 余るので、相互法則より $$\left(\frac{3}{103}\right)=-\left(\frac{103}{3}\right)=-\left(\frac{1}{3}\right)=-1$$（$103=3\cdot 34+1$）。

$a=5$: $5\equiv 1(\mathrm{mod}4)$ なので $$\left(\frac{5}{103}\right)=\left(\frac{103}{5}\right)=\left(\frac{3}{5}\right)=-1$$（$103=5\cdot 20+3$、法 $5$ の平方剰余は $1,4$ のみ）。

$a=7$: $7\equiv 3(\mathrm{mod}4)$ なので $$\left(\frac{7}{103}\right)=-\left(\frac{103}{7}\right)=-\left(\frac{5}{7}\right)$$（$103=7\cdot 14+5$）。法 $7$ の平方剰余は $1,2,4$ なので $\left(\frac{5}{7}\right)=-1$。よって $\left(\frac{7}{103}\right)=1$。

$a=11$: $11\equiv 3(\mathrm{mod}4)$ なので $$\left(\frac{11}{103}\right)=-\left(\frac{103}{11}\right)=-\left(\frac{4}{11}\right)=-1$$（$103=11\cdot 9+4$、$4=2^2$ は平方剰余）。

$a=13$: $13\equiv 1(\mathrm{mod}4)$ なので $$\left(\frac{13}{103}\right)=\left(\frac{103}{13}\right)=\left(\frac{12}{13}\right)=\left(\frac{-1}{13}\right)=1$$（$103=13\cdot 7+12$、$12\equiv -1$、第 1 補充法則より $13\equiv 1(\mathrm{mod}4)$ なら $\left(\frac{-1}{13}\right)=1$）。

以上より、平方剰余であるのは $a=2,7,13$ である。

$p=103$ は素数で $p\equiv 3(\mathrm{mod}4)$、$p\equiv 7(\mathrm{mod}8)$。ルジャンドル記号と平方剰余の相互法則（$p,q$ が奇素数で、ともに $3(\mathrm{mod}4)$ のとき $\left(\frac{p}{q}\right)=-\left(\frac{q}{p}\right)$、それ以外は等しい）を使う。

・$a=2$: $p\equiv \pm 1(\mathrm{mod}8)$ なので $\left(\frac{2}{103}\right)=1$。（実際 $38^2=1444=14\cdot 103+2$ ✓）
・$a=3$: 両方 $3(\mathrm{mod}4)$ なので $\left(\frac{3}{103}\right)=-\left(\frac{103}{3}\right)=-\left(\frac{1}{3}\right)=-1$。
・$a=5$: $\left(\frac{5}{103}\right)=\left(\frac{103}{5}\right)=\left(\frac{3}{5}\right)=-1$（5 を法とする平方は $1,4$）。
・$a=7$: 両方 $3(\mathrm{mod}4)$ なので $\left(\frac{7}{103}\right)=-\left(\frac{103}{7}\right)=-\left(\frac{5}{7}\right)$。7 を法とする平方は $1,2,4$ なので $\left(\frac{5}{7}\right)=-1$、よって $\left(\frac{7}{103}\right)=1$。
・$a=11$: 両方 $3(\mathrm{mod}4)$ なので $\left(\frac{11}{103}\right)=-\left(\frac{103}{11}\right)=-\left(\frac{4}{11}\right)=-1$。
・$a=13$: $13\equiv 1(\mathrm{mod}4)$ なので $\left(\frac{13}{103}\right)=\left(\frac{103}{13}\right)=\left(\frac{12}{13}\right)=\left(\frac{-1}{13}\right)=1$。

確かめ: $7$: $103\cdot k+7$ が平方になる例 $103\cdot 3+7=316$, ... $103\cdot 5+7=522$, $103\cdot 9+7=934$, 続けて $103\cdot 57+7=5878$... 直接の確認の代わりに、$2\cdot 7=14$ と $2,7$ がともに平方剰余、$3\cdot 5=15$ が平方剰余（$-1\cdot -1$）などの整合性から矛盾はない。また $13$: $103+13\cdot ...$ 相互法則の計算で $\left(\frac{103}{13}\right)=\left(\frac{12}{13}\right)=1$。

よって平方剰余であるものは $2,7,13$。