整数論の問題

平方剰余の相互法則を使って、ルジャンドル記号の上下を入れ替えながら数を小さくしていきます。

手順 1：相互法則で上下を入れ替える

$31,89$ は異なる奇素数なので、相互法則
$$\left(\frac{31}{89}\right)\left(\frac{89}{31}\right)=(-1{)}^{\frac{31-1}{2}\cdot \frac{89-1}{2}}=(-1{)}^{15\cdot 44}$$
が使えます。指数 $15\cdot 44=660$ は偶数なので右辺は $1$ です。ルジャンドル記号の値は $\pm 1$ なので
$$\left(\frac{31}{89}\right)=\left(\frac{89}{31}\right).$$

手順 2：分子を法 $31$ で小さくする

$89=2\cdot 31+27$ より $89\equiv 27(\mathrm{mod}31)$ です。ルジャンドル記号は分子を法 $p$ で取り替えても値が変わらないので
$$\left(\frac{89}{31}\right)=\left(\frac{27}{31}\right).$$

手順 3：乗法性で分解する

$27=3^3$ なので、乗法性より
$$\left(\frac{27}{31}\right)={\left(\frac{3}{31}\right)}^3=\left(\frac{3}{31}\right).$$
最後の等号は、$\left(\frac{3}{31}\right)=\pm 1$ の 3 乗はもとの値に等しいことによります。

手順 4：もう一度相互法則を使う

$3,31$ は異なる奇素数なので
$$\left(\frac{3}{31}\right)\left(\frac{31}{3}\right)=(-1{)}^{\frac{3-1}{2}\cdot \frac{31-1}{2}}=(-1{)}^{1\cdot 15}=-1.$$
よって
$$\left(\frac{3}{31}\right)=-\left(\frac{31}{3}\right).$$
$31=10\cdot 3+1$ より $31\equiv 1(\mathrm{mod}3)$ なので
$$\left(\frac{31}{3}\right)=\left(\frac{1}{3}\right)=1.$$
したがって $\left(\frac{3}{31}\right)=-1$ です。

結論
$$\left(\frac{31}{89}\right)=\left(\frac{89}{31}\right)=\left(\frac{27}{31}\right)=\left(\frac{3}{31}\right)=-1.$$
つまり $31$ は法 $89$ の平方非剰余です。答えは $-1$ です。

$89\equiv 1(\mathrm{mod}4)$ なので、平方剰余の相互法則より $\left(\frac{31}{89}\right)=\left(\frac{89}{31}\right)$ である。$89=2\cdot 31+27$ より $\left(\frac{89}{31}\right)=\left(\frac{27}{31}\right)={\left(\frac{3}{31}\right)}^3=\left(\frac{3}{31}\right)$ となる。

$3\equiv 31\equiv 3(\mathrm{mod}4)$ なので、相互法則より $\left(\frac{3}{31}\right)=-\left(\frac{31}{3}\right)=-\left(\frac{1}{3}\right)=-1$ である。

検算として、$31$ を法とする平方剰余は $1,2,4,5,7,8,9,10,14,16,18,19,20,25,28$ であり、$3$ も $27$ も含まれない。よって $\left(\frac{27}{31}\right)=-1$ で一致する。

答え: $-1$