ルジャンドル記号の性質
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/06/16 13:12 UTC 版)
「ルジャンドル記号」の記事における「ルジャンドル記号の性質」の解説
ルジャンドル記号には平方剰余の法則とともに効率的に計算するために使うことのできる便利な性質がいくつかある。 p ≡ 3 ( mod 4 ) {\displaystyle p\equiv 3({\text{mod }}4)} の場合、 p + 1 4 + p + 1 4 = ( p − 1 ) + 2 2 {\displaystyle {\frac {p+1}{4}}+{\frac {p+1}{4}}={\frac {(p-1)+2}{2}}} という事実は a = x ( p + 1 ) / 4 {\displaystyle a=x^{(p+1)/4}} が平方剰余 x {\displaystyle x} の平方根であることを提供する。 a ≡ b (mod p)の場合、ルジャンドル記号は1番目の（上の）引数において周期的である。 ( a p ) = ( b p ) . {\displaystyle \left({\frac {a}{p}}\right)=\left({\frac {b}{p}}\right).} ルジャンドル記号は、上の引数の完全乗法的関数(en:completely multiplicative function)である。 ( a b p ) = ( a p ) ( b p ) . {\displaystyle \left({\frac {ab}{p}}\right)=\left({\frac {a}{p}}\right)\left({\frac {b}{p}}\right).} 特に、pを法とし共に平方剰余である、またはともに平方非剰余である2つの数の積は剰余であるが、剰余と非剰余の積は非剰余である。特別なケースは平方数のルジャンドル記号である。 ( x 2 p ) = { 1 if p ∤ x 0 if p ∣ x . {\displaystyle \left({\frac {x^{2}}{p}}\right)={\begin{cases}1&{\mbox{if }}p\nmid x\\0&{\mbox{if }}p\mid x.\end{cases}}} a の関数としてみた時、ルジャンドル記号 ( a p ) {\displaystyle \left({\frac {a}{p}}\right)} はpを法とする一意の2次ディリクレ指標となる。 平方剰余の法則の第1補足 ( − 1 p ) = ( − 1 ) p − 1 2 = { 1 if p ≡ 1 ( mod 4 ) − 1 if p ≡ 3 ( mod 4 ) . {\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補足 ( 2 p ) = ( − 1 ) p 2 − 1 8 = { 1 if p ≡ 1 or 7 ( mod 8 ) − 1 if p ≡ 3 or 5 ( mod 8 ) . {\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 が小さい場合のルジャンドル記号 ( a p ) {\displaystyle \left({\frac {a}{p}}\right)} の特別式p ≠ 3である奇素数 ( 3 p ) = ( − 1 ) ⌊ p + 1 6 ⌋ = { 1 if p ≡ 1 or 11 ( mod 12 ) − 1 if p ≡ 5 or 7 ( mod 12 ) . {\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である奇素数 ( 5 p ) = ( − 1 ) ⌊ 2 p + 2 5 ⌋ = { 1 if p ≡ 1 or 4 ( mod 5 ) − 1 if p ≡ 2 or 3 ( mod 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, … は漸化式F1 = F2 = 1, Fn+1 = Fn + Fn−1. により定義される。p が素数の場合 F p − ( p 5 ) ≡ 0 ( mod p ) , F p ≡ ( p 5 ) ( mod p ) . {\displaystyle F_{p-\left({\frac {p}{5}}\right)}\equiv 0{\pmod {p}},\qquad F_{p}\equiv \left({\frac {p}{5}}\right){\pmod {p}}.} 例えば ( 2 5 ) = − 1 , F 3 = 2 , F 2 = 1 , ( 3 5 ) = − 1 , F 4 = 3 , F 3 = 2 , ( 5 5 ) = 0 , F 5 = 5 , ( 7 5 ) = − 1 , F 8 = 21 , F 7 = 13 , ( 11 5 ) = 1 , F 10 = 55 , F 11 = 89. {\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}}} この結果は、素数判定で使用されるリュカ数列の理論に基づいている。en:Wall–Sun–Sun prime参照。
※この「ルジャンドル記号の性質」の解説は、「ルジャンドル記号」の解説の一部です。
「ルジャンドル記号の性質」を含む「ルジャンドル記号」の記事については、「ルジャンドル記号」の概要を参照ください。
- ルジャンドル記号の性質のページへのリンク
