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

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

$x^2\equiv a(\mathrm{mod}m).$

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

Властивості

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

  $a^{(p-1)/2}\equiv 1(\mathrm{mod}p)$

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

$a^{(p-1)/2}\equiv -1(\mathrm{mod}p).$

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

Див. також

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

Джерела

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