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

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

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

${\displaystyle x^{2}\equiv p{\pmod {q}}}$

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

${\displaystyle y^{2}\equiv q{\pmod {p}}}$

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

${\displaystyle x^{2}\equiv p{\pmod {q}}}$

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

${\displaystyle y^{2}\equiv q{\pmod {p}}}$

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle \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}$