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

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