Квадратичний закон взаємності

В математиці, а точніше в теорії чисел, квадратичний закон взаємності — твердження, що стосується розв'язності квадратичних рівнянь у модульній арифметиці .

Твердження

Елементарне твердження

Нехай маємо два різних простих числа p і q. Тоді квадратичний закон взаємності стверджує, що:

• Якщо хоча б одне з чисел p і q є рівним 1 за модулем 4, то рівняння відносно невідомого x:

$x^2\equiv p(\mathrm{mod}q)$

має розв'язок тоді й лише тоді, коли має розв'язок відносно невідомого y таке рівняння:

$y^2\equiv q(\mathrm{mod}p)$

• Якщо p і q рівні 3 за модулем 4, то рівняння відносно невідомого x:

$x^2\equiv p(\mathrm{mod}q)$

має розв'язок тоді й лише тоді, коли рівняння відносно невідомого y:

$y^2\equiv q(\mathrm{mod}p)$

не має розв'язку.

Твердження за допомогою символу Лежандра

З використанням символу Лежандра, твердження закону можна записати так:

$\left(\frac{p}{q}\right)\left(\frac{q}{p}\right)=(-1{)}^{\frac{(p-1)(q-1)}{4}}$

Також існує два доповнення до закону:

$\left(\frac{-1}{p}\right)=(-1{)}^{\frac{p-1}{2}}$     і     $\left(\frac{2}{p}\right)=(-1{)}^{\frac{p^2-1}{8}}.$

Приклади

Для простих чисел

Нехай p дорівнює 11, а q дорівнює 19, i тоді $\left(\frac{11}{19}\right)=-\left(\frac{19}{11}\right)=-\left(\frac{8}{11}\right)$ (оскільки $19\equiv 8(11)$). Далі $-\left(\frac{8}{11}\right)=-\left(\frac{-3}{11}\right)=-\left(\frac{11}{3}\right)=-\left(\frac{2}{3}\right)$, і, оскільки 2 не є квадратичним лишком за модулем 3, маємо: $-\left(\frac{2}{3}\right)=-(-1)=1$. Тобто одержуємо, що 11 є квадратичним лишком за модулем 19. Це твердження легко можна перевірити: $7^2=49=38+11\equiv 11(\mathrm{mod}19)$

Загальний випадок

Покажемо, що 219 є квадратичним лишком за модулем 383. Із властивостей символу Лежандра маємо:

$\left(\frac{219}{383}\right)=\left(\frac{3}{383}\right)\left(\frac{73}{383}\right)$

Використання квадратичного закону взаємності дає рівність:

$\left(\frac{219}{383}\right)=-\left(\frac{383}{3}\right)\left(\frac{383}{73}\right)$

Подальше використання закону та властивостей символу Лежандра приводить до необхідного результату:

$\left(\frac{219}{383}\right)=-\left(\frac{-1}{3}\right)\left(\frac{18}{73}\right)=-\left(\frac{-1}{3}\right)\left(\frac{2}{73}\right)\left(\frac{9}{73}\right)=\left(\frac{2}{73}\right)=(-1{)}^{\left(\frac{73^2-1}{8}\right)}=(-1{)}^{666}=1$

Див. також

• Модульна арифметика
• Символ Лежандра