整数論の問題

相互法則 $\left(\frac{p}{q}\right)\left(\frac{q}{p}\right)=(-1{)}^{\frac{p-1}{2}\cdot \frac{q-1}{2}}$ を使って、分母を小さくしていきます。

ステップ 1：相互法則で上下を入れ替える

$31$ と $103$ は異なる奇素数です。指数は
$$\frac{31-1}{2}\cdot \frac{103-1}{2}=15\cdot 51=765$$
で、これは奇数です。（$31\equiv 3$, $103\equiv 3(\mathrm{mod}4)$ なので、指数が奇数になることはすぐにわかります。）したがって
$$\left(\frac{31}{103}\right)=-\left(\frac{103}{31}\right)$$
です。

ステップ 2：分子を法 $31$ で小さくする

$103=3\cdot 31+10$ より $103\equiv 10(\mathrm{mod}31)$ なので
$$\left(\frac{103}{31}\right)=\left(\frac{10}{31}\right)=\left(\frac{2}{31}\right)\left(\frac{5}{31}\right)$$
です。2 つ目の等号では乗法性を使いました。

ステップ 3：補充法則で $\left(\frac{2}{31}\right)$ を求める

$$\frac{31^2-1}{8}=\frac{960}{8}=120$$
は偶数なので、$\left(\frac{2}{31}\right)=(-1{)}^{120}=1$ です。（$31\equiv 7(\mathrm{mod}8)$ からもわかります。）

ステップ 4：再び相互法則で $\left(\frac{5}{31}\right)$ を求める

指数は $\frac{5-1}{2}\cdot \frac{31-1}{2}=2\cdot 15=30$ で偶数なので
$$\left(\frac{5}{31}\right)=\left(\frac{31}{5}\right)$$
です。$31\equiv 1(\mathrm{mod}5)$ より $\left(\frac{31}{5}\right)=\left(\frac{1}{5}\right)=1$ となります。

ステップ 5：まとめる

$$\left(\frac{31}{103}\right)=-\left(\frac{2}{31}\right)\left(\frac{5}{31}\right)=-1\cdot 1\cdot 1=-1$$

よって答えは $-1$ です。つまり、$31$ は法 $103$ の平方非剰余です。

$31\equiv 3(\mathrm{mod}4)$、$103\equiv 3(\mathrm{mod}4)$ なので、平方剰余の相互法則より $\left(\frac{31}{103}\right)=-\left(\frac{103}{31}\right)$。

$103=3\cdot 31+10$ より $\left(\frac{103}{31}\right)=\left(\frac{10}{31}\right)=\left(\frac{2}{31}\right)\left(\frac{5}{31}\right)$。

$31\equiv 7(\mathrm{mod}8)$ なので $\left(\frac{2}{31}\right)=1$。

$5\equiv 1(\mathrm{mod}4)$ なので $\left(\frac{5}{31}\right)=\left(\frac{31}{5}\right)=\left(\frac{1}{5}\right)=1$。

よって $\left(\frac{10}{31}\right)=1$。

検算：$14^2=196=6\cdot 31+10$ より $10$ は法 $31$ の平方剰余であり、$\left(\frac{10}{31}\right)=1$ と一致する。

ゆえに $\left(\frac{31}{103}\right)=-1$。