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

Квадратичний лишок по модулю $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$ лишок = нелишок.

Див. також

• Символ Лежандра
• Критерій Ейлера
• Лема Гауса
• A096008 в OEIS — послідовність квадратичних залишків.
• Побудова Пелі

Джерела

• Богуш В. М., Мухачов В. А. Криптографічні застосування елементарної теорії чисел^{[недоступне посилання з червня 2019]} — К.: ДУІКТ, 2005. — 176 с., ISBN 966-2970-06-1