平方剰余の相互法則：演習問題と回答

\(1^2,2^2,3^2,4^2,5^2\equiv 1,4,9,5,3\pmod{11}\)。したがって \(1, 3, 4, 5, 9\)。

平方剰余は \(1, 3, 4, 9, 10, 12\)。非剰余は \(2, 5, 6, 7, 8, 11\)。

\(x^2=y^2\) なら \((x-y)(x+y)\equiv0\pmod p\)。非零平方に対して根は \(x\) と \(-x\) の 2 個だけ。非零元は \(p-1\) 個なので、平方値は \((p-1)/2\) 個。

\(4=2^2\) なので平方剰余。したがって \(\Leg{4}{17}=1\)。Euler 判定法でも \(4^8=(2^2)^8=2^{16}\equiv1\pmod{17}\)。

Legendre 記号では、\(p\mid a\) のとき \(\Leg{a}{p}=0\)。したがって \(\Leg{0}{p}=0\)。

負号は \(\left(\frac{-1}{7}\right)=(-1)^{(7-1)/2}=-1\)。
分子を素因数分解すると \(1=1\)。Legendre 記号の乗法性で各因子に分ける。
積を取って \(\left(\frac{-1}{7}\right)=-1\)。

負号は \(\left(\frac{-1}{29}\right)=(-1)^{(29-1)/2}=1\)。
分子を素因数分解すると \(1=1\)。Legendre 記号の乗法性で各因子に分ける。
積を取って \(\left(\frac{-1}{29}\right)=1\)。

負号は \(\left(\frac{-1}{43}\right)=(-1)^{(43-1)/2}=-1\)。
分子を素因数分解すると \(1=1\)。Legendre 記号の乗法性で各因子に分ける。
積を取って \(\left(\frac{-1}{43}\right)=-1\)。

分子を素因数分解すると \(2=2\)。Legendre 記号の乗法性で各因子に分ける。
補充法則より \(\left(\frac{2}{17}\right)=(-1)^{(17^2-1)/8}\)。
\(17\equiv 1\pmod 8\) なので値は \(1\)。
積を取って \(\left(\frac{2}{17}\right)=1\)。

分子を素因数分解すると \(2=2\)。Legendre 記号の乗法性で各因子に分ける。
補充法則より \(\left(\frac{2}{23}\right)=(-1)^{(23^2-1)/8}\)。
\(23\equiv 7\pmod 8\) なので値は \(1\)。
積を取って \(\left(\frac{2}{23}\right)=1\)。

分子を素因数分解すると \(2=2\)。Legendre 記号の乗法性で各因子に分ける。
補充法則より \(\left(\frac{2}{41}\right)=(-1)^{(41^2-1)/8}\)。
\(41\equiv 1\pmod 8\) なので値は \(1\)。
積を取って \(\left(\frac{2}{41}\right)=1\)。

分子を素因数分解すると \(2=2\)。Legendre 記号の乗法性で各因子に分ける。
補充法則より \(\left(\frac{2}{73}\right)=(-1)^{(73^2-1)/8}\)。
\(73\equiv 1\pmod 8\) なので値は \(1\)。
積を取って \(\left(\frac{2}{73}\right)=1\)。

負号は \(\left(\frac{-1}{31}\right)=(-1)^{(31-1)/2}=-1\)。
分子を素因数分解すると \(2=2\)。Legendre 記号の乗法性で各因子に分ける。
補充法則より \(\left(\frac{2}{31}\right)=(-1)^{(31^2-1)/8}\)。
\(31\equiv 7\pmod 8\) なので値は \(1\)。
積を取って \(\left(\frac{-2}{31}\right)=-1\)。

負号は \(\left(\frac{-1}{47}\right)=(-1)^{(47-1)/2}=-1\)。
分子を素因数分解すると \(2=2\)。Legendre 記号の乗法性で各因子に分ける。
補充法則より \(\left(\frac{2}{47}\right)=(-1)^{(47^2-1)/8}\)。
\(47\equiv 7\pmod 8\) なので値は \(1\)。
積を取って \(\left(\frac{-2}{47}\right)=-1\)。

分子を素因数分解すると \(8=2^3\)。Legendre 記号の乗法性で各因子に分ける。
補充法則より \(\left(\frac{2}{89}\right)=(-1)^{(89^2-1)/8}\)。
\(89\equiv 1\pmod 8\) なので値は \(1\)。
積を取って \(\left(\frac{8}{89}\right)=1\)。

分子を素因数分解すると \(3=3\)。Legendre 記号の乗法性で各因子に分ける。
相互法則より \(\left(\frac{3}{11}\right)=-\left(\frac{11}{3}\right)=-\left(\frac{2}{3}\right)\)。
法 \(3\) で \(2\) は平方非剰余。
したがって値は \(1\)。
積を取って \(\left(\frac{3}{11}\right)=1\)。

分子を素因数分解すると \(3=3\)。Legendre 記号の乗法性で各因子に分ける。
相互法則より \(\left(\frac{3}{37}\right)=\left(\frac{37}{3}\right)=\left(\frac{1}{3}\right)\)。
法 \(3\) で \(1\) は平方剰余。根は \(1, 2\)。
したがって値は \(1\)。
積を取って \(\left(\frac{3}{37}\right)=1\)。

分子を素因数分解すると \(5=5\)。Legendre 記号の乗法性で各因子に分ける。
相互法則より \(\left(\frac{5}{31}\right)=\left(\frac{31}{5}\right)=\left(\frac{1}{5}\right)\)。
法 \(5\) で \(1\) は平方剰余。根は \(1, 4\)。
したがって値は \(1\)。
積を取って \(\left(\frac{5}{31}\right)=1\)。

分子を素因数分解すると \(7=7\)。Legendre 記号の乗法性で各因子に分ける。
相互法則より \(\left(\frac{7}{43}\right)=-\left(\frac{43}{7}\right)=-\left(\frac{1}{7}\right)\)。
法 \(7\) で \(1\) は平方剰余。根は \(1, 6\)。
したがって値は \(-1\)。
積を取って \(\left(\frac{7}{43}\right)=-1\)。

分子を素因数分解すると \(11=11\)。Legendre 記号の乗法性で各因子に分ける。
相互法則より \(\left(\frac{11}{59}\right)=-\left(\frac{59}{11}\right)=-\left(\frac{4}{11}\right)\)。
法 \(11\) で \(4\) は平方剰余。根は \(2, 9\)。
したがって値は \(-1\)。
積を取って \(\left(\frac{11}{59}\right)=-1\)。

分子を素因数分解すると \(13=13\)。Legendre 記号の乗法性で各因子に分ける。
相互法則より \(\left(\frac{13}{61}\right)=\left(\frac{61}{13}\right)=\left(\frac{9}{13}\right)\)。
法 \(13\) で \(9\) は平方剰余。根は \(3, 10\)。
したがって値は \(1\)。
積を取って \(\left(\frac{13}{61}\right)=1\)。

分子を素因数分解すると \(17=17\)。Legendre 記号の乗法性で各因子に分ける。
相互法則より \(\left(\frac{17}{79}\right)=\left(\frac{79}{17}\right)=\left(\frac{11}{17}\right)\)。
法 \(17\) で \(11\) は平方非剰余。
したがって値は \(-1\)。
積を取って \(\left(\frac{17}{79}\right)=-1\)。

分子を素因数分解すると \(19=19\)。Legendre 記号の乗法性で各因子に分ける。
相互法則より \(\left(\frac{19}{83}\right)=-\left(\frac{83}{19}\right)=-\left(\frac{7}{19}\right)\)。
法 \(19\) で \(7\) は平方剰余。根は \(8, 11\)。
したがって値は \(-1\)。
積を取って \(\left(\frac{19}{83}\right)=-1\)。

分子を素因数分解すると \(23=23\)。Legendre 記号の乗法性で各因子に分ける。
相互法則より \(\left(\frac{23}{97}\right)=\left(\frac{97}{23}\right)=\left(\frac{5}{23}\right)\)。
法 \(23\) で \(5\) は平方非剰余。
したがって値は \(-1\)。
積を取って \(\left(\frac{23}{97}\right)=-1\)。

分子を素因数分解すると \(29=29\)。Legendre 記号の乗法性で各因子に分ける。
相互法則より \(\left(\frac{29}{103}\right)=\left(\frac{103}{29}\right)=\left(\frac{16}{29}\right)\)。
法 \(29\) で \(16\) は平方剰余。根は \(4, 25\)。
したがって値は \(1\)。
積を取って \(\left(\frac{29}{103}\right)=1\)。

分子を素因数分解すると \(31=31\)。Legendre 記号の乗法性で各因子に分ける。
相互法則より \(\left(\frac{31}{107}\right)=-\left(\frac{107}{31}\right)=-\left(\frac{14}{31}\right)\)。
法 \(31\) で \(14\) は平方剰余。根は \(13, 18\)。
したがって値は \(-1\)。
積を取って \(\left(\frac{31}{107}\right)=-1\)。

分子を素因数分解すると \(37=37\)。Legendre 記号の乗法性で各因子に分ける。
相互法則より \(\left(\frac{37}{109}\right)=\left(\frac{109}{37}\right)=\left(\frac{35}{37}\right)\)。
法 \(37\) で \(35\) は平方非剰余。
したがって値は \(-1\)。
積を取って \(\left(\frac{37}{109}\right)=-1\)。

分子を素因数分解すると \(41=41\)。Legendre 記号の乗法性で各因子に分ける。
相互法則より \(\left(\frac{41}{131}\right)=\left(\frac{131}{41}\right)=\left(\frac{8}{41}\right)\)。
法 \(41\) で \(8\) は平方剰余。根は \(7, 34\)。
したがって値は \(1\)。
積を取って \(\left(\frac{41}{131}\right)=1\)。

分子を素因数分解すると \(43=43\)。Legendre 記号の乗法性で各因子に分ける。
相互法則より \(\left(\frac{43}{137}\right)=\left(\frac{137}{43}\right)=\left(\frac{8}{43}\right)\)。
法 \(43\) で \(8\) は平方非剰余。
したがって値は \(-1\)。
積を取って \(\left(\frac{43}{137}\right)=-1\)。

分子を素因数分解すると \(47=47\)。Legendre 記号の乗法性で各因子に分ける。
相互法則より \(\left(\frac{47}{149}\right)=\left(\frac{149}{47}\right)=\left(\frac{8}{47}\right)\)。
法 \(47\) で \(8\) は平方剰余。根は \(14, 33\)。
したがって値は \(1\)。
積を取って \(\left(\frac{47}{149}\right)=1\)。

分子を素因数分解すると \(55=5\cdot 11\)。Legendre 記号の乗法性で各因子に分ける。
相互法則より \(\left(\frac{5}{151}\right)=\left(\frac{151}{5}\right)=\left(\frac{1}{5}\right)\)。
法 \(5\) で \(1\) は平方剰余。根は \(1, 4\)。
したがって値は \(1\)。
相互法則より \(\left(\frac{11}{151}\right)=-\left(\frac{151}{11}\right)=-\left(\frac{8}{11}\right)\)。
法 \(11\) で \(8\) は平方非剰余。
したがって値は \(1\)。
積を取って \(\left(\frac{55}{151}\right)=1\)。

分子を素因数分解すると \(65=5\cdot 13\)。Legendre 記号の乗法性で各因子に分ける。
相互法則より \(\left(\frac{5}{157}\right)=\left(\frac{157}{5}\right)=\left(\frac{2}{5}\right)\)。
法 \(5\) で \(2\) は平方非剰余。
したがって値は \(-1\)。
相互法則より \(\left(\frac{13}{157}\right)=\left(\frac{157}{13}\right)=\left(\frac{1}{13}\right)\)。
法 \(13\) で \(1\) は平方剰余。根は \(1, 12\)。
したがって値は \(1\)。
積を取って \(\left(\frac{65}{157}\right)=-1\)。

分子を素因数分解すると \(77=7\cdot 11\)。Legendre 記号の乗法性で各因子に分ける。
相互法則より \(\left(\frac{7}{163}\right)=-\left(\frac{163}{7}\right)=-\left(\frac{2}{7}\right)\)。
法 \(7\) で \(2\) は平方剰余。根は \(3, 4\)。
したがって値は \(-1\)。
相互法則より \(\left(\frac{11}{163}\right)=-\left(\frac{163}{11}\right)=-\left(\frac{9}{11}\right)\)。
法 \(11\) で \(9\) は平方剰余。根は \(3, 8\)。
したがって値は \(-1\)。
積を取って \(\left(\frac{77}{163}\right)=1\)。

分子を素因数分解すると \(91=7\cdot 13\)。Legendre 記号の乗法性で各因子に分ける。
相互法則より \(\left(\frac{7}{173}\right)=\left(\frac{173}{7}\right)=\left(\frac{5}{7}\right)\)。
法 \(7\) で \(5\) は平方非剰余。
したがって値は \(-1\)。
相互法則より \(\left(\frac{13}{173}\right)=\left(\frac{173}{13}\right)=\left(\frac{4}{13}\right)\)。
法 \(13\) で \(4\) は平方剰余。根は \(2, 11\)。
したがって値は \(1\)。
積を取って \(\left(\frac{91}{173}\right)=-1\)。

分子を素因数分解すると \(105=3\cdot 5\cdot 7\)。Legendre 記号の乗法性で各因子に分ける。
相互法則より \(\left(\frac{3}{181}\right)=\left(\frac{181}{3}\right)=\left(\frac{1}{3}\right)\)。
法 \(3\) で \(1\) は平方剰余。根は \(1, 2\)。
したがって値は \(1\)。
相互法則より \(\left(\frac{5}{181}\right)=\left(\frac{181}{5}\right)=\left(\frac{1}{5}\right)\)。
法 \(5\) で \(1\) は平方剰余。根は \(1, 4\)。
したがって値は \(1\)。
相互法則より \(\left(\frac{7}{181}\right)=\left(\frac{181}{7}\right)=\left(\frac{6}{7}\right)\)。
法 \(7\) で \(6\) は平方非剰余。
したがって値は \(-1\)。
積を取って \(\left(\frac{105}{181}\right)=-1\)。

\(\left(\frac{3}{7}\right)=-1\)。したがって解は存在しない。

\(\left(\frac{5}{11}\right)=1\)。したがって解があり、根は \(4, 7\)。

\(\left(\frac{10}{13}\right)=1\)。したがって解があり、根は \(6, 7\)。

\(\left(\frac{13}{17}\right)=1\)。したがって解があり、根は \(8, 9\)。

\(\left(\frac{11}{19}\right)=1\)。したがって解があり、根は \(7, 12\)。

\(\left(\frac{6}{29}\right)=1\)。したがって解があり、根は \(8, 21\)。

\(\left(\frac{7}{31}\right)=1\)。したがって解があり、根は \(10, 21\)。

\(\left(\frac{18}{37}\right)=-1\)。したがって解は存在しない。

\(\left(\frac{30}{41}\right)=-1\)。したがって解は存在しない。

\(\left(\frac{37}{59}\right)=-1\)。したがって解は存在しない。

\(\left(\frac{52}{73}\right)=-1\)。したがって解は存在しない。

\(\left(\frac{56}{83}\right)=-1\)。したがって解は存在しない。

\(15=3\cdot 5\) なので Jacobi 記号は \(\left(\frac{2}{3}\right)^1=-1^1\) \(\left(\frac{2}{5}\right)^1=-1^1\) の積。したがって \(\left(\frac{2}{15}\right)_J=1\)。

\(21=3\cdot 7\) なので Jacobi 記号は \(\left(\frac{5}{3}\right)^1=-1^1\) \(\left(\frac{5}{7}\right)^1=-1^1\) の積。したがって \(\left(\frac{5}{21}\right)_J=1\)。

\(33=3\cdot 11\) なので Jacobi 記号は \(\left(\frac{8}{3}\right)^1=-1^1\) \(\left(\frac{8}{11}\right)^1=-1^1\) の積。したがって \(\left(\frac{8}{33}\right)_J=1\)。

\(45=3^2\cdot 5\) なので Jacobi 記号は \(\left(\frac{19}{3}\right)^2=1^2\) \(\left(\frac{19}{5}\right)^1=1^1\) の積。したがって \(\left(\frac{19}{45}\right)_J=1\)。

\(77=7\cdot 11\) なので Jacobi 記号は \(\left(\frac{17}{7}\right)^1=-1^1\) \(\left(\frac{17}{11}\right)^1=-1^1\) の積。したがって \(\left(\frac{17}{77}\right)_J=1\)。

\(91=7\cdot 13\) なので Jacobi 記号は \(\left(\frac{10}{7}\right)^1=-1^1\) \(\left(\frac{10}{13}\right)^1=1^1\) の積。したがって \(\left(\frac{10}{91}\right)_J=-1\)。

\(105=3\cdot 5\cdot 7\) なので Jacobi 記号は \(\left(\frac{31}{3}\right)^1=1^1\) \(\left(\frac{31}{5}\right)^1=1^1\) \(\left(\frac{31}{7}\right)^1=-1^1\) の積。したがって \(\left(\frac{31}{105}\right)_J=-1\)。

\(143=11\cdot 13\) なので Jacobi 記号は \(\left(\frac{37}{11}\right)^1=1^1\) \(\left(\frac{37}{13}\right)^1=-1^1\) の積。したがって \(\left(\frac{37}{143}\right)_J=-1\)。

\(221=13\cdot 17\) なので Jacobi 記号は \(\left(\frac{100}{13}\right)^1=1^1\) \(\left(\frac{100}{17}\right)^1=1^1\) の積。したがって \(\left(\frac{100}{221}\right)_J=1\)。

\(9907=9907\) なので Jacobi 記号は \(\left(\frac{1001}{9907}\right)^1=-1^1\) の積。したがって \(\left(\frac{1001}{9907}\right)_J=-1\)。

Gauss 補題は、\(a\) と奇素数 \(p\) が互いに素のとき、\(aj\) の最小正剰余が \(p/2\) を超える個数を \(\mu\) として \(\Leg{a}{p}=(-1)^\mu\) と述べる。積を比較すると \(a^M M!\equiv (-1)^\mu M!\pmod p\)。\(M!\) は \(p\) で割れないので法 \(p\) で逆元を持ち、消去できる。

もし \(qx=py\) なら、\(p\mid qx\)。\(p\nmid q\) なので \(p\mid x\)。しかし \(1\le x < p\) だから不可能。同様に \(q\mid y\) も不可能。

\((p-1)/2\) が奇数であることと \(p\equiv3\pmod4\) は同値。積が奇数になるのは両方が奇数のとき、すなわち \(p,q\equiv3\pmod4\) のときだけ。

\(\left(\frac{2}{15}\right)_J=\left(\frac{2}{3}\right)\left(\frac{2}{5}\right)=(-1)(-1)=1\)。しかし \(x^2\equiv2\pmod3\) は解を持たないので、\(x^2\equiv2\pmod{15}\) も解を持たない。

Euler 判定法より \(\Leg{a}{p}\equiv a^{(p-1)/2}\), \(\Leg{b}{p}\equiv b^{(p-1)/2}\)。積を取ると \(\Leg{a}{p}\Leg{b}{p}\equiv (ab)^{(p-1)/2}\equiv\Leg{ab}{p}\pmod p\)。両辺は \(0,\pm1\) の値なので一致する。

\(p\equiv1,7\pmod8\) なら \(p^2\equiv1\pmod{16}\) なので \((p^2-1)/8\) は偶数。\(p\equiv3,5\pmod8\) なら \(p^2\equiv9\pmod{16}\) なので奇数。