ルジャンドル記号

Summarize Timeline Fact Check

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

${\displaystyle \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}}}$

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

${\displaystyle \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]。次の表の各行は、説明したように周期性を示していることが分かる。

Summarize Fact Check

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

Summarize Timeline Top Qs Fact Check

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

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

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

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

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

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

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

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

  ${\displaystyle \left({\frac {x^{2}}{p}}\right)={\begin{cases}1&{\mbox{if }}p\nmid x\\0&{\mbox{if }}p\mid x.\end{cases}}}$

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

  ${\displaystyle \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補足

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

    ${\displaystyle \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である奇素数

    ${\displaystyle \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 が素数の場合

  ${\displaystyle F_{p-\left({\frac {p}{5}}\right)}\equiv 0{\pmod {p}},\qquad F_{p}\equiv \left({\frac {p}{5}}\right){\pmod {p}}.}$

例えば

${\displaystyle {\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参照。

Summarize Timeline Top Qs Fact Check

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

${\displaystyle \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)はルジャンドルの式に基づく。

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

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

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

${\displaystyle \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) の関係を得た。

${\displaystyle \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]は次を示すことから始まる。

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

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

Summarize Top Qs Fact Check

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

${\displaystyle {\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}}}$

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

${\displaystyle \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)にはルジャンドル記号の操作の例がさらにある。