Лема Гауса

Для кожного ${\displaystyle 1\leq j\leq m}$ існує єдине ${\displaystyle 1\leq u_{j}\leq m,}$ таке що виконується ${\displaystyle xj\equiv e_{j}u_{j}{\pmod {p}},}$ де ${\displaystyle e_{j}=1.}$ Тоді ${\displaystyle e_{1}e_{2}...e_{m}=(-1)^{n}.}$

Якщо j і k є двома різними числами від 1 до m тоді ${\displaystyle j\not \equiv k{\pmod {p}}}$ і ${\displaystyle j\not \equiv -k{\pmod {p}}}$. Як наслідок враховуючи, що p не ділить x маємо:

${\displaystyle xj\not \equiv xk{\pmod {p}}}$ і ${\displaystyle xj\not \equiv -xk{\pmod {p}}.}$

Тобто різним значенням ${\displaystyle 1\leq j\leq m}$ відповідають різні значення ${\displaystyle 1\leq u_{j}\leq m,}$. Але тоді ${\displaystyle u_{1},u_{2},\ldots ,u_{m}=m!}$ Перемножуючи дві сторони рівностей ${\displaystyle xj\equiv e_{j}u_{j}{\pmod {p}},}$ для ${\displaystyle j=1,2,\ldots ,m}$ одержимо ${\displaystyle x^{m}m!\equiv (-1)^{n}m!{\pmod {p}},}$ і, враховуючи взаємну простоту p і m!, як наслідок ${\displaystyle x^{m}\equiv (-1)^{n}{\pmod {p}}.}$

Згідно з властивостями символу Лежандра ${\displaystyle x^{m}\equiv \left({\frac {x}{p}}\right){\pmod {p}}.}$ Звідси одержуємо ${\displaystyle \left({\frac {x}{p}}\right)\equiv (-1)^{n}{\pmod {p}}}$ і нарешті ${\displaystyle \left({\frac {x}{p}}\right)=(-1)^{n}}$