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

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

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

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

Властивості

• Критерій Ейлера: Нехай ${\displaystyle p>2}$ просте число. Число а, взаємно просте з ${\displaystyle p}$, є квадратичним лишком за модулем ${\displaystyle p}$ тоді і тільки тоді, коли

  ${\displaystyle a^{(p-1)/2}\equiv 1{\pmod {p}}\,}$

і є квадратичним нелишком за модулем p тоді і тільки тоді, коли

${\displaystyle a^{(p-1)/2}\equiv -1{\pmod {p}}.\,}$

• Квадратичний закон взаємності
• Квадратичні лишки, взаємно прості з модулем, утворюють мультиплікативну підгрупу кільця лишків, зокрема:
  • лишок ${\displaystyle \times }$ лишок = лишок;
  • нелишок ${\displaystyle \times }$ лишок = нелишок.

Див. також

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

Джерела

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