ルジャンドル記号

数論において、ルジャンドル記号は、奇数素数pを法とする二次関数で、値が 1、-1、0 である乗法関数である。 pを法とする (ゼロでない)二次剰余におけるその値は1 であり、非二次剰余 (非剰余) におけるその値は -1 である。ゼロにおけるその値は 0 である。

ルジャンドル記号は、1798年にアドリアン・マリー・ルジャンドルが二次の相互法則を証明しようと試みる過程で導入した^{[1] 。この記号の一般化には、}ヤコビ記号や高次のディリクレ指標などがある。ルジャンドル記号の表記上の利便性は、ヒルベルト記号やアルティン記号など、代数的整数論で使用される他のいくつかの「記号」の導入に影響を与えた。

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

${\displaystyle \left({\frac {a}{p}}\right)={\begin{cases}1&{\text{if }}a{\text{ is modulo }}p{\text{ and }}a\not \equiv 0{\pmod {p}},\\-1&{\text{if }}a{\text{ is 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{ および }}\quad \left({\frac {a}{p}}\right)\in \{-1,0,1\}.}$

以前に発見され、ルジャンドルも知っていたオイラーの基準によれば、これら 2 つの定義は同等である。 ^[2]したがって、ルジャンドルの貢献は、 p を法 とするaの二次剰余を記録する便利な表記法を導入したことである。比較のために、ガウスは、 aがpを法とする剰余か非剰余かに応じて、 a R p、a N pという表記法を使用した。印刷上の便宜上、ルジャンドル記号は ( a  |  p ) または ( a / p ) と表記されることもある。p を固定した場合、数列は周期p で周期的となり、ルジャンドル数列と呼ばれることもある。次の表の各行は、説明どおりに周期性を示している。 ${\displaystyle \left({\tfrac {0}{p}}\right),\left({\tfrac {1}{p}}\right),\left({\tfrac {2}{p}}\right),\ldots }$

以下は、 p  ≤ 127、a  ≤ 30、p が奇数素数であるルジャンドル記号の値の表です。 ${\displaystyle \left({\frac {a}{p}}\right)}$

ルジャンドル記号には、二次の相互法則と組み合わせることで効率的に計算できる 便利な特性が数多くあります。

• 生成元 が与えられている場合、が偶数である場合に限り、 は平方剰余です。これは、 の要素の半分が平方剰余であることを示しています。${\displaystyle g\in \mathbb {F} _{p}^{*}}$${\displaystyle x=g^{r}}$${\displaystyle x}$${\displaystyle r}$${\displaystyle \mathbb {F} _{p}^{*}}$
• もし、 ${\displaystyle p\equiv 3{\text{mod}}4}$

  ${\displaystyle {\frac {p+1}{4}}+{\frac {p+1}{4}}={\frac {p+1}{2}}={\frac {(p-1)+2}{2}}={\frac {p-1}{2}}+1}$は平方剰余の平方根である ことがわかります。${\displaystyle a=x^{(p+1)/4}}$${\displaystyle x}$

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

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

• ルジャンドル記号は、その最上位引数の完全な乗法関数です。

  ${\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の関数として見ると、ルジャンドル記号はp を法とする唯一の二次（または 2 次）ディリクレ指標です。${\displaystyle \left({\frac {a}{p}}\right)}$
• 二次相互法則の最初の補足:

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

• この結果は素数判定に使われるルーカス数列の理論から来ている。^[3]ウォール・サン・サン素数を参照。

pとq が異なる奇数の素数であるとします。ルジャンドル記号を使用すると、二次の相互法則は簡潔に次のように表すことができます。

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

二次相互性の証明の多くはオイラーの基準に基づいている。

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

さらに、二次の相互法則のさまざまな証明を生み出すために、ルジャンドル記号のいくつかの代替表現が考案されました。

• ガウスは二次ガウス和を導入し、次の公式を用いた。

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

二次の相互法則の4番目の^[4]と6番目の^[5]の証明において。

• クロネッカーの証明^[6] はまず、

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

pとqの役割を逆にすると、 ( ⁠p/q⁠ ) と ( ⁠q/p⁠）。

• アイゼンシュタインの証明の一つ^[7]は、

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

• ヤコビ記号（⁠1つの/ん⁠ ) は、ルジャンドル記号の一般化であり、合成の 2 番目の (下) 引数nを許可しますが、n は依然として奇数かつ正である必要があります。この一般化により、途中で因数分解を実行せずにすべてのルジャンドル記号を効率的に計算できるようになります。
• さらなる拡張はクロネッカー記号であり、その下の引数は任意の整数になることができます。
• べき乗剰余記号（⁠1つの/ん⁠ ) _{n は、}ルジャンドル記号をn のより高いべき乗に一般化します。ルジャンドル記号は、n  = 2のべき乗剰余記号を表します。

二次の相互法則を含む上記の性質は、任意のルジャンドル記号を評価するために使用できます。例:

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

記事「Jacobi 記号」には、Legendre 記号の操作例がさらに記載されています。

効率的な因数分解アルゴリズムは知られていないが、効率的なべき乗剰余アルゴリズムは知られているため、一般的にはルジャンドルの元の定義を使用する方が効率的である。例えば、

${\displaystyle {\begin{aligned}\left({\frac {98}{331}}\right)&\equiv 98^{\frac {331-1}{2}}&{\pmod {331}}\\&\equiv 98^{165}&{\pmod {331}}\\&\equiv 98\cdot (98^{2})^{82}&{\pmod {331}}\\&\equiv 98\cdot 5^{82}&{\pmod {331}}\\&\equiv 98\cdot 25^{41}&{\pmod {331}}\\&\equiv 133\cdot 25^{40}&{\pmod {331}}\\&\equiv 133\cdot 294^{20}&{\pmod {331}}\\&\equiv 133\cdot 45^{10}&{\pmod {331}}\\&\equiv 133\cdot 39^{5}&{\pmod {331}}\\&\equiv 222\cdot 39^{4}&{\pmod {331}}\\&\equiv 222\cdot 197^{2}&{\pmod {331}}\\&\equiv 222\cdot 82&{\pmod {331}}\\&\equiv -1&{\pmod {331}}\end{aligned}}}$

331 を法とする繰り返しの二乗を使用し、各演算の後に法を使用してすべての値を減らして、大きな整数での計算を回避します。

• Gauss, Carl Friedrich (1965)、Untersuchungen über höhere Arithmetik (Disquisitiones Arithmeticae & その他の数論に関する論文)、Maser, H. 訳 (第 2 版)、ニューヨーク: チェルシー、ISBN 0-8284-0191-8
• ガウス、カール・フリードリヒ（1986）、Disquisitiones Arithmeticae、クラーク、アーサー・A（第2版、訂正版）訳、ニューヨーク：シュプリンガー、ISBN 0-387-96254-9
• バッハ、エリック、シャリット、ジェフリー（1996）、アルゴリズム数論、第1巻：効率的なアルゴリズム）、ケンブリッジ：MITプレス、ISBN 0-262-02405-5
• ハーディ、GH、ライト、EM（1980）、数論入門（第5版）、オックスフォード：オックスフォード大学出版局、ISBN 978-0-19-853171-5
• アイルランド、ケネス、ローゼン、マイケル（1990）、現代数論への古典的入門（第2版）、ニューヨーク：シュプリンガー、ISBN 0-387-97329-X
• Lemmermeyer、Franz (2000)、相反性の法則: オイラーからエイゼンシュタインまで、ベルリン: Springer、ISBN 3-540-66957-4
• リベンボイム、パウロ（1996）、素数記録の新書、ニューヨーク：シュプリンガー、ISBN 0-387-94457-5

• ヤコビ記号計算機