Пункт 22. Порівняння другого степеня. Символ Лежандра.
Розглянемо найпростіші двочленні порівняння другого степеня виду
x2ºa(mod p),
де а і р взаємно прості, а р - непарне просте число. Зверніть увагу, що умова взаємної простоти (а, р)=1 виключає з нашого розгляду випадок а =0.
Нас буде цікавити питання, при яких а найпростіше двочленне порівняння другого степеня має розв’язок, а при яких – не має. Зрозуміло, що порівняння x2ºa(mod 2) має розв’язок при будь-яких а, тому що замість а достатньо підставити тільки 0 або 1, а числа 0 і 1 є квадратами. Саме тому випадок р=2 не представляє особливого інтересу і виводиться з подальшого розгляду.
Що стосується порівняння x2º0(mod p), то воно завжди має розв’язок х=0. Отже, інтерес представляє лише ситуація з непарним простим модулем і а¹0.
Визначення. Якщо порівняння x2ºa(mod p) має розв’язок, то число а називається квадратним лишком за модулем р. В іншому випадку, число а називається квадратним нелишком за модулем р.
Отже, якщо а – квадрат деякого числа за модулем р, то а -“квадратний лишок”, якщо жодне число в квадраті не порівнянльне з а за модулем р, то а - “квадратний нелишок”.
Приклад. Число 2 є квадратом за модулем 7, бо
42º16º2(mod7). Виходить, 2 - квадратний лишок. (Порівняння x2º2(mod7) має ще й інший розв’язок: 32º9º2(mod7).) Навпаки, число 3 є квадратним нелишком за модулем 7, тому що порівняння x2º3(mod7) розв’язків не має, у чому неважко переконатися послідовним перебором повної системи лишків: x = 0,1,2,3,4,5,6.
Спостереження: Якщо а - квадратний лишок за модулем р, то порівняння x2ºa(mod p) має лише два розв’язки. Дійсно, якщо а - квадратний лишок за модулем р, то в порівняння x2ºa(mod p) є хоча б один розв’язок xºx1(mod p). Тоді x2=-x1 – теж розв’язок, адже (-x1)2=x12. Ці два розв’язки непорівняльні за модулем р>2, бо з x1º-x1(mod p) випливає 2x1º0(mod p), тобто (оскільки р¹ 2) x1º0(mod p), що неможливо, тому що а¹ 0.
Оскільки порівняння x2ºa(mod p) є порівнянням другого степеня за простим модулем, то більше двох розв’язків воно мати не може (див. пункт 20, лема 2).
Спостереження: Зведена (тобто без нуля) система лишків
за модулем р складається з (p-1)/2 квадратних лишків, порівняльних з числами 12,22,…,((p-1)/2)2,і (p-1)/2 квадратних нелишків, тобто лишків і нелишків порівну.
Дійсно, квадратні лишки порівняльні з квадратами чисел
тобто з числами 12,22,…,((p-1)/2)2, при цьому всі ці квадрати різні за модулем р, тому що з k2ºl2(mod p), де 0<k<l£ (p-1)/2, випливає, що нетривіальне порівняння x2ºk2(mod p) має аж чотири розв’язки: l, –l, k, –k, що неможливо (див. пункт 20, лема 2).
