Квадратичний лишок

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Квадратичний лишок по модулю mціле число \ a, для якого має розв'язок наступне порівняння

\ x^2 \equiv a \pmod{m}.

Якщо вказане порівняння не має розв'язку, то число a називається квадратичним нелишком по модулю m.

Властивості[ред.ред. код]

  • Критерій Ейлера: Нехай p>2 просте число. Число а, взаємно просте з p, є квадратичним лишком по модулю p тоді і тільки тоді, коли
    a^{(p-1)/2} \equiv 1\pmod{p} \,
і є квадратичним нелишком по модулю p тоді і тільки тоді, коли
a^{(p-1)/2} \equiv -1\pmod{p}.\,
  • Квадратичний закон взаємності
  • Квадратичні лишки, взаємно прості з модулем, утворюють мультиплікативну підгрупу кільця лишків, зокрема:
    • лишок \times лишок = лишок;
    • нелишок \times лишок = нелишок.

Див. також[ред.ред. код]

Джерела[ред.ред. код]