Матеріал з Вікіпедії — вільної енциклопедії.
В математиці , а точніше в теорії чисел , квадратичний закон взаємності — твердження, що стосується розв'язності квадратичних рівнянь у модульній арифметиці .
Елементарне твердження [ ред. | ред. код ] Нехай маємо два різних простих числа p і q . Тоді квадратичний закон взаємності стверджує, що:
Якщо хоча б одне з чисел p і q є рівним 1 за модулем 4, то рівняння відносно невідомого x :
x
2
≡
p
(
mod
q
)
{\displaystyle x^{2}\equiv p{\pmod {q}}}
має розв'язок тоді й лише тоді , коли має розв'язок відносно невідомого y таке рівняння:
y
2
≡
q
(
mod
p
)
{\displaystyle y^{2}\equiv q{\pmod {p}}}
Якщо p і q рівні 3 за модулем 4, то рівняння відносно невідомого x :
x
2
≡
p
(
mod
q
)
{\displaystyle x^{2}\equiv p{\pmod {q}}}
має розв'язок тоді й лише тоді, коли рівняння відносно невідомого y :
y
2
≡
q
(
mod
p
)
{\displaystyle y^{2}\equiv q{\pmod {p}}}
не має розв'язку. Твердження за допомогою символу Лежандра [ ред. | ред. код ] З використанням символу Лежандра , твердження закону можна записати так:
(
p
q
)
(
q
p
)
=
(
−
1
)
(
p
−
1
)
(
q
−
1
)
4
{\displaystyle \left({\frac {p}{q}}\right)\left({\frac {q}{p}}\right)=(-1)^{\frac {(p-1)(q-1)}{4}}}
Також існує два доповнення до закону:
(
−
1
p
)
=
(
−
1
)
p
−
1
2
{\displaystyle \left({\frac {-1}{p}}\right)=(-1)^{\frac {p-1}{2}}}
(
2
p
)
=
(
−
1
)
p
2
−
1
8
.
{\displaystyle \left({\frac {2}{p}}\right)=(-1)^{\frac {p^{2}-1}{8}}.}
Нехай p дорівнює 11, а q дорівнює 19, i тоді
(
11
19
)
=
−
(
19
11
)
=
−
(
8
11
)
{\displaystyle \left({\frac {11}{19}}\right)=-\left({\frac {19}{11}}\right)=-\left({\frac {8}{11}}\right)}
19
≡
8
(
11
)
{\displaystyle 19\equiv 8\ (11)}
−
(
8
11
)
=
−
(
−
3
11
)
=
−
(
11
3
)
=
−
(
2
3
)
{\displaystyle -\left({\frac {8}{11}}\right)=-\left({\frac {-3}{11}}\right)=-\left({\frac {11}{3}}\right)=-\left({\frac {2}{3}}\right)}
квадратичним лишком за модулем 3, маємо:
−
(
2
3
)
=
−
(
−
1
)
=
1
{\displaystyle -\left({\frac {2}{3}}\right)=-(-1)=1}
7
2
=
49
=
38
+
11
≡
11
(
mod
19
)
{\displaystyle 7^{2}=49=38+11\equiv 11{\pmod {19}}}
Покажемо, що 219 є квадратичним лишком за модулем 383. Із властивостей символу Лежандра маємо:
(
219
383
)
=
(
3
383
)
(
73
383
)
{\displaystyle \left({\frac {219}{383}}\right)=\left({\frac {3}{383}}\right)\left({\frac {73}{383}}\right)}
Використання квадратичного закону взаємності дає рівність:
(
219
383
)
=
−
(
383
3
)
(
383
73
)
{\displaystyle \left({\frac {219}{383}}\right)=-\left({\frac {383}{3}}\right)\left({\frac {383}{73}}\right)}
Подальше використання закону та властивостей символу Лежандра приводить до необхідного результату:
(
219
383
)
=
−
(
−
1
3
)
(
18
73
)
=
−
(
−
1
3
)
(
2
73
)
(
9
73
)
=
(
2
73
)
=
(
−
1
)
(
73
2
−
1
8
)
=
(
−
1
)
666
=
1
{\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}
