Символ Лежандра

Символ Лежандра — функция, используемая в теории чисел. Введён французским математиком А. М. Лежандром. Символ Лежандра является частным случаем символа Якоби, который, в свою очередь, является частным случаем символа Кронекера — Якоби, который иногда называют символом Лежандра — Якоби — Кронекера.

Определение

Пусть a — целое число, и p — простое число, отличное от 2. Символ Лежандра ( a p ) {displaystyle extstyle left({frac {a}{p}} ight)} определяется следующим образом:

• ( a p ) = 0 {displaystyle extstyle left({frac {a}{p}} ight)=0} , если a делится на p;
• ( a p ) = 1 {displaystyle extstyle left({frac {a}{p}} ight)=1} , если a является квадратичным вычетом по модулю p (то есть существует такое целое x, что x 2 ≡ a ( mod p ) {displaystyle x^{2}equiv a{pmod {p}}} ), но при этом a не делится на p;
• ( a p ) = − 1 {displaystyle extstyle left({frac {a}{p}} ight)=-1} , если a является квадратичным невычетом по модулю p.

Свойства

• Мультипликативность: ( a b p ) = ( a p ) ( b p ) {displaystyle left({frac {ab}{p}} ight)=left({frac {a}{p}} ight)left({frac {b}{p}} ight)} . Очевидными свойствами мультипликативности являются также следующие:
  • если a {displaystyle a} не делится на p {displaystyle p} , то ( a 2 p ) = 1 ; {displaystyle left({frac {a^{2}}{p}} ight)=1;}
  • если a = p 1 α 1 ⋅ p 2 α 2 ⋅ … ⋅ p k α k {displaystyle a=p_{1}^{alpha _{1}}cdot p_{2}^{alpha _{2}}cdot ldots cdot p_{k}^{alpha _{k}}} — каноническое разложение a {displaystyle a} на простые множители, то ( a p ) = ( p 1 p ) α 1 ( mod 2 ) ⋅ ( p 2 p ) α 2 ( mod 2 ) ⋅ … ⋅ ( p k p ) α k ( mod 2 ) . {displaystyle left({frac {a}{p}} ight)=left({frac {p_{1}}{p}} ight)^{alpha _{1}{pmod {2}}}cdot left({frac {p_{2}}{p}} ight)^{alpha _{2}{pmod {2}}}cdot ldots cdot left({frac {p_{k}}{p}} ight)^{alpha _{k}{pmod {2}}}.}
• Если a ≡ b ( mod p ) {displaystyle aequiv b{pmod {p}}} , то ( a p ) = ( b p ) . {displaystyle left({frac {a}{p}} ight)=left({frac {b}{p}} ight).}
• ( 1 p ) = 1. {displaystyle left({frac {1}{p}} ight)=1.}
• Лемма Гаусса о квадратичных вычетах.
• Критерий Эйлера:

( a p ) ≡ a ( p − 1 ) / 2 ( mod p ) . {displaystyle left({frac {a}{p}} ight)equiv a^{(p-1)/2}{pmod {p}}.}

• Если p ≠ 2 {displaystyle p eq 2} , то:

( − 1 p ) = ( − 1 ) ( p − 1 ) / 2 {displaystyle left({frac {-1}{p}} ight)=(-1)^{(p-1)/2}} (частный случай критерия Эйлера); ( 2 p ) = ( − 1 ) ( p 2 − 1 ) / 8 . {displaystyle left({frac {2}{p}} ight)=(-1)^{(p^{2}-1)/8}.} Доказательство

Если x < p 2 {displaystyle x<{frac {p}{2}}} и x {displaystyle x} нечётно, то p − x > p 2 {displaystyle p-x>{frac {p}{2}}} , причём p − x {displaystyle p-x} чётно, и наоборот. Поэтому

1 ⋅ 2 ⋅ 3 ⋅ 4 ⋅ … ⋅ p − 1 2 = {displaystyle 1cdot 2cdot 3cdot 4cdot ldots cdot {frac {p-1}{2}}=}

= ( − ( − 1 ) ) ⋅ 2 ⋅ ( − ( − 3 ) ) ⋅ 4 ⋅ … ⋅ ( ± ( ± p − 1 2 ) ) ≡ {displaystyle =(-(-1))cdot 2cdot (-(-3))cdot 4cdot ldots cdot left({pm left({pm {frac {p-1}{2}}} ight)} ight)equiv }

≡ ( − ( p − 1 ) ) ⋅ 2 ⋅ ( − ( p − 3 ) ) ⋅ 4 ⋅ … ⋅ ( ± ( ± p − 1 2 ) ) ( mod p )   , {displaystyle equiv (-{color {blue}{(p-1)}})cdot {color {red}{2}}cdot (-{color {blue}{(p-3)}})cdot {color {red}{4}}cdot ldots cdot left({pm left({pm {frac {p-1}{2}}} ight)} ight){pmod {p}} ,}

где в последнем произведении числа под знаками чётны, причём встречаются все чётные числа. Таким образом, обозначая s = p − 1 2 {displaystyle s={frac {p-1}{2}}} , имеем

s ! = 1 ⋅ 2 ⋅ 3 ⋅ 4 ⋅ … ⋅ p − 1 2 ≡ {displaystyle s!=1cdot 2cdot 3cdot 4cdot ldots cdot {frac {p-1}{2}}equiv }

≡ ( − 1 ) ⌊ ( s + 1 ) / 2 ⌋ ⋅ 2 ⋅ 4 ⋅ … ⋅ ( p − 3 ) ⋅ ( p − 1 ) = ( − 1 ) ⌊ ( s + 1 ) / 2 ⌋ ⋅ 2 s ( s ! ) ( mod p ) {displaystyle equiv (-1)^{lfloor {(s+1)/2} floor }cdot {color {red}{2}}cdot {color {red}{4}}cdot ldots cdot {color {blue}{(p-3)}}cdot {color {blue}{(p-1)}}=(-1)^{lfloor {(s+1)/2} floor }cdot 2^{s}(s!){pmod {p}}}

Поэтому 2 s ≡ ( − 1 ) ⌊ ( s + 1 ) / 2 ⌋ = ( − 1 ) s ( s + 1 ) 2 = ( − 1 ) p 2 − 1 8 {displaystyle 2^{s}equiv (-1)^{lfloor {(s+1)/2} floor }=(-1)^{frac {s(s+1)}{2}}=(-1)^{frac {p^{2}-1}{8}}} , что, по критерию Эйлера, доказывает утверждение.

• Квадратичный закон взаимности: Пусть p и q — неравные нечетные простые числа, тогда ( q p ) = ( − 1 ) p − 1 2 ⋅ q − 1 2 ⋅ ( p q ) . {displaystyle left({frac {q}{p}} ight)=(-1)^{{frac {p-1}{2}}cdot {frac {q-1}{2}}}cdot left({frac {p}{q}} ight).}
• Если p ≡ q ( mod 4 ⋅ a ) {displaystyle pequiv q{pmod {4cdot a}}} , то

( a p ) = ( a q ) {displaystyle left({frac {a}{p}} ight)=left({frac {a}{q}} ight)} .

• При p ≠ 2 {displaystyle p eq 2} среди чисел 1 ⩽ a ⩽ p − 1 {displaystyle 1leqslant aleqslant p-1} ровно половина имеет символ Лежандра, равный 1, а другая половина — равный −1.