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

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

Определение


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

  • (ap)=0, если a делится на p;
  • (ap)=1, если a является квадратичным вычетом по модулю p (то есть существует такое целое x, что x2a(modp)) и a не делится на p;
  • (ap)=1, если a является квадратичным невычетом по модулю p.

Свойства



  • Мультипликативность: (abp)=(ap)(bp). В частности,
    • Eсли a не делится на p, то (a2p)=1.
    • Если a=p1α1p2α2pkαk — каноническое разложение a на простые сомножители, то
      (ap)=(p1p)α1(mod2)(p2p)α2(mod2)(pkp)αk(mod2).

  • Если ab(modp), то
    (ap)=(bp).

  • (1p)=1.
  • (1p)=(1)(p1)/2.
  • (2p)=(1)(p21)/8.
  • Квадратичный закон взаимности: Пусть p и q — неравные нечетные простые числа, тогда
    (qp)=(1)p12q12(pq).


 Если pq(mod4a) тогда
(ap)=(aq)
.

  • Среди чисел 1ap1 ровно половина имеет символ Лежандра, равный +1, а другая половина — равный −1.
  • формула Эйлера



(ap)a(p1)/2(modp).