ルジャンドル記号

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

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

いくつかの $a$ と $p$ のときのルジャンドル記号 ( $.mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num,.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0 0.1em}.mw-parser-output .sfrac .den{border-top:1px solid}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}a/p$ )
	$a =0$	1	2	3	4	5	6	7	8	9	10
$p =3$	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
$p$ を法として合同ならルジャンドル記号の値は等しくなるため、 $0 \leq a < p$ の場合の値のみ示す。表では $a$ が平方剰余となる（ルジャンドル記号の値が 0 または 1）部分を黄色で強調している。

定義

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

\left({\frac {a}{p}}\right)={\begin{cases}1&{\text{if }}a{\text{ is a quadratic residue modulo }}p{\text{ and }}a\not \equiv 0{\pmod {p}},\\-1&{\text{if }}a{\text{ is a non-quadratic residue modulo }}p,\\0&{\text{if }}a\equiv 0{\pmod {p}}.\end{cases}}

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

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

先に発見されルジャンドルにも知られていたオイラーの規準によると、これら2つの定義は同等である^[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}であることがある^[3]。次の表の各行は、説明したように周期性を示していることが分かる。

値の表

ルジャンドル記号 $\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	−1	−1	0	−1	−1	0	1	−1	−0	1	−1	0	1	−1	0	−1	−1	0	1	−1	0	1	−1	0	−1	−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{cases}1&{\mbox{if }}p\nmid x\\0&{\mbox{if }}p\mid x.\end{cases}}$
a の関数としてみた時、ルジャンドル記号 $\left({\frac {a}{p}}\right)$ はpを法とする一意の2次ディリクレ指標となる。
平方剰余の法則の第1補足
$\left({\frac {-1}{p}}\right)=(-1)^{\frac {p-1}{2}}={\begin{cases}1&{\mbox{ if }}p\equiv 1{\pmod {4}}\\-1&{\mbox{ if }}p\equiv 3{\pmod {4}}.\end{cases}}$
平方剰余の法則の第2補足
$\left({\frac {2}{p}}\right)=(-1)^{\tfrac {p^{2}-1}{8}}={\begin{cases}1&{\mbox{ if }}p\equiv 1{\mbox{ or }}7{\pmod {8}}\\-1&{\mbox{ if }}p\equiv 3{\mbox{ or }}5{\pmod {8}}.\end{cases}}$
a が小さい場合のルジャンドル記号 $\left({\frac {a}{p}}\right)$ $\left({\frac {a}{p}}\right)$ の特別式
- p ≠ 3である奇素数
  $\left({\frac {3}{p}}\right)=(-1)^{{\big \lfloor }{\frac {p+1}{6}}{\big \rfloor }}={\begin{cases}1&{\mbox{ if }}p\equiv 1{\mbox{ or }}11{\pmod {12}}\\-1&{\mbox{ if }}p\equiv 5{\mbox{ or }}7{\pmod {12}}.\end{cases}}$
- p ≠ 5である奇素数
  $\left({\frac {5}{p}}\right)=(-1)^{{\big \lfloor }{\frac {2p+2}{5}}{\big \rfloor }}={\begin{cases}1&{\mbox{ if }}p\equiv 1{\mbox{ or }}4{\pmod {5}}\\-1&{\mbox{ if }}p\equiv 2{\mbox{ or }}3{\pmod {5}}.\end{cases}}$
フィボナッチ数 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, … は漸化式F₁ = F₂ = 1, F_n+1 = F_n + F_n−1. により定義される。p が素数の場合
$F_{p-\left({\frac {p}{5}}\right)}\equiv 0{\pmod {p}},\qquad F_{p}\equiv \left({\frac {p}{5}}\right){\pmod {p}}.$

例えば

{\begin{aligned}\left({\tfrac {2}{5}}\right)&=-1,&F_{3}&=2,&F_{2}&=1,\\\left({\tfrac {3}{5}}\right)&=-1,&F_{4}&=3,&F_{3}&=2,\\\left({\tfrac {5}{5}}\right)&=0,&F_{5}&=5,&&\\\left({\tfrac {7}{5}}\right)&=-1,&F_{8}&=21,&F_{7}&=13,\\\left({\tfrac {11}{5}}\right)&=1,&F_{10}&=55,&F_{11}&=89.\end{aligned}}

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

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

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

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

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

\left({\frac {a}{p}}\right)\equiv a^{\tfrac {p-1}{2}}{\pmod {p}}.

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

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

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

クロネッカ－の証明は^[7]初めに下式を立て、p と q の役割を反対にすることで(p/q) と (q/p) の関係を得た。

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

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

\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次の相互作用も証明することができた。

計算例

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

{\begin{aligned}\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{aligned}}

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

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

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

出典

^ Legendre, A. M. (1798). Essai sur la théorie des nombres. Paris. p. 186
^ Hardy & Wright, Thm. 83.
^ Kim, Jeong-Heon; Song, Hong-Yeop (2001). “Trace Representation of Legendre Sequences”. Designs, Codes, and Cryptography 24: 343–348.
^ Ribenboim, p. 64; Lemmermeyer, ex. 2.25–2.28, pp. 73–74.
^ Gauss, "Summierung gewisser Reihen von besonderer Art" (1811), reprinted in Untersuchungen ... pp. 463–495
^ Gauss, "Neue Beweise und Erweiterungen des Fundamentalsatzes in der Lehre von den quadratischen Resten" (1818) reprinted in Untersuchungen ... pp. 501–505
^ Lemmermeyer, ex. p. 31, 1.34
^ Lemmermeyer, pp. 236 ff.

参考文献

Gauss, Carl Friedrich; Maser, H. (translator into German) (1965), Untersuchungen über höhere Arithmetik (Disquisitiones Arithmeticae & other papers on number theory) (Second edition), New York: Chelsea, ISBN 0-8284-0191-8
Gauss, Carl Friedrich; Clarke, Arthur A. (translator into English) (1986), Disquisitiones Arithmeticae (Second, corrected edition), New York: Springer, ISBN 0-387-96254-9
Bach, Eric; Shallit, Jeffrey (1996), Algorithmic Number Theory (Vol I: Efficient Algorithms), Cambridge: The MIT Press, ISBN 0-262-02405-5
Hardy, G. H.; Wright, E. M. (1980), An Introduction to the Theory of Numbers (Fifth edition), Oxford: Oxford University Press, ISBN 978-0-19-853171-5
Ireland, Kenneth; Rosen, Michael (1990), A Classical Introduction to Modern Number Theory (Second edition), New York: Springer, ISBN 0-387-97329-X
Lemmermeyer, Franz (2000), Reciprocity Laws: from Euler to Eisenstein, Berlin: Springer, ISBN 3-540-66957-4
Ribenboim, Paulo (1996), The New Book of Prime Number Records, New York: Springer, ISBN 0-387-94457-5

外部リンク

[1] Legendre, A. M. (1798). Essai sur la théorie des nombres. Paris. p. 186

[2] Hardy & Wright, Thm. 83.

[KimSong01-3] Kim, Jeong-Heon; Song, Hong-Yeop (2001). “Trace Representation of Legendre Sequences”. Designs, Codes, and Cryptography 24: 343–348.

[4] Ribenboim, p. 64; Lemmermeyer, ex. 2.25–2.28, pp. 73–74.

[5] Gauss, "Summierung gewisser Reihen von besonderer Art" (1811), reprinted in Untersuchungen ... pp. 463–495

[6] Gauss, "Neue Beweise und Erweiterungen des Fundamentalsatzes in der Lehre von den quadratischen Resten" (1818) reprinted in Untersuchungen ... pp. 501–505

[7] Lemmermeyer, ex. p. 31, 1.34

[8] Lemmermeyer, pp. 236 ff.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

定義

値の表

ルジャンドル記号の性質

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

関連する関数

計算例

出典

参考文献

外部リンク