ルジャンドル記号

数論において、ルジャンドル記号（るじゃんどるきごう、テンプレート:Lang-en-short）は数 テンプレート:Mvar が奇素数（すなわち 3 以上の素数）テンプレート:Mvar を法とするゼロでない平方剰余かを分類する乗法的関数である。ルジャンドル記号の値はそれぞれ、テンプレート:Mvar を法として テンプレート:Mvar がゼロでない平方剰余なら 1、非平方剰余なら −1、ゼロなら 0 となる。 名称はこの関数を導入した数学者、アドリアン＝マリ・ルジャンドルに因む。

ルジャンドル記号は、1798年に平方剰余の法則を証明しようとしたアドリアン＝マリ・ルジャンドルにより導入された。この記号の一般化には高次のヤコビ記号やディリクレ指標が含まれる。ルジャンドル記号の表記上の便利さは、テンプレート:仮リンクやアルティン記号などの代数的整数論で使用される他のいくつかの「記号」の導入に影響を与えた。

いくつかの テンプレート:Mvar と テンプレート:Mvar のときのルジャンドル記号 (テンプレート:Math)

	テンプレート:Math	1	2	3	4	5	6	7	8	9	10
テンプレート:Math	0	1	−1
5	0	1	−1	−1	1
7	0	1	1	−1	1	−1	−1
11	0	1	−1	1	1	1	−1	−1	−1	1	−1
テンプレート:Mvar を法として合同ならルジャンドル記号の値は等しくなるため、テンプレート:Math の場合の値のみ示す。表では テンプレート:Mvar が平方剰余となる（ルジャンドル記号の値が 0 または 1）部分を黄色で強調している。

定義

$p$ を奇数の素数とする。整数 $a$ が $p$ を法とする完全平方と合同である場合は、$a$ は $p$ を法とする平方剰余であり、そうでない場合は $p$ を法とする平方非剰余である。ルジャンドル記号は次のように定義される $a$ と $p$ の関数である。

$\left(\frac{a}{p}\right)=\{\begin{array}{cc}1& \text{if }a\text{ is a quadratic residue modulo }p\text{ and }a\equiv ̸0(\mathrm{mod}p),\\ -1& \text{if }a\text{ is a non-quadratic residue modulo }p,\\ 0& \text{if }a\equiv 0(\mathrm{mod}p).\end{array}$

ルジャンドルによる最初の定義は、次のように式を明示したものだった。

$\left(\frac{a}{p}\right)\equiv a^{\frac{p-1}{2}}(\mathrm{mod}p)\text{ and }\left(\frac{a}{p}\right)\in \{-1,0,1\}.$

先に発見されルジャンドルにも知られていたオイラーの規準によると、これら2つの定義は同等である。よって、ルジャンルドルが貢献したのは、mod pでのaの平方剰余性を記録する便利な表記法を導入したことにあった。比較の目的で、ガウスはaがpを法とする剰余であるか非剰余であるかに応じて、aRpとaNpという表記を使用した。印刷の都合上、ルジャンドル記号は(a | p) または (a/p) と表記されることがある。a が0, 1, 2,...であるときの数列 (a | p) は周期pで周期的であり、ルジャンドル数列と呼ばれることがある。{0,1,−1}という値は{1,0,1}または{0,1,0}であることがある。次の表の各行は、説明したように周期性を示していることが分かる。

値の表

ルジャンドル記号 $\left(\frac{a}{p}\right)$ の表 (p ≤ 127, a ≤ 30, p は奇素数)

縦 p 横 a	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30
3	テンプレート:01	−1	0	テンプレート:01	−1	0	1	−1	テンプレート:00	1	−1	0	1	−1	0	テンプレート:01	−1	0	1	−1	0	1	−1	0	テンプレート:01	−1	0	1	−1	0
5	1	−1	−1	1	0	1	−1	−1	1	0	1	−1	−1	1	0	1	−1	−1	1	0	1	−1	−1	1	0	1	−1	−1	1	0
7	1	1	−1	1	−1	−1	0	1	1	−1	1	−1	−1	0	1	1	−1	1	−1	−1	0	1	1	−1	1	−1	−1	0	1	1
11	1	−1	1	1	1	−1	−1	−1	1	−1	0	1	−1	1	1	1	−1	−1	−1	1	−1	0	1	−1	1	1	1	−1	−1	−1
13	1	−1	1	1	−1	−1	−1	−1	1	1	−1	1	0	1	−1	1	1	−1	−1	−1	−1	1	1	−1	1	0	1	−1	1	1
17	1	1	−1	1	−1	−1	−1	1	1	−1	−1	−1	1	−1	1	1	0	1	1	−1	1	−1	−1	−1	1	1	−1	−1	−1	1
19	1	−1	−1	1	1	1	1	−1	1	−1	1	−1	−1	−1	−1	1	1	−1	0	1	−1	−1	1	1	1	1	−1	1	−1	1
23	1	1	1	1	−1	1	−1	1	1	−1	−1	1	1	−1	−1	1	−1	1	−1	−1	−1	−1	0	1	1	1	1	−1	1	−1
29	1	−1	−1	1	1	1	1	−1	1	−1	−1	−1	1	−1	−1	1	−1	−1	−1	1	−1	1	1	1	1	−1	−1	1	0	1
31	1	1	−1	1	1	−1	1	1	1	1	−1	−1	−1	1	−1	1	−1	1	1	1	−1	−1	−1	−1	1	−1	−1	1	−1	−1
37	1	−1	1	1	−1	−1	1	−1	1	1	1	1	−1	−1	−1	1	−1	−1	−1	−1	1	−1	−1	−1	1	1	1	1	−1	1
41	1	1	−1	1	1	−1	−1	1	1	1	−1	−1	−1	−1	−1	1	−1	1	−1	1	1	−1	1	−1	1	−1	−1	−1	−1	−1
43	1	−1	−1	1	−1	1	−1	−1	1	1	1	−1	1	1	1	1	1	−1	−1	−1	1	−1	1	1	1	−1	−1	−1	−1	−1
47	1	1	1	1	−1	1	1	1	1	−1	−1	1	−1	1	−1	1	1	1	−1	−1	1	−1	−1	1	1	−1	1	1	−1	−1
53	1	−1	−1	1	−1	1	1	−1	1	1	1	−1	1	−1	1	1	1	−1	−1	−1	−1	−1	−1	1	1	−1	−1	1	1	−1
59	1	−1	1	1	1	−1	1	−1	1	−1	−1	1	−1	−1	1	1	1	−1	1	1	1	1	−1	−1	1	1	1	1	1	−1
61	1	−1	1	1	1	−1	−1	−1	1	−1	−1	1	1	1	1	1	−1	−1	1	1	−1	1	−1	−1	1	−1	1	−1	−1	−1
67	1	−1	−1	1	−1	1	−1	−1	1	1	−1	−1	−1	1	1	1	1	−1	1	−1	1	1	1	1	1	1	−1	−1	1	−1
71	1	1	1	1	1	1	−1	1	1	1	−1	1	−1	−1	1	1	−1	1	1	1	−1	−1	−1	1	1	−1	1	−1	1	1
73	1	1	1	1	−1	1	−1	1	1	−1	−1	1	−1	−1	−1	1	−1	1	1	−1	−1	−1	1	1	1	−1	1	−1	−1	−1
79	1	1	−1	1	1	−1	−1	1	1	1	1	−1	1	−1	−1	1	−1	1	1	1	1	1	1	−1	1	1	−1	−1	−1	−1
83	1	−1	1	1	−1	−1	1	−1	1	1	1	1	−1	−1	−1	1	1	−1	−1	−1	1	−1	1	−1	1	1	1	1	1	1
89	1	1	−1	1	1	−1	−1	1	1	1	1	−1	−1	−1	−1	1	1	1	−1	1	1	1	−1	−1	1	−1	−1	−1	−1	−1
97	1	1	1	1	−1	1	−1	1	1	−1	1	1	−1	−1	−1	1	−1	1	−1	−1	−1	1	−1	1	1	−1	1	−1	−1	−1
101	1	−1	−1	1	1	1	−1	−1	1	−1	−1	−1	1	1	−1	1	1	−1	1	1	1	1	1	1	1	−1	−1	−1	−1	1
103	1	1	−1	1	−1	−1	1	1	1	−1	−1	−1	1	1	1	1	1	1	1	−1	−1	−1	1	−1	1	1	−1	1	1	1
107	1	−1	1	1	−1	−1	−1	−1	1	1	1	1	1	1	−1	1	−1	−1	1	−1	−1	−1	1	−1	1	−1	1	−1	1	1
109	1	−1	1	1	1	−1	1	−1	1	−1	−1	1	−1	−1	1	1	−1	−1	−1	1	1	1	−1	−1	1	1	1	1	1	−1
113	1	1	−1	1	−1	−1	1	1	1	−1	1	−1	1	1	1	1	−1	1	−1	−1	−1	1	−1	−1	1	1	−1	1	−1	1
127	1	1	−1	1	−1	−1	−1	1	1	−1	1	−1	1	−1	1	1	1	1	1	−1	1	1	−1	−1	1	1	−1	−1	−1	1

ルジャンドル記号の性質

ルジャンドル記号には平方剰余の法則とともに効率的に計算するために使うことのできる便利な性質がいくつかある。

• $p\equiv 3(\text{mod }4)$ の場合、

  $\frac{p+1}{4}+\frac{p+1}{4}=\frac{(p-1)+2}{2}$ という事実は$a=x^{(p+1)/4}$ が平方剰余 $x$ の平方根であることを提供する。

• a ≡ b (mod p)の場合、ルジャンドル記号は1番目の（上の）引数において周期的である。

  $\left(\frac{a}{p}\right)=\left(\frac{b}{p}\right).$

• ルジャンドル記号は、上の引数の完全乗法的関数(en:completely multiplicative function)である。

  $\left(\frac{ab}{p}\right)=\left(\frac{a}{p}\right)\left(\frac{b}{p}\right).$

• 特に、pを法とし共に平方剰余である、またはともに平方非剰余である2つの数の積は剰余であるが、剰余と非剰余の積は非剰余である。特別なケースは平方数のルジャンドル記号である。

  $\left(\frac{x^2}{p}\right)=\{\begin{array}{cc}1& \text{if }p\nmid x\\ 0& \text{if }p\mid x.\end{array}$

• a の関数としてみた時、ルジャンドル記号 $\left(\frac{a}{p}\right)$ はpを法とする一意の2次ディリクレ指標となる。
• 平方剰余の法則の第1補足

  $\left(\frac{-1}{p}\right)=(-1{)}^{\frac{p-1}{2}}=\{\begin{array}{cc}1& \text{ if }p\equiv 1(\mathrm{mod}4)\\ -1& \text{ if }p\equiv 3(\mathrm{mod}4).\end{array}$

• 平方剰余の法則の第2補足

  $\left(\frac{2}{p}\right)=(-1{)}^{\frac{p^2-1}{8}}=\{\begin{array}{cc}1& \text{ if }p\equiv 1\text{ or }7(\mathrm{mod}8)\\ -1& \text{ if }p\equiv 3\text{ or }5(\mathrm{mod}8).\end{array}$

• a が小さい場合のルジャンドル記号 $\left(\frac{a}{p}\right)$ の特別式
  • p ≠ 3である奇素数

    $\left(\frac{3}{p}\right)=(-1{)}^{\lfloor \frac{p+1}{6}\rfloor }=\{\begin{array}{cc}1& \text{ if }p\equiv 1\text{ or }11(\mathrm{mod}12)\\ -1& \text{ if }p\equiv 5\text{ or }7(\mathrm{mod}12).\end{array}$

  • p ≠ 5である奇素数

    $\left(\frac{5}{p}\right)=(-1{)}^{\lfloor \frac{2p+2}{5}\rfloor }=\{\begin{array}{cc}1& \text{ if }p\equiv 1\text{ or }4(\mathrm{mod}5)\\ -1& \text{ if }p\equiv 2\text{ or }3(\mathrm{mod}5).\end{array}$

• フィボナッチ数 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, … は漸化式テンプレート:Nowrap テンプレート:Nowrap により定義される。p が素数の場合

  $F_{p-\left(\frac{p}{5}\right)}\equiv 0(\mathrm{mod}p),F_p\equiv \left(\frac{p}{5}\right)(\mathrm{mod}p).$

例えば

$\begin{array}{cccccc}\left(\frac{2}{5}\right)& =-1,& F_3& =2,& F_2& =1,\\ \left(\frac{3}{5}\right)& =-1,& F_4& =3,& F_3& =2,\\ \left(\frac{5}{5}\right)& =0,& F_5& =5,& & \\ \left(\frac{7}{5}\right)& =-1,& F_8& =21,& F_7& =13,\\ \left(\frac{11}{5}\right)& =1,& F_{10}& =55,& F_{11}& =89.\end{array}$

• この結果は、素数判定で使用されるリュカ数列の理論に基づいている。en:Wall–Sun–Sun prime参照。

ルジャンドル記号と平方剰余

p と q を別々の奇素数とする。ルジャンドル記号を使用すると、平方剰余の法則を次のように簡潔に表すことができる。

$\left(\frac{q}{p}\right)\left(\frac{p}{q}\right)=(-1{)}^{\frac{p-1}{2}\cdot \frac{q-1}{2}}.$

多くの平方剰余の証明(en:proofs of quadratic reciprocity)はルジャンドルの式に基づく。

$\left(\frac{a}{p}\right)\equiv a^{\frac{p-1}{2}}(\mathrm{mod}p).$

さらに、平方剰余の法則の様々な証明を作るために、ルジャンドル記号の代わりとなる表現がいくつか考案された。

• ガウスはen:quadratic Gauss sumを導入し、自身の4番目および6番目の平方剰余の証明に下式を用いた。

$\sum _{k=0}^{p-1}{\zeta }^{a{k}^2}=\left(\frac{a}{p}\right)\sum _{k=0}^{p-1}{\zeta }^{k^2},\zeta =e^{\frac{2\pi i}{p}}$

• クロネッカ－の証明は初めに下式を立て、p と q の役割を反対にすることで(テンプレート:Sfrac) と (テンプレート:Sfrac) の関係を得た。

$\left(\frac{p}{q}\right)=\mathrm{sgn}\left(\prod _{i=1}^{\frac{q-1}{2}}\prod _{k=1}^{\frac{p-1}{2}}(\frac{k}{p}-\frac{i}{q})\right).$

• アイゼンシュタインの証明は次を示すことから始まる。

$\left(\frac{q}{p}\right)=\prod _{n=1}^{\frac{p-1}{2}}\frac{\sin \left(\frac{2\pi qn}{p}\right)}{\sin \left(\frac{2\pi n}{p}\right)}.$

正弦関数ではなく特定の楕円関数を使用することで、エイゼンシュタインは3次および4次の相互作用も証明することができた。

関連する関数

• ヤコビ記号 (テンプレート:Sfrac) はルジャンドル記号の一般化であり、合成数で2番目（下）の引数nの場合も可能であるが、nは奇数かつ正でなければならない。この一般化は途中で因数分解をせずにすべてのルジャンドル記号を計算する効率的な方法を提供する。
• さらに拡大したものはクロネッカー記号(en:Kronecker symbol)であり、下の引数は任意の整数である。
• 冪剰余記号(en:power residue symbol) (テンプレート:Sfrac)テンプレート:Sub はルジャンドル記号をより高い冪 n に一般化する。ルジャンドル記号はn = 2の場合の冪剰余記号を表す。

計算例

平方剰余の法則を含む上記の性質をルジャンドル記号を評価するために使用できる。例えば

$\begin{array}{cc}\left(\frac{12345}{331}\right)& =\left(\frac{3}{331}\right)\left(\frac{5}{331}\right)\left(\frac{823}{331}\right)\\ & =\left(\frac{3}{331}\right)\left(\frac{5}{331}\right)\left(\frac{161}{331}\right)\\ & =\left(\frac{3}{331}\right)\left(\frac{5}{331}\right)\left(\frac{7}{331}\right)\left(\frac{23}{331}\right)\\ & =(-1)\left(\frac{331}{3}\right)\left(\frac{331}{5}\right)(-1)\left(\frac{331}{7}\right)(-1)\left(\frac{331}{23}\right)\\ & =-\left(\frac{1}{3}\right)\left(\frac{1}{5}\right)\left(\frac{2}{7}\right)\left(\frac{9}{23}\right)\\ & =-\left(\frac{1}{3}\right)\left(\frac{1}{5}\right)\left(\frac{2}{7}\right)\left(\frac{3^2}{23}\right)\\ & =-(1)(1)(1)(1)\\ & =-1.\end{array}$

またはより効率的な計算では

$\left(\frac{12345}{331}\right)=\left(\frac{98}{331}\right)=\left(\frac{2\cdot 7^2}{331}\right)=\left(\frac{2}{331}\right)=(-1{)}^{\frac{331^2-1}{8}}=-1.$

ヤコビ記号の記事(en:Jacobi symbol#Calculations using the Legendre symbol)にはルジャンドル記号の操作の例がさらにある。

参考文献

• テンプレート:Citation
• テンプレート:Citation
• テンプレート:Citation
• テンプレート:Citation
• テンプレート:Citation
• テンプレート:Citation
• テンプレート:Citation

外部リンク

• Jacobi symbol calculator
• テンプレート:高校数学の美しい物語