1. 計算ツール
Legendre / Jacobi 記号計算機
平方剰余表ジェネレータ
2. 小さい奇素数の平方剰余表
まずは手で見える範囲の表です。\(a\) が平方剰余なら \(\Leg{a}{p}=1\)、平方非剰余なら \(-1\) です。
法 \(3\)
非零平方剰余：\(1\)
| a | \((a/3)\) | 根 |
|---|---|---|
| 1 | 1 | 1, 2 |
| 2 | -1 | なし |
法 \(5\)
非零平方剰余：\(1, 4\)
| a | \((a/5)\) | 根 |
|---|---|---|
| 1 | 1 | 1, 4 |
| 2 | -1 | なし |
| 3 | -1 | なし |
| 4 | 1 | 2, 3 |
法 \(7\)
非零平方剰余：\(1, 2, 4\)
| a | \((a/7)\) | 根 |
|---|---|---|
| 1 | 1 | 1, 6 |
| 2 | 1 | 3, 4 |
| 3 | -1 | なし |
| 4 | 1 | 2, 5 |
| 5 | -1 | なし |
| 6 | -1 | なし |
法 \(11\)
非零平方剰余：\(1, 3, 4, 5, 9\)
| a | \((a/11)\) | 根 |
|---|---|---|
| 1 | 1 | 1, 10 |
| 2 | -1 | なし |
| 3 | 1 | 5, 6 |
| 4 | 1 | 2, 9 |
| 5 | 1 | 4, 7 |
| 6 | -1 | なし |
| 7 | -1 | なし |
| 8 | -1 | なし |
| 9 | 1 | 3, 8 |
| 10 | -1 | なし |
法 \(13\)
非零平方剰余：\(1, 3, 4, 9, 10, 12\)
| a | \((a/13)\) | 根 |
|---|---|---|
| 1 | 1 | 1, 12 |
| 2 | -1 | なし |
| 3 | 1 | 4, 9 |
| 4 | 1 | 2, 11 |
| 5 | -1 | なし |
| 6 | -1 | なし |
| 7 | -1 | なし |
| 8 | -1 | なし |
| 9 | 1 | 3, 10 |
| 10 | 1 | 6, 7 |
| 11 | -1 | なし |
| 12 | 1 | 5, 8 |
法 \(17\)
非零平方剰余：\(1, 2, 4, 8, 9, 13, 15, 16\)
| a | \((a/17)\) | 根 |
|---|---|---|
| 1 | 1 | 1, 16 |
| 2 | 1 | 6, 11 |
| 3 | -1 | なし |
| 4 | 1 | 2, 15 |
| 5 | -1 | なし |
| 6 | -1 | なし |
| 7 | -1 | なし |
| 8 | 1 | 5, 12 |
| 9 | 1 | 3, 14 |
| 10 | -1 | なし |
| 11 | -1 | なし |
| 12 | -1 | なし |
| 13 | 1 | 8, 9 |
| 14 | -1 | なし |
| 15 | 1 | 7, 10 |
| 16 | 1 | 4, 13 |
法 \(19\)
非零平方剰余：\(1, 4, 5, 6, 7, 9, 11, 16, 17\)
| a | \((a/19)\) | 根 |
|---|---|---|
| 1 | 1 | 1, 18 |
| 2 | -1 | なし |
| 3 | -1 | なし |
| 4 | 1 | 2, 17 |
| 5 | 1 | 9, 10 |
| 6 | 1 | 5, 14 |
| 7 | 1 | 8, 11 |
| 8 | -1 | なし |
| 9 | 1 | 3, 16 |
| 10 | -1 | なし |
| 11 | 1 | 7, 12 |
| 12 | -1 | なし |
| 13 | -1 | なし |
| 14 | -1 | なし |
| 15 | -1 | なし |
| 16 | 1 | 4, 15 |
| 17 | 1 | 6, 13 |
| 18 | -1 | なし |
法 \(23\)
非零平方剰余：\(1, 2, 3, 4, 6, 8, 9, 12, 13, 16, 18\)
| a | \((a/23)\) | 根 |
|---|---|---|
| 1 | 1 | 1, 22 |
| 2 | 1 | 5, 18 |
| 3 | 1 | 7, 16 |
| 4 | 1 | 2, 21 |
| 5 | -1 | なし |
| 6 | 1 | 11, 12 |
| 7 | -1 | なし |
| 8 | 1 | 10, 13 |
| 9 | 1 | 3, 20 |
| 10 | -1 | なし |
| 11 | -1 | なし |
| 12 | 1 | 9, 14 |
| 13 | 1 | 6, 17 |
| 14 | -1 | なし |
| 15 | -1 | なし |
| 16 | 1 | 4, 19 |
| 17 | -1 | なし |
| 18 | 1 | 8, 15 |
| 19 | -1 | なし |
| 20 | -1 | なし |
| 21 | -1 | なし |
| 22 | -1 | なし |
法 \(29\)
非零平方剰余：\(1, 4, 5, 6, 7, 9, 13, 16, 20, 22, 23, 24, 25, 28\)
| a | \((a/29)\) | 根 |
|---|---|---|
| 1 | 1 | 1, 28 |
| 2 | -1 | なし |
| 3 | -1 | なし |
| 4 | 1 | 2, 27 |
| 5 | 1 | 11, 18 |
| 6 | 1 | 8, 21 |
| 7 | 1 | 6, 23 |
| 8 | -1 | なし |
| 9 | 1 | 3, 26 |
| 10 | -1 | なし |
| 11 | -1 | なし |
| 12 | -1 | なし |
| 13 | 1 | 10, 19 |
| 14 | -1 | なし |
| 15 | -1 | なし |
| 16 | 1 | 4, 25 |
| 17 | -1 | なし |
| 18 | -1 | なし |
| 19 | -1 | なし |
| 20 | 1 | 7, 22 |
| 21 | -1 | なし |
| 22 | 1 | 14, 15 |
| 23 | 1 | 9, 20 |
| 24 | 1 | 13, 16 |
| 25 | 1 | 5, 24 |
| 26 | -1 | なし |
| 27 | -1 | なし |
| 28 | 1 | 12, 17 |
法 \(31\)
非零平方剰余：\(1, 2, 4, 5, 7, 8, 9, 10, 14, 16, 18, 19, 20, 25, 28\)
| a | \((a/31)\) | 根 |
|---|---|---|
| 1 | 1 | 1, 30 |
| 2 | 1 | 8, 23 |
| 3 | -1 | なし |
| 4 | 1 | 2, 29 |
| 5 | 1 | 6, 25 |
| 6 | -1 | なし |
| 7 | 1 | 10, 21 |
| 8 | 1 | 15, 16 |
| 9 | 1 | 3, 28 |
| 10 | 1 | 14, 17 |
| 11 | -1 | なし |
| 12 | -1 | なし |
| 13 | -1 | なし |
| 14 | 1 | 13, 18 |
| 15 | -1 | なし |
| 16 | 1 | 4, 27 |
| 17 | -1 | なし |
| 18 | 1 | 7, 24 |
| 19 | 1 | 9, 22 |
| 20 | 1 | 12, 19 |
| 21 | -1 | なし |
| 22 | -1 | なし |
| 23 | -1 | なし |
| 24 | -1 | なし |
| 25 | 1 | 5, 26 |
| 26 | -1 | なし |
| 27 | -1 | なし |
| 28 | 1 | 11, 20 |
| 29 | -1 | なし |
| 30 | -1 | なし |
3. Legendre 記号の計算例
ここでは、補充法則・乗法性・相互法則を実際に使います。各例で最も重要なのは、分子を素因数へ分け、奇素数因子について法を交換することです。
例 1: \(\left(\frac{3}{11}\right)\)
分子を素因数分解すると \(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\)。
例 2: \(\left(\frac{3}{13}\right)\)
分子を素因数分解すると \(3=3\)。Legendre 記号の乗法性で各因子に分ける。
相互法則より \(\left(\frac{3}{13}\right)=\left(\frac{13}{3}\right)=\left(\frac{1}{3}\right)\)。
法 \(3\) で \(1\) は平方剰余。根は \(1, 2\)。
したがって値は \(1\)。
積を取って \(\left(\frac{3}{13}\right)=1\)。
例 3: \(\left(\frac{5}{19}\right)\)
分子を素因数分解すると \(5=5\)。Legendre 記号の乗法性で各因子に分ける。
相互法則より \(\left(\frac{5}{19}\right)=\left(\frac{19}{5}\right)=\left(\frac{4}{5}\right)\)。
法 \(5\) で \(4\) は平方剰余。根は \(2, 3\)。
したがって値は \(1\)。
積を取って \(\left(\frac{5}{19}\right)=1\)。
例 4: \(\left(\frac{7}{29}\right)\)
分子を素因数分解すると \(7=7\)。Legendre 記号の乗法性で各因子に分ける。
相互法則より \(\left(\frac{7}{29}\right)=\left(\frac{29}{7}\right)=\left(\frac{1}{7}\right)\)。
法 \(7\) で \(1\) は平方剰余。根は \(1, 6\)。
したがって値は \(1\)。
積を取って \(\left(\frac{7}{29}\right)=1\)。
例 5: \(\left(\frac{11}{31}\right)\)
分子を素因数分解すると \(11=11\)。Legendre 記号の乗法性で各因子に分ける。
相互法則より \(\left(\frac{11}{31}\right)=-\left(\frac{31}{11}\right)=-\left(\frac{9}{11}\right)\)。
法 \(11\) で \(9\) は平方剰余。根は \(3, 8\)。
したがって値は \(-1\)。
積を取って \(\left(\frac{11}{31}\right)=-1\)。
例 6: \(\left(\frac{13}{41}\right)\)
分子を素因数分解すると \(13=13\)。Legendre 記号の乗法性で各因子に分ける。
相互法則より \(\left(\frac{13}{41}\right)=\left(\frac{41}{13}\right)=\left(\frac{2}{13}\right)\)。
法 \(13\) で \(2\) は平方非剰余。
したがって値は \(-1\)。
積を取って \(\left(\frac{13}{41}\right)=-1\)。
例 7: \(\left(\frac{17}{43}\right)\)
分子を素因数分解すると \(17=17\)。Legendre 記号の乗法性で各因子に分ける。
相互法則より \(\left(\frac{17}{43}\right)=\left(\frac{43}{17}\right)=\left(\frac{9}{17}\right)\)。
法 \(17\) で \(9\) は平方剰余。根は \(3, 14\)。
したがって値は \(1\)。
積を取って \(\left(\frac{17}{43}\right)=1\)。
例 8: \(\left(\frac{19}{53}\right)\)
分子を素因数分解すると \(19=19\)。Legendre 記号の乗法性で各因子に分ける。
相互法則より \(\left(\frac{19}{53}\right)=\left(\frac{53}{19}\right)=\left(\frac{15}{19}\right)\)。
法 \(19\) で \(15\) は平方非剰余。
したがって値は \(-1\)。
積を取って \(\left(\frac{19}{53}\right)=-1\)。
例 9: \(\left(\frac{29}{71}\right)\)
分子を素因数分解すると \(29=29\)。Legendre 記号の乗法性で各因子に分ける。
相互法則より \(\left(\frac{29}{71}\right)=\left(\frac{71}{29}\right)=\left(\frac{13}{29}\right)\)。
法 \(29\) で \(13\) は平方剰余。根は \(10, 19\)。
したがって値は \(1\)。
積を取って \(\left(\frac{29}{71}\right)=1\)。
例 10: \(\left(\frac{31}{103}\right)\)
分子を素因数分解すると \(31=31\)。Legendre 記号の乗法性で各因子に分ける。
相互法則より \(\left(\frac{31}{103}\right)=-\left(\frac{103}{31}\right)=-\left(\frac{10}{31}\right)\)。
法 \(31\) で \(10\) は平方剰余。根は \(14, 17\)。
したがって値は \(-1\)。
積を取って \(\left(\frac{31}{103}\right)=-1\)。
例 11: \(\left(\frac{-1}{43}\right)\)
負号は \(\left(\frac{-1}{43}\right)=(-1)^{(43-1)/2}=-1\)。
分子を素因数分解すると \(1=1\)。Legendre 記号の乗法性で各因子に分ける。
積を取って \(\left(\frac{-1}{43}\right)=-1\)。
例 12: \(\left(\frac{2}{73}\right)\)
分子を素因数分解すると \(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\)。
例 13: \(\left(\frac{6}{37}\right)\)
分子を素因数分解すると \(6=2\cdot 3\)。Legendre 記号の乗法性で各因子に分ける。
補充法則より \(\left(\frac{2}{37}\right)=(-1)^{(37^2-1)/8}\)。
\(37\equiv 5\pmod 8\) なので値は \(-1\)。
相互法則より \(\left(\frac{3}{37}\right)=\left(\frac{37}{3}\right)=\left(\frac{1}{3}\right)\)。
法 \(3\) で \(1\) は平方剰余。根は \(1, 2\)。
したがって値は \(1\)。
積を取って \(\left(\frac{6}{37}\right)=-1\)。
例 14: \(\left(\frac{10}{59}\right)\)
分子を素因数分解すると \(10=2\cdot 5\)。Legendre 記号の乗法性で各因子に分ける。
補充法則より \(\left(\frac{2}{59}\right)=(-1)^{(59^2-1)/8}\)。
\(59\equiv 3\pmod 8\) なので値は \(-1\)。
相互法則より \(\left(\frac{5}{59}\right)=\left(\frac{59}{5}\right)=\left(\frac{4}{5}\right)\)。
法 \(5\) で \(4\) は平方剰余。根は \(2, 3\)。
したがって値は \(1\)。
積を取って \(\left(\frac{10}{59}\right)=-1\)。
例 15: \(\left(\frac{14}{83}\right)\)
分子を素因数分解すると \(14=2\cdot 7\)。Legendre 記号の乗法性で各因子に分ける。
補充法則より \(\left(\frac{2}{83}\right)=(-1)^{(83^2-1)/8}\)。
\(83\equiv 3\pmod 8\) なので値は \(-1\)。
相互法則より \(\left(\frac{7}{83}\right)=-\left(\frac{83}{7}\right)=-\left(\frac{6}{7}\right)\)。
法 \(7\) で \(6\) は平方非剰余。
したがって値は \(1\)。
積を取って \(\left(\frac{14}{83}\right)=-1\)。
例 16: \(\left(\frac{30}{101}\right)\)
分子を素因数分解すると \(30=2\cdot 3\cdot 5\)。Legendre 記号の乗法性で各因子に分ける。
補充法則より \(\left(\frac{2}{101}\right)=(-1)^{(101^2-1)/8}\)。
\(101\equiv 5\pmod 8\) なので値は \(-1\)。
相互法則より \(\left(\frac{3}{101}\right)=\left(\frac{101}{3}\right)=\left(\frac{2}{3}\right)\)。
法 \(3\) で \(2\) は平方非剰余。
したがって値は \(-1\)。
相互法則より \(\left(\frac{5}{101}\right)=\left(\frac{101}{5}\right)=\left(\frac{1}{5}\right)\)。
法 \(5\) で \(1\) は平方剰余。根は \(1, 4\)。
したがって値は \(1\)。
積を取って \(\left(\frac{30}{101}\right)=1\)。
例 17: \(\left(\frac{77}{109}\right)\)
分子を素因数分解すると \(77=7\cdot 11\)。Legendre 記号の乗法性で各因子に分ける。
相互法則より \(\left(\frac{7}{109}\right)=\left(\frac{109}{7}\right)=\left(\frac{4}{7}\right)\)。
法 \(7\) で \(4\) は平方剰余。根は \(2, 5\)。
したがって値は \(1\)。
相互法則より \(\left(\frac{11}{109}\right)=\left(\frac{109}{11}\right)=\left(\frac{10}{11}\right)\)。
法 \(11\) で \(10\) は平方非剰余。
したがって値は \(-1\)。
積を取って \(\left(\frac{77}{109}\right)=-1\)。
例 18: \(\left(\frac{154}{167}\right)\)
分子を素因数分解すると \(154=2\cdot 7\cdot 11\)。Legendre 記号の乗法性で各因子に分ける。
補充法則より \(\left(\frac{2}{167}\right)=(-1)^{(167^2-1)/8}\)。
\(167\equiv 7\pmod 8\) なので値は \(1\)。
相互法則より \(\left(\frac{7}{167}\right)=-\left(\frac{167}{7}\right)=-\left(\frac{6}{7}\right)\)。
法 \(7\) で \(6\) は平方非剰余。
したがって値は \(1\)。
相互法則より \(\left(\frac{11}{167}\right)=-\left(\frac{167}{11}\right)=-\left(\frac{2}{11}\right)\)。
法 \(11\) で \(2\) は平方非剰余。
したがって値は \(1\)。
積を取って \(\left(\frac{154}{167}\right)=1\)。
例 19: \(\left(\frac{65}{197}\right)\)
分子を素因数分解すると \(65=5\cdot 13\)。Legendre 記号の乗法性で各因子に分ける。
相互法則より \(\left(\frac{5}{197}\right)=\left(\frac{197}{5}\right)=\left(\frac{2}{5}\right)\)。
法 \(5\) で \(2\) は平方非剰余。
したがって値は \(-1\)。
相互法則より \(\left(\frac{13}{197}\right)=\left(\frac{197}{13}\right)=\left(\frac{2}{13}\right)\)。
法 \(13\) で \(2\) は平方非剰余。
したがって値は \(-1\)。
積を取って \(\left(\frac{65}{197}\right)=1\)。
例 20: \(\left(\frac{110}{211}\right)\)
分子を素因数分解すると \(110=2\cdot 5\cdot 11\)。Legendre 記号の乗法性で各因子に分ける。
補充法則より \(\left(\frac{2}{211}\right)=(-1)^{(211^2-1)/8}\)。
\(211\equiv 3\pmod 8\) なので値は \(-1\)。
相互法則より \(\left(\frac{5}{211}\right)=\left(\frac{211}{5}\right)=\left(\frac{1}{5}\right)\)。
法 \(5\) で \(1\) は平方剰余。根は \(1, 4\)。
したがって値は \(1\)。
相互法則より \(\left(\frac{11}{211}\right)=-\left(\frac{211}{11}\right)=-\left(\frac{2}{11}\right)\)。
法 \(11\) で \(2\) は平方非剰余。
したがって値は \(1\)。
積を取って \(\left(\frac{110}{211}\right)=-1\)。
例 21: \(\left(\frac{91}{223}\right)\)
分子を素因数分解すると \(91=7\cdot 13\)。Legendre 記号の乗法性で各因子に分ける。
相互法則より \(\left(\frac{7}{223}\right)=-\left(\frac{223}{7}\right)=-\left(\frac{6}{7}\right)\)。
法 \(7\) で \(6\) は平方非剰余。
したがって値は \(1\)。
相互法則より \(\left(\frac{13}{223}\right)=\left(\frac{223}{13}\right)=\left(\frac{2}{13}\right)\)。
法 \(13\) で \(2\) は平方非剰余。
したがって値は \(-1\)。
積を取って \(\left(\frac{91}{223}\right)=-1\)。
例 22: \(\left(\frac{143}{229}\right)\)
分子を素因数分解すると \(143=11\cdot 13\)。Legendre 記号の乗法性で各因子に分ける。
相互法則より \(\left(\frac{11}{229}\right)=\left(\frac{229}{11}\right)=\left(\frac{9}{11}\right)\)。
法 \(11\) で \(9\) は平方剰余。根は \(3, 8\)。
したがって値は \(1\)。
相互法則より \(\left(\frac{13}{229}\right)=\left(\frac{229}{13}\right)=\left(\frac{8}{13}\right)\)。
法 \(13\) で \(8\) は平方非剰余。
したがって値は \(-1\)。
積を取って \(\left(\frac{143}{229}\right)=-1\)。
例 23: \(\left(\frac{210}{251}\right)\)
分子を素因数分解すると \(210=2\cdot 3\cdot 5\cdot 7\)。Legendre 記号の乗法性で各因子に分ける。
補充法則より \(\left(\frac{2}{251}\right)=(-1)^{(251^2-1)/8}\)。
\(251\equiv 3\pmod 8\) なので値は \(-1\)。
相互法則より \(\left(\frac{3}{251}\right)=-\left(\frac{251}{3}\right)=-\left(\frac{2}{3}\right)\)。
法 \(3\) で \(2\) は平方非剰余。
したがって値は \(1\)。
相互法則より \(\left(\frac{5}{251}\right)=\left(\frac{251}{5}\right)=\left(\frac{1}{5}\right)\)。
法 \(5\) で \(1\) は平方剰余。根は \(1, 4\)。
したがって値は \(1\)。
相互法則より \(\left(\frac{7}{251}\right)=-\left(\frac{251}{7}\right)=-\left(\frac{6}{7}\right)\)。
法 \(7\) で \(6\) は平方非剰余。
したがって値は \(1\)。
積を取って \(\left(\frac{210}{251}\right)=-1\)。
例 24: \(\left(\frac{255}{257}\right)\)
分子を素因数分解すると \(255=3\cdot 5\cdot 17\)。Legendre 記号の乗法性で各因子に分ける。
相互法則より \(\left(\frac{3}{257}\right)=\left(\frac{257}{3}\right)=\left(\frac{2}{3}\right)\)。
法 \(3\) で \(2\) は平方非剰余。
したがって値は \(-1\)。
相互法則より \(\left(\frac{5}{257}\right)=\left(\frac{257}{5}\right)=\left(\frac{2}{5}\right)\)。
法 \(5\) で \(2\) は平方非剰余。
したがって値は \(-1\)。
相互法則より \(\left(\frac{17}{257}\right)=\left(\frac{257}{17}\right)=\left(\frac{2}{17}\right)\)。
法 \(17\) で \(2\) は平方剰余。根は \(6, 11\)。
したがって値は \(1\)。
積を取って \(\left(\frac{255}{257}\right)=1\)。
例 25: \(\left(\frac{1001}{991}\right)\)
分子を素因数分解すると \(1001=7\cdot 11\cdot 13\)。Legendre 記号の乗法性で各因子に分ける。
相互法則より \(\left(\frac{7}{991}\right)=-\left(\frac{991}{7}\right)=-\left(\frac{4}{7}\right)\)。
法 \(7\) で \(4\) は平方剰余。根は \(2, 5\)。
したがって値は \(-1\)。
相互法則より \(\left(\frac{11}{991}\right)=-\left(\frac{991}{11}\right)=-\left(\frac{1}{11}\right)\)。
法 \(11\) で \(1\) は平方剰余。根は \(1, 10\)。
したがって値は \(-1\)。
相互法則より \(\left(\frac{13}{991}\right)=\left(\frac{991}{13}\right)=\left(\frac{3}{13}\right)\)。
法 \(13\) で \(3\) は平方剰余。根は \(4, 9\)。
したがって値は \(1\)。
積を取って \(\left(\frac{1001}{991}\right)=1\)。
4. 合同方程式 \(x^2\equiv a\pmod p\) の例
Legendre 記号が \(-1\) なら根は存在せず、\(1\) ならちょうど 2 個の根があります。ただし \(a\equiv0\pmod p\) の場合は根は 1 個、すなわち \(x\equiv0\) です。
| # | 合同式 | 判定 | 根 |
|---|---|---|---|
| 1 | \(x^2\equiv 4\pmod{7}\) | \(\left(\frac{4}{7}\right)=1\) | 2, 5 |
| 2 | \(x^2\equiv 5\pmod{11}\) | \(\left(\frac{5}{11}\right)=1\) | 4, 7 |
| 3 | \(x^2\equiv 10\pmod{13}\) | \(\left(\frac{10}{13}\right)=1\) | 6, 7 |
| 4 | \(x^2\equiv 9\pmod{17}\) | \(\left(\frac{9}{17}\right)=1\) | 3, 14 |
| 5 | \(x^2\equiv 13\pmod{23}\) | \(\left(\frac{13}{23}\right)=1\) | 6, 17 |
| 6 | \(x^2\equiv 6\pmod{29}\) | \(\left(\frac{6}{29}\right)=1\) | 8, 21 |
| 7 | \(x^2\equiv 20\pmod{31}\) | \(\left(\frac{20}{31}\right)=1\) | 12, 19 |
| 8 | \(x^2\equiv 11\pmod{41}\) | \(\left(\frac{11}{41}\right)=-1\) | 解なし |
| 9 | \(x^2\equiv 25\pmod{43}\) | \(\left(\frac{25}{43}\right)=1\) | 5, 38 |
| 10 | \(x^2\equiv 37\pmod{59}\) | \(\left(\frac{37}{59}\right)=-1\) | 解なし |
| 11 | \(x^2\equiv 56\pmod{83}\) | \(\left(\frac{56}{83}\right)=-1\) | 解なし |
| 12 | \(x^2\equiv 64\pmod{101}\) | \(\left(\frac{64}{101}\right)=1\) | 8, 93 |
根の探索ツール
5. Jacobi 記号の例：値 \(1\) は「平方剰余」を保証しない
Jacobi 記号は、\(n=\prod p_i^{e_i}\) に対して \(\left(\frac{a}{n}\right)_J=\prod_i\left(\frac{a}{p_i}\right)^{e_i}\) と定義されます。これは計算には便利ですが、合成数法での平方剰余性とは一致しません。
| 記号 | 法の分解 | Jacobi 値 | 実際の根 |
|---|---|---|---|
| \(\left(\frac{2}{15}\right)_J\) | \(15=3\cdot 5\) | 1 | 解なし |
| \(\left(\frac{5}{21}\right)_J\) | \(21=3\cdot 7\) | 1 | 解なし |
| \(\left(\frac{8}{33}\right)_J\) | \(33=3\cdot 11\) | 1 | 解なし |
| \(\left(\frac{19}{45}\right)_J\) | \(45=3^2\cdot 5\) | 1 | 8, 17, 28, 37 |
| \(\left(\frac{17}{77}\right)_J\) | \(77=7\cdot 11\) | 1 | 解なし |
| \(\left(\frac{10}{91}\right)_J\) | \(91=7\cdot 13\) | -1 | 解なし |
| \(\left(\frac{31}{105}\right)_J\) | \(105=3\cdot 5\cdot 7\) | -1 | 解なし |
| \(\left(\frac{1001}{9907}\right)_J\) | \(9907=9907\) | -1 | 大きいので表では省略 |
6. 例から見えるパターン
\(-1\) は mod 4
\(\Leg{-1}{p}=1\) となるのは \(p\equiv1\pmod4\) のとき、\(-1\) となるのは \(p\equiv3\pmod4\) のときです。
\(2\) は mod 8
\(\Leg{2}{p}=1\) となるのは \(p\equiv1,7\pmod8\)、\(-1\) となるのは \(p\equiv3,5\pmod8\) のときです。
交換符号は mod 4
\(\Leg{p}{q}\) と \(\Leg{q}{p}\) が逆符号になるのは、\(p,q\) がどちらも \(3\pmod4\) のときだけです。