Пусть $m$ натуральное число. Произвольное целое число можно поделить на $m$ с остатком, который принимает значения $0,1,2,\ldots ,m-1$. Разобьём множество целых чисел на $m$ классов, каждый из которых содержит все целые числа, дающие один и тот же остаток при делении на $m$. Это будут так называемые классы вычетов по модулю числа $m$.

Выберем из каждого класса вычетов ровно по одному представителю, тогда полученное множество называется полной системой вычетов по модулю $m$. Если же из произвольной полной системы вычетов дополнительно выбрать только те числа, которые взаимно просты с $m$, то полученное множество будем называть приведённой системой вычетов по модулю $m$.

Пример 5. Вот некоторые полные системы вычетов по модулю $7$: $$\{0,1,2,3,4,5,6\},\quad\{1,2,3,4,5,6,7\},\quad\{-27,-19,-11,-3,5,13,21\}.$$ Соответствующие им приведённые системы вычетов по модулю $7$: $$\{1,2,3,4,5,6\},\quad\{1,2,3,4,5,6\},\quad\{-27,-19,-11,-3,5,13\}.$$ Дадим также некоторые полные системы вычетов по модулю $9$: $$\{0,1,2,3,4,5,6,7,8\},\quad\{-4,-3,-2,-1,0,1,2,3,4\},\quad\{100,200,300,400,500,600,700,800,900\}.$$ Соответствующие им приведённые системы вычетов по модулю $9$: $$\{1,2,4,5,7,8\},\quad\{-4,-2,-1,1,2,4\},\quad\{100,200,400,500,700,800\}.$$

Заметим, что если имеются две полные системы вычетов по модулю $m$, то каждый элемент одной из них сравним по модулю $m$ с каким-то одним и только одним элементом другой, просто потому, что каждая полная система вычетов по модулю $m$ содержит ровно по одному представителю из каждого класса вычетов по модулю $m$. То же самое свойство сохранится и если мы рассмотрим две произвольные приведённые системы вычетов по модулю $m$. В частности, поскольку числа $1,2,\ldots ,m$ образуют полную систему вычетов по модулю $m$, то соответствующая приведённая система вычетов будет выбираться из этих чисел и по определению функции Эйлера будет состоять из $\varphi(m)$ элементов. А следовательно и в любой приведённой системе вычетов по модулю $m$ будет содержаться $\varphi(m)$ чисел. Одновременно таково будет количество классов вычетов по модулю $m$, состоящих из взаимно простых с $m$ чисел.

Если числа $a$ и $b$ содержатся в одном и том же классе вычетов по модулю $m$, то говорят, что они сравнимы по модулю $m$. Обозначается это так: $$a\equiv b\pmod{m}.$$ Заметим, что $a\equiv b\pmod{m}\Leftrightarrow m|(b-a)$.

Из этого замечания, самого определения и из свойств делимости вытекают следующие очевидные свойства сравнений:

1. $a\equiv a\pmod{m}$.
2. Если $a\equiv b\pmod{m}$ и $b\equiv c\pmod{m}$, то $a\equiv c\pmod{m}$.
3. Если $a\equiv b\pmod{m}$ и $c\in\mathbb{Z}$, то $a\cdot c\equiv b\cdot c\pmod{m}$.
4. Если $a\cdot n\equiv b\cdot n\pmod{m}$ и $(m,n)=1$, то $a\equiv b\pmod{m}$.
5. Если $a\cdot n\equiv b\cdot n\pmod{m\cdot n}$, то $a\equiv b\pmod{m}$.
6. Если $a\equiv b\pmod{m}$ и $c\equiv d\pmod{m}$, то $a\pm c\equiv b\pm d\pmod{m}$ и $a\cdot c\equiv b\cdot d\pmod{m}$.

Прокомментируем лишь последнее свойство. Из третьего свойства получаем $a\cdot c\equiv b\cdot c\pmod{m}$ и $b\cdot c\equiv b\cdot d\pmod{m}$. Теперь по второму свойству находим $a\cdot c\equiv b\cdot d\pmod{m}$.

Предложение 3. Пусть $a$ пробегает полную систему вычетов по модулю $m$, а также $k,n\in\mathbb{Z}$ и $(m,n)=1$. Тогда числа вида $a\cdot n+k$ тоже пробегают полную систему вычетов по модулю $m$.

Доказательство. Достаточно повторить рассуждения последнего абзаца предыдущего доказательства мультипликативности функции Эйлера. Сделаем это. Необходимо показать, что все эти числа $a\cdot n+k$ лежат в разных классах вычетов по модулю $m$. Допустим, что два из них лежат в одном и том же классе, то есть $a_1\cdot n+k\equiv a_2\cdot n+k\pmod{m}$, где $a_1\not\equiv a_2\pmod{m}$. Но тогда из первого и шестого свойств сравнений следует, что $a_1\cdot n\equiv a_2\cdot n\pmod{m}$, и, так как $(m,n)=1$, то по четвёртому свойству сравнений $a_1\equiv a_2\pmod{m}$. Противоречие. Предложение 3 доказано.

Следствие 10. Пусть $a$ пробегает приведённую систему вычетов по модулю $m$, а также $n\in\mathbb{Z},\ (m,n)=1$. Тогда числа вида $a\cdot n$ тоже пробегают приведённую систему вычетов по модулю $m$.

Доказательство. По предложению 3, если $a$ пробегает полную систему вычетов по модулю $m$, то и $a\cdot n$ тоже. Очевидно, что взаимно просты с $m$ будут те и только те числа $a\cdot n$, для которых $a$ взаимно просто с $m$. Следствие 10 доказано.

Теорема Эйлера. Пусть $m$ натуральное число, $b\in\mathbb{Z},\ (b,m)=1$. Тогда $b{}^{\varphi(m)}\equiv 1\pmod{m}$.

Доказательство. Пусть $a$ пробегает приведённую систему вычетов по модулю $m$. Тогда по следствию 10 числа вида $a\cdot b$ тоже пробегают приведённую систему вычетов по модулю $m$. Каждый элемент первой совокупности сравним по модулю $m$ с каким-то одним и только одним элементом второй совокупности. Следовательно произведение элементов первой совокупности сравнимо по модулю $m$ с произведением элементов второй. Если занумеровать элементы первой совокупности $a_1,a_2,\ldots ,a_{\varphi(m)}$, то можно записать это так: $$\prod_{i=1}^{\varphi(m)}a_i\ \equiv\ \prod_{i=1}^{\varphi(m)}(a_i\cdot b)\ =\ b{}^{\varphi(m)}\prod_{i=1}^{\varphi(m)}a_i\pmod{m}.$$ Так как по определению все элементы приведённой системы вычетов взаимно просты с $m$, то по четвёртому свойству сравнений мы можем сократить левую и правую части сравнения на $\displaystyle\prod_{i=1}^{\varphi(m)}a_i$ и получим, что $b{}^{\varphi(m)}\equiv 1\pmod{m}$. Теорема Эйлера доказана.

Заметим, что если $(b,m)>1$, то сравнение $b{}^{\varphi(m)}\equiv 1\pmod{m}$ не может выполняться, так как из него бы следовало, что с некоторым целым числом $y$ верно $b{}^{\varphi(m)}+my= 1$, откуда по второму свойству делимости $(b,m)|1$.

Пусть $(M,m)=1$. Тогда существует бесконечно много решений уравнения $Mx+my=1$. Общее решение имеет вид $x=x_0+m\cdot t,\ y=y_0-M\cdot t,\ t\in\mathbb{Z}$. Если перейти на язык сравнений, то получится, что сравнение $Mx\equiv 1\pmod{m}$ имеет решение $x\equiv x_0\pmod{m}$. Каждого из представителей класса вычетов по модулю $m$, содержащего $x_0$, будем обозначать $M^{-1}$ и будем говорить, что это обратный к $M$ вычет по модулю $m$. Очевидно, что $(M^{-1},m)=1$ и $(M^{-1})^{-1}\equiv M\pmod{m}$. Мы видим, что все вычеты, обратные к данному, содержатся в одном единственном классе по модулю $m$, и для представителей разных классов вычетов по модулю $m$ обратные к ним вычеты будут содержаться также в разных классах по модулю $m$.

Если же $(M,m)>1$, то уравнение $Mx+my=1$ не имеет решений и $M$ не будет иметь обратного элемента по модулю $m$.

Пусть $m_1,\ldots ,m_n$ натуральные попарно взаимно простые числа, и требуется решить систему сравнений $$x\equiv a_1\pmod{m_1};$$ $$\ldots$$ $$x\equiv a_n\pmod{m_n}.$$ Положим $M=m_1\cdots m_n$ и $M_i=\frac{M}{m_i},\ i=1,\ldots ,n$. По условию получается, что при всех $i=1,\ldots ,n$ будет $(M_i,m_i)=1$ и согласно предыдущему пункту можно найти $M_i^{-1}$ по модулю $m_i$.

Теорема 7. Все решения указанной системы состоят из всех представителей одного единственного класса вычетов по модулю $M$ и удовлетворяют условию $$x\equiv a_1\cdot M_1\cdot M_1^{-1}+a_2\cdot M_2\cdot M_2^{-1}+\ldots +a_n\cdot M_n\cdot M_n^{-1}\pmod{M}.$$

Доказательство. Пусть $x,y$ два решения нашей системы. Получаем для каждого $i=1,\ldots ,n$ выполнено сравнение $x\equiv a_i\equiv y\pmod{m_i}$. Таким образом, $x-y$ делится на каждое $m_i$, а значит является их общим кратным и делится на их наименьшее общее кратное, которое по следствию 6 равняется $M$. Это эквивалентно тому, что $x\equiv y\pmod{M}$. Обратно, если $y$ является решением системы и $x\equiv y\pmod{M}$, то $x$ также будет решением системы, так как $x=y+kM$ с некоторым целым числом $k$ и $M\equiv 0\pmod{m_i}$ для каждого $i=1,\ldots ,n$.

Далее, заметим, что при $j\neq i$ имеем $M_j\equiv 0\pmod {m_i} $. Поэтому при любом $i=1,\ldots ,n$ получаем $$a_1\cdot M_1\cdot M_1^{-1}+\ldots +a_n\cdot M_n\cdot M_n^{-1}\equiv a_i\cdot M_i\cdot M_i^{-1}\equiv a_i\pmod {m_i}, $$ то есть данное число является решением нашей системы сравнений. Теорема 7 доказана.

Замечание 5. Формула, приведённая в условии теоремы 7, устанавливает взаимно однозначное соответствие между совокупностью полных систем вычетов по модулям $m_1,\ldots ,m_n$ и полной системой вычетов по модулю $M$. В частности, тот факт, что решение системы единственно по модулю $M$, иногда позволяет на практике угадывать это решение, не прибегая к вычислениям. Например, решением системы $$x\equiv 4\pmod{9};$$ $$x\equiv 5\pmod{8};$$ $$x\equiv 6\pmod{7}$$ очевидно будет $x\equiv 13\pmod{504}$.

Пусть $p$ простое число, $a,b$ целые и $(a,p)=1$. У сравнения $ax\equiv b\pmod{p}$ существует единственное по модулю $p$ решение, так как все решения уравнения $ax+py=b$ имеют вид $x=x_0+pt,\ y=y_0-at,\ t\in\mathbb{Z}$. Оказывается, имеет место более общее утверждение, а именно

Теорема 8 (теорема Лагранжа). Пусть $p$ простое число и $f(x)=a_nx^n+a_{n-1}x^{n-1}+\ldots +a_1x+a_0$, где $a_n,\ldots ,a_0\in\mathbb{Z}$, причём $a_n\not\equiv 0\pmod{p}$. Тогда сравнение $f(x)\equiv 0\pmod{p}$ имеет не более $n$ решений по модулю $p$.

Доказательство. Проведём индукцию по $n$. При $n=1$ справедливость теоремы уже установлена. Пусть утверждение теоремы верно для всех многочленов степени $n-1$. Покажем, что оно справедливо и для многочленов степени $n$. Пусть $f(x)$ – многочлен, описанный в условии теоремы. Если сравнение $f(x)\equiv 0\pmod{p}$ неразрешимо, то утверждение теоремы выполняется. Допустим указанное сравнение имеет некоторое решение $x_0$, то есть $f(x_0)\equiv 0\pmod{p}$. Тогда $$f(x)\equiv f(x)-f(x_0)=a_n(x^n-x_0^n)+a_{n-1}(x^{n-1}-x_0^{n-1})+\ldots +a_1(x-x_0)=(x-x_0)\cdot g(x)\pmod{p},$$ где $g(x)=a_nx^{n-1}+\ldots$ – многочлен степени $n-1$, и по предположению индукции сравнение $g(x)\equiv 0\pmod{p}$ имеет не более $n-1$ решения по модулю $p$. При этом из установленного сравнения следует, что $f(x)\equiv 0\pmod{p}$ тогда и только тогда, когда $g(x)\equiv 0\pmod{p}$ или $x-x_0\equiv 0\pmod{p}$. Второе из этих сравнений имеет единственное решение по модулю $p$, а значит сравнение $f(x)\equiv 0\pmod{p}$ имеет не более $n$ решений. Теорема 8 доказана.

Замечание 6. Если $m$ составное число, то сравнение $f(x)\equiv 0\pmod{m}$ может иметь более $n$ решений по модулю $m$. Например у сравнения $x^2\equiv 4\pmod{15}$ имеется $4$ решения: $x\equiv \pm 2\pmod{15},\ x\equiv \pm 7\pmod{15}$. Дело в том, что если сравнение выполнено по модулю $15$, то оно также выполняется и по модулям $3$ и $5$. C другой стороны, из любой пары решений сравнения по модулям $3$ и $5$ по китайской теореме об остатках единственным образом можно получить одно из решений сравнения по модулю $15$. То есть решений по модулю $15$ будет ровно столько, сколько можно составить различных пар решений по модулям $3$ и $5$. По модулю $3$, как и по модулю $5$ есть ровно два решения, а именно $x\equiv\pm 2$. Это позволяет составить четыре различные пары, которые и отвечают предъявленным решениям по модулю $15$. В общем случае, если пользоваться обозначениями китайской теоремы об остатках, когда у некоторого сравнения будет $N_1,\ldots , N_n$ решений по модулям $m_1,\ldots , m_n$, то у этого же сравнения по модулю $M$ будет $N_1\cdots N_n$ решений.

Пусть $p$ простое нечётное число, $a,b$ целые и $(a,p)=(b,p)=1$. У сравнения $ax\equiv b\pmod{p}$ существует, как мы видели, единственное по модулю $p$ решение. Очевидно, что при различных $a$ эти решения тоже будут различны, ведь из сравнений $a_1x\equiv a_2x\equiv b\pmod{p}$ следовало бы $a_1\equiv a_2\pmod{p}$, так как очевидно $(x,p)=1$. Заметим также, что если $a_1$ есть решение сравнения $ax\equiv b\pmod{p}$, то, наоборот, $a$ будет решением сравнения $a_1x\equiv b\pmod{p}$.

При некоторых $b$ возможно, что само $a$ будет решением сравнения $ax\equiv b\pmod{p}$. Это случится тогда и только тогда, когда разрешимо сравнение $x^2\equiv b\pmod{p}$. Сколько решений может иметь такое сравнение? Пусть $x$ – некоторое решение данного сравнения, тогда $-x$ – тоже его решение. При этом из $(b,p)=1$ следует $x\not\equiv 0\pmod{p}$, а значит $x\not\equiv -x\pmod{p}$, поскольку $p$ нечётно. По теореме Лагранжа более двух решений данное сравнение иметь не может. Следовательно $x$ и $-x$ – все решения данного сравнения. Если же $p|b$, то $x\equiv 0\pmod{p}$, очевидно, является единственным решением.

При $(b,p)=1$ получается, что если сравнение $x^2\equiv b\pmod{p}$ неразрешимо, то приведённая система вычетов по модулю $p$ разбивается на пары чисел $a,a_1$ таких, что $aa_1\equiv b\pmod{p}$, а значит произведение всех $p-1$ элементов приведённой системы вычетов будет сравнимо с $b^{\frac{p-1}{2}}$ по модулю $p$. Если же сравнение $x^2\equiv b\pmod{p}$ разрешимо, то приведённая система вычетов по модулю $p$ разбивается на пары чисел $a,a_1$ таких, что $aa_1\equiv b\pmod{p}$ за исключением двух решений $x$ и $-x$ сравнения $x^2\equiv b\pmod{p}$, произведение которых сравнимо с $-b$ по модулю $p$. Таким образом, произведение всех $p-1$ элементов приведённой системы вычетов будет сравнимо с $-b^{\frac{p-1}{2}}$ по модулю $p$.

Очень удобно рассмотреть следующее обозначение, называемое символом Лежандра:

• $\left(\frac{b}{p}\right)=1$, если $(b,p)=1$ и сравнение $x^2\equiv b\pmod{p}$ разрешимо;
• $\left(\frac{b}{p}\right)=0$, если $(b,p)\neq 1$, то есть $p|b$;
• $\left(\frac{b}{p}\right)=-1$, если сравнение $x^2\equiv b\pmod{p}$ неразрешимо.

Пример 5. $\left(\frac{1}{p}\right)=1$, так как $(1,p)=1$ и сравнение $x^2\equiv 1\pmod{p}$ имеет очевидные решения $x\equiv 1\pmod{p}$ и $x\equiv -1\pmod{p}$.

Рассмотрим как раз случай $b=1$ в проведённых выше рассуждениях. Так как сравнение $x^2\equiv 1\pmod{p}$ разрешимо, то произведение всех $p-1$ элементов приведённой системы вычетов будет сравнимо с $-1^{\frac{p-1}{2}}$, то есть с $-1$ по модулю $p$. Это позволяет доказать ряд известных теорем.

Теорема Вильсона. Пусть $p$ простое число. Тогда $(p-1)!\equiv -1\pmod{p}$.

Доказательство. При $p=2$ утверждение теоремы очевидно выполняется. Поскольку числа $1,2,\ldots ,p-1$ составляют приведённую систему вычетов по модулю $p$, то их произведение, как раз равное $(p-1)!$, сравнимо с $-1$ по модулю $p$ и в случае любого нечётного простого $p$. Теорема Вильсона доказана.

Критерий Эйлера. Пусть $b\in\mathbb{Z}$. Тогда $\left(\frac{b}{p}\right)\equiv b^{\frac{p-1}{2}}\pmod{p}$.

Доказательство. Пусть $b\in\mathbb{Z}, (b,p)=1$. Мы знаем, что если сравнение $x^2\equiv b\pmod{p}$ неразрешимо, то $b^{\frac{p-1}{2}}$ сравнимо с произведением всех элементов приведённой системы вычетов по модулю $p$, которое, в свою очередь, сравнимо с $-1$. Но и символ Лежандра $\left(\frac{b}{p}\right)$ в этом случае тоже равен $-1$. Если же сравнение $x^2\equiv b\pmod{p}$ разрешимо, то $-b^{\frac{p-1}{2}}$ сравнимо с произведением всех элементов приведённой системы вычетов по модулю $p$, а значит $b^{\frac{p-1}{2}}\equiv 1\pmod{p}$. При этом символ Лежандра $\left(\frac{b}{p}\right)$ в этом случае также равен $1$. Пусть теперь $p|b$. Но тогда $b^{\frac{p-1}{2}}\equiv 0\pmod{p}$, и символ Лежандра $\left(\frac{b}{p}\right)$ тоже равен $0$. Таким образом, во всех случаях критерий Эйлера доказан.

Теорема Ферма. Пусть $b\in\mathbb{Z}, (b,p)=1$. Тогда $b^{p-1}\equiv 1\pmod{p}$.

Доказательство. Это очевидно следует из критерия Эйлера, поскольку при $(b,p)=1$ будет $b^{\frac{p-1}{2}}\equiv\pm 1\pmod{p}$, и утверждение теоремы Ферма получится при возведении обеих частей данного сравнения в квадрат. Теорема Ферма доказана.

Второй способ – повторить доказательство теоремы Эйлера, ведь теорема Ферма является её частным случаем при $m=p$.

Заметим, что при $(b,p)\neq 1$, то есть когда $p|b$, будет $b^{p-1}\equiv 0\pmod{p}$. Поэтому, чтобы включить и этот случай в условие теоремы Ферма, используют следующую формулировку: для любого целого числа $b$ выполнено $$b^p\equiv b\pmod{p}.$$

Пусть $p$ нечётное простое число, $a,b\in\mathbb{Z}$. Тогда

1. Если $a\equiv b\pmod{p}$, то $\left(\frac{a}{p}\right)=\left(\frac{b}{p}\right)$;
2. $\left(\frac{a\cdot b}{p}\right)=\left(\frac{a}{p}\right)\left(\frac{b}{p}\right)$;
3. Если $p\nmid b$, то $\left(\frac{b^2}{p}\right)=1$, в частности $\left(\frac{1}{p}\right)=1$;
4. • $\left(\frac{-1}{p}\right)=1$, если $p\equiv 1\pmod{4}$,
   • $\left(\frac{-1}{p}\right)=-1$, если $p\equiv -1\pmod{4}$;
5. • $\left(\frac{2}{p}\right)=1$, если $p\equiv\pm 1\pmod{8}$,
   • $\left(\frac{2}{p}\right)=-1$, если $p\equiv\pm 3\pmod{8}$;
6. Квадратичный закон взаимности. Пусть $p,q$ нечётные простые числа, тогда
   • $\left(\frac{p}{q}\right)=-\left(\frac{q}{p}\right)$, если $p\equiv q\equiv -1\pmod{4}$,
   • $\left(\frac{p}{q}\right)=\left(\frac{q}{p}\right)$ иначе.

Докажем эти свойства символа Лежандра. Пусть $a\equiv b\pmod{p}$, тогда, если $p\nmid b$, то и $p\nmid a$, и сравнение $x^2\equiv a\pmod{p}$ разрешимо тогда и только тогда, когда разрешимо сравнение $x^2\equiv b\pmod{p}$. Если же $p|b$, то также $p|a$. В обоих случаях по определению символа Лежандра получаем, что $\left(\frac{a}{p}\right)=\left(\frac{b}{p}\right)$. Первое свойство доказано.

По критерию Эйлера имеем $$\left(\frac{a\cdot b}{p}\right)\equiv (ab)^{\frac{p-1}{2}}=a^{\frac{p-1}{2}}b^{\frac{p-1}{2}}\equiv\left(\frac{a}{p}\right)\left(\frac{b}{p}\right)\pmod{p}.$$ Поскольку как правая, так и левая часть сравнения есть целое число, не превосходящее $1$ по абсолютной величине, то их разность не превосходит $2$ по абсолютной величине, при этом по определению сравнимости эта разность должна делиться на $p$, которое больше или равно трём, что возможно лишь когда эти два числа равны. Второе свойство доказано.

При $p\nmid b$ сравнение $x^2\equiv b^2\pmod{p}$ имеет два очевидных решения $x\equiv b\pmod{p}$ и $x\equiv -b\pmod{p}$, откуда по определению символа Лежандра получаем, что $\left(\frac{b^2}{p}\right)=1$. Третье свойство доказано.

По критерию Эйлера имеем $$\left(\frac{-1}{p}\right)\equiv (-1)^{\frac{p-1}{2}}\pmod{p}.$$ Опять как правая, так и левая часть сравнения есть целое число, не превосходящее $1$ по абсолютной величине, а модуль по которому эти величины сравнимы, не меньше трёх, а значит эти два числа равны. Но то, что $(-1)^{\frac{p-1}{2}}=1$, если $p\equiv 1\pmod{4}$, и $(-1)^{\frac{p-1}{2}}=-1$, если $p\equiv -1\pmod{4}$, очевидно. Четвёртое свойство доказано.

Пятое свойство можно доказать отдельно, но удобнее воспользоваться следующим результатом:

Лемма Гаусса. Пусть $p$ нечётное простое число, $b\in\mathbb{Z},\ p\nmid b$. Тогда $$\left(\frac{b}{p}\right)=(-1)^N,$$ где $N$ – количество отрицательных среди чисел $\varepsilon_1,\varepsilon_2,\ldots ,\varepsilon_{\frac{p-1}{2}}$, определяемых следующим образом. Поскольку числа $\pm 1,\pm 2,\ldots ,\pm\frac{p-1}{2}$ образуют приведённую систему вычетов по модулю $p$, то любое взаимно простое с $p$ число сравнимо по модулю $p$ ровно с одним из этих чисел. Пусть $k=1, 2,\ldots ,\frac{p-1}{2}$, тогда $b\cdot k\equiv\varepsilon_kr_k\pmod{p}$, где $\varepsilon_k=\pm 1$ и $r_k\in\{1, 2,\ldots ,\frac{p-1}{2}\}$.

Доказательство. Покажем, что среди чисел $r_1, r_2,\ldots ,r_{\frac{p-1}{2}}$ нет равных друг другу, то есть они представляют собой перестановку чисел $1, 2,\ldots ,\frac{p-1}{2}$. От противного, если $i<j$ и $r_i=r_j$, то по определению этих чисел получим, что $b\cdot i\equiv\pm b\cdot j\pmod{p}$, и так как $p\nmid b$, то $i\equiv \pm j\pmod{p}$, что невозможно при $1\leqslant i<j\leqslant\frac{p-1}{2}$. Теперь перемножим левые и правые части сравнений $b\cdot k\equiv\varepsilon_kr_k\pmod{p}$ при всех $k=1, 2,\ldots ,\frac{p-1}{2}$. Получим $$b^{\frac{p-1}{2}}{\textstyle \frac{p-1}{2}!}\equiv\varepsilon_1\cdot\varepsilon_2\cdots\varepsilon_{\frac{p-1}{2}}\cdot r_1\cdot r_2\cdots r_{\frac{p-1}{2}}\pmod{p}.$$ Так как $r_1, r_2,\ldots ,r_{\frac{p-1}{2}}$ есть перестановка чисел $1, 2,\ldots ,\frac{p-1}{2}$, то $r_1\cdot r_2\cdots r_{\frac{p-1}{2}}={\textstyle \frac{p-1}{2}!}$ и на это взаимно простое с $p$ число обе части полученного сравнения можно сократить. Кроме того, по критерию Эйлера $b^{\frac{p-1}{2}}\equiv\left(\frac{b}{p}\right)\pmod{p}$, а по определению числа $N$ имеем $\varepsilon_1\cdot\varepsilon_2\cdots\varepsilon_{\frac{p-1}{2}}=(-1)^N$. Таким образом, находим $\left(\frac{b}{p}\right)\equiv (-1)^N\pmod{p}$, откуда уже знакомыми нам из доказательства третьего и четвёртого свойств рассуждениями приходим к требуемому в лемме Гаусса равенству. Лемма Гаусса доказана.

Воспользуемся леммой Гаусса при $b=2$. Поскольку $2\cdot k\leqslant\frac{p-1}{2}$ при $1\leqslant k\leqslant\left[\frac{p-1}{4}\right]$, то $\varepsilon_1=\ldots =\varepsilon_{[\frac{p-1}{4}]}=1$, а так как $\frac{p-1}{2}<2\cdot k\leqslant p-1$ при $\left[\frac{p-1}{4}\right]< k\leqslant{\textstyle \frac{p-1}{2}}$, то $\varepsilon_{[\frac{p-1}{4}]+1}=\ldots =\varepsilon_{\frac{p-1}{2}}=-1$, например $2\cdot\frac{p-1}{2}\equiv -1\pmod{p}$. Отсюда $N=\frac{p-1}{2}-\left[\frac{p-1}{4}\right]=\left[\frac{p+1}{4}\right]$. Получаем, что $\left(\frac{2}{p}\right)=(-1)^{[\frac{p+1}{4}]},$ и очевидно, что $(-1)^{[\frac{p+1}{4}]}=1$, если $p\equiv\pm 1\pmod{8}$, и $(-1)^{[\frac{p+1}{4}]}=-1$, если $p\equiv\pm 3\pmod{8}$. Пятое свойство доказано.

Если $p=q$, то шестое свойство верно. Пусть теперь $p,q$ различные нечётные простые числа и $b$ произвольное целое число. Будем ассоциировать с ним пару чисел $(b_p,b_q), |b_p|\leqslant\frac{p-1}{2},\ |b_q|\leqslant\frac{q-1}{2}$, где $b\equiv b_p\pmod{p}$ и $b\equiv b_q\pmod{q}$. Поскольку $b_p$ и $b_q$ пробегают полные системы вычетов по модулям соответственно $p$ и $q$, то согласно китайской теореме об остатках множество всех пар $(b_p,b_q)$ можно поставить во взаимно однозначное соответствие с произвольной полной системой вычетов по модулю $pq$. Рассмотрим множества $$P_1=\left\{1,2,\ldots ,\frac{pq-1}{2}\right\},\quad P_2=\left\{-1,-2,\ldots ,-\frac{pq-1}{2}\right\}$$ и несколько их подмножеств $$S_2=\left\{b\in P_1\ \Big|\ 1\leqslant b_p\leqslant\frac{p-1}{2},\ -\frac{q-1}{2}\leqslant b_q\leqslant -1\right\},\quad R_2=\left\{b\in P_2\ \Big|\ 1\leqslant b_p\leqslant\frac{p-1}{2},\ -\frac{q-1}{2}\leqslant b_q\leqslant -1\right\},$$ $$S_3=\left\{b\in P_1\ \Big|\ -\frac{p-1}{2}\leqslant b_p\leqslant -1,\ 1\leqslant b_q\leqslant\frac{q-1}{2}\right\},\quad R_3=\left\{b\in P_2\ \Big|\ -\frac{p-1}{2}\leqslant b_p\leqslant -1,\ 1\leqslant b_q\leqslant\frac{q-1}{2}\right\},$$ $$S_4=\left\{b\in P_1\ \Big|\ -\frac{p-1}{2}\leqslant b_p\leqslant -1,\ -\frac{q-1}{2}\leqslant b_q\leqslant -1\right\},\quad R_4=\left\{b\in P_2\ \Big|\ -\frac{p-1}{2}\leqslant b_p\leqslant -1,\ -\frac{q-1}{2}\leqslant b_q\leqslant -1\right\},$$ $$T_1=\left\{b\in P_1\ \Big|\ b_p=0,\ -\frac{q-1}{2}\leqslant b_q\leqslant -1\right\},\quad T_2=\left\{b\in P_1\ \Big|\ -\frac{p-1}{2}\leqslant b_p\leqslant -1,\ b_q=0\right\}.$$ Так как объединение непересекающихся множеств $P_1$ и $P_2$ образует полную систему вычетов по модулю $pq$, то по вышесказанному ему можно поставить в соответствие множество всевозможных пар $(b_p,b_q)$, а значит объединение множеств $S_2$ и $R_2$ будет содержать все числа $b$, удовлетворяющие условиям $1\leqslant b_p\leqslant\frac{p-1}{2},\ -\frac{q-1}{2}\leqslant b_q\leqslant -1$, откуда $$|S_2|+|R_2|=\frac{p-1}{2}\cdot\frac{q-1}{2}.$$ Но очевидное сопоставление $x\longleftrightarrow -x$ устанавливает взаимно однозначное соответствие между множествами $R_2$ и $S_3$. Поэтому $|R_2|=|S_3|$ и $$|S_2|+|S_3|=\frac{p-1}{2}\cdot\frac{q-1}{2}.$$ Далее, объединение множеств $S_2,\ S_4$ и $T_1$ содержит все числа из $P_1$ с условием $-\frac{q-1}{2}\leqslant b_q\leqslant -1$. Эти числа можно явно перечислить: $$\frac{q+1}{2},\ldots ,q-1,q+\frac{q+1}{2},\ldots ,2q-1,\ldots,\frac{p-3}{2}\cdot q+\frac{q+1}{2},\ldots ,\frac{p-1}{2}\cdot q-1.$$ Их количество равно $\frac{p-1}{2}\cdot\frac{q-1}{2}$, то есть $$|S_2|+|S_4|+|T_1|=\frac{p-1}{2}\cdot\frac{q-1}{2}.$$ Аналогично $$|S_3|+|S_4|+|T_2|=\frac{p-1}{2}\cdot\frac{q-1}{2}.$$ Комбинируя три полученных равенства, находим $$2|S_4|+|T_1|+|T_2|=\frac{p-1}{2}\cdot\frac{q-1}{2}.$$ Откуда $(-1)^{|T_1|+|T_2|}=(-1)^{\frac{p-1}{2}\cdot\frac{q-1}{2}}$, что равносильно $$(-1)^{|T_1|}=(-1)^{|T_2|}(-1)^{\frac{p-1}{2}\cdot\frac{q-1}{2}}.$$ Остаётся заметить, что множество $T_2$ состоит в точности из тех чисел множества $\left\{q,2q,\ldots ,\frac{p-1}{2}q\right\}$, которые по модулю $p$ сравнимы с одним из чисел $-1,-2,\ldots ,-\frac{p-1}{2}$. Их количество есть в точности число $N$ из леммы Гаусса при $b=q$, так что по этой самой лемме $$(-1)^{|T_2|}=\left(\frac{q}{p}\right).$$ Аналогично $$(-1)^{|T_1|}=\left(\frac{p}{q}\right).$$ При этом очевидно, что $(-1)^{\frac{p-1}{2}\cdot\frac{q-1}{2}}=-1$, если $p\equiv q\equiv -1\pmod{4}$, и $(-1)^{\frac{p-1}{2}\cdot\frac{q-1}{2}}=1$ иначе. Квадратичный закон взаимности доказан.

Ещё вводя в рассмотрение символ Лежандра $\left(\frac{b}{p}\right)$ мы установили, что он даёт полную информацию о разрешимости сравнения $x^2\equiv b\pmod{p}$, а именно

• Если $\left(\frac{b}{p}\right)=1$, то сравнение имеет два решения;
• Если $\left(\frac{b}{p}\right)=0$, то сравнение имеет одно решение;
• Если $\left(\frac{b}{p}\right)=-1$, то сравнение не имеет решений.

Это можно резюмировать утверждением, что данное сравнение имеет ровно $\left(\frac{b}{p}\right)+1$ решение. Данное наблюдение можно распространить на произвольное квадратичное сравнение.

Пусть $p$ нечётное простое число и имеется сравнение $ax^2+bx+c\equiv 0\pmod{p}$, где $a,b,c\in\mathbb{Z}$ и $p\nmid a$ (чтобы сравнение имело именно вторую, а не меньшую степень). Домножим обе части сравнения на взаимно простое с $p$ число $4a$. Это не повлияет на разрешимость и не изменит решения данного сравнения. Получим $4a^2x^2+4abx+4ac\equiv 0\pmod{p}$. Выделяя полный квадрат и производя замену $y=2ax+b$, получаем $$y^2\equiv b^2-4ac\pmod{p}.$$ Полученное сравнение, как мы видели, имеет в точности $\left(\frac{b^2-4ac}{p}\right)+1$ решений. Столько же решений будет и у исходного сравнения, так как замена $y=2ax+b$ взаимно однозначно отображает полную систему вычетов по модулю $p$ в таковую же.

Следовательно, для подсчёта числа решений квадратичного сравнения по нечётному простому модулю достаточно уметь вычислять символ Лежандра. Доказанных выше свойств этого символа вполне достаточно для эффективного его вычисления, но чтобы делать это максимально быстро удобно ввести также символ Якоби.

Пусть $P>1$ нечётное натуральное число, $P=p_1\cdots p_s$ – его разложение на простые множители (возможно совпадающие, но все нечётные) и $A\in\mathbb{Z}$. Тогда символ Якоби определяется так: $$\left(\frac{A}{P}\right)=\left(\frac{A}{p_1}\right)\cdots\ \left(\frac{A}{p_s}\right).$$ Свойства символа Лежандра переносятся и на символ Якоби. Пусть $P$ нечётное число, $A,B\in\mathbb{Z}$. Тогда

1. Если $A\equiv B\pmod{P}$, то $\left(\frac{A}{P}\right)=\left(\frac{B}{P}\right)$;
2. $\left(\frac{A\cdot B}{P}\right)=\left(\frac{A}{P}\right)\left(\frac{B}{P}\right)$;
3. Если $(P,B)=1$, то $\left(\frac{B^2}{P}\right)=1$, в частности $\left(\frac{1}{P}\right)=1$;
4. • $\left(\frac{-1}{P}\right)=1$, если $P\equiv 1\pmod{4}$,
   • $\left(\frac{-1}{P}\right)=-1$, если $P\equiv -1\pmod{4}$;
5. • $\left(\frac{2}{P}\right)=1$, если $P\equiv\pm 1\pmod{8}$,
   • $\left(\frac{2}{P}\right)=-1$, если $P\equiv\pm 3\pmod{8}$;
6. Пусть $P,Q$ нечётные числа, большие $1$, тогда
   • $\left(\frac{P}{Q}\right)=-\left(\frac{Q}{P}\right)$, если $P\equiv Q\equiv -1\pmod{4}$,
   • $\left(\frac{P}{Q}\right)=\left(\frac{Q}{P}\right)$ иначе.

Свойства с первого по третье напрямую следуют из определения символа Якоби и аналогичных свойств для символа Лежандра.

Для доказательства четвёртого свойства заметим, что произведение двух чисел, сравнимых с $-1$ по модулю $4$, будет сравнимо с $1$ по модулю $4$. Поэтому, если $P\equiv -1\pmod{4}$, то в разложении $P=p_1\cdots p_s$ количество простых, сравнимых с $-1$ по модулю $4$, нечётно. Но тогда и в произведении $\left(\frac{-1}{p_1}\right)\cdots\ \left(\frac{-1}{p_s}\right)$ количество символов Лежандра, равных $-1$ будет нечётно, откуда $\left(\frac{-1}{P}\right)=-1$. Если же $P\equiv 1\pmod{4}$, то в разложении $P=p_1\cdots p_s$ количество простых, сравнимых с $-1$ по модулю $4$, чётно, и $\left(\frac{-1}{P}\right)=1$.

Для доказательства пятого свойства необходимо заметить, что произведение двух чисел, сравнимых с $\pm 3$ по модулю $8$, даёт $\pm 1$ по модулю $8$. Дальнейшие рассуждения аналогичны предыдущему пункту.

Для доказательства шестого свойства достаточно рассмотреть нетривиальный случай $(P,Q)=1$ и действовать аналогично, исследуя, чётно или нечётно количество простых, сравнимых с $-1$ по модулю $4$, в разложениях $P$ и $Q$.

Замечание 7. Символ Якоби $\left(\frac{A}{P}\right)$ не даёт полной информации о разрешимости сравнения $x^2\equiv A\pmod{P}$. Разумеется, если $\left(\frac{A}{P}\right)=-1$, то сравнение неразрешимо, но если символ Якоби принимает другие значения, то из этого нельзя сделать определённых выводов. Например, поскольку $15\equiv -1\pmod{8}$, то $\left(\frac{2}{15}\right)=1$, однако сравнение $x^2\equiv 2$ неразрешимо ни по модулю $3$, ни по модулю $5$, а следовательно оно не может быть разрешимо и по модулю $15$.

Поэтому главным предназначением символа Якоби является ускорение процедуры вычисления символа Лежандра. Пусть требуется определить количество решений сравнения $$x^2-19x+1\equiv 0\pmod{1013}.$$ Легко убедиться (например с помощью решета Эратосфена), что $1013$ – простое число, а значит данное сравнение будет иметь $1+\left(\frac{19^2-4}{1013}\right)=1+\left(\frac{357}{1013}\right)$ решений. Находим $$\left(\frac{357}{1013}\right)=\left(\frac{1013}{357}\right)=\left(\frac{-58}{357}\right)= \left(\frac{-1}{357}\right)\left(\frac{2}{357}\right)\left(\frac{29}{357}\right)=-\left(\frac{29}{357}\right)=-\left(\frac{357}{29}\right)=-\left(\frac{9}{29}\right)=-1.$$ Здесь мы последовательно применили шестое, первое, второе, четвёртое с пятым, снова шестое и, наконец, третье свойства символа Якоби. Мы имели право так действовать, не оглядываясь на то, что число $357$ является составным. В итоге, получаем, что рассматриваемое сравнение не имеет решений.

Итак, для того, чтобы всё же определить разрешимость сравнения $x^2\equiv A\pmod{P}$ необходимо обладать большей информацией, нежели просто значение символа Якоби $\left(\frac{A}{P}\right)$. Чтобы понять, что это за информация для начала рассмотрим сравнения вида $x^2\equiv A\pmod{p^k}$. Следующий результат описывает даже более полную ситуацию.

Лемма Гензеля. Пусть $p$ простое число, многочлен $f(x)$ имеет целые коэффициенты и его старший коэффициент не сравним с нулём по модулю $p$. Допустим имеется целое число $x_1$ такое, что $f(x_1)\equiv 0\pmod{p}$ и $f'(x_1)\not\equiv 0\pmod{p}$, где $f'(x)$ – производная многочлена $f(x)$. Тогда для любого натурального числа $k$ в любой полной системе вычетов по модулю $p^k$ найдётся единственный элемент $x_k$ с условиями $x_k\equiv x_1\pmod{p}$ и $f(x_k)\equiv 0\pmod{p^k}$.

Прежде чем доказывать лемму Гензеля сформулируем следующий вспомогательный результат.

Лемма ???. Пусть $f(x)$ – многочлен степени $m$. Тогда $$f(x+a)=f(x)+af'(x)+a^2\frac{f''(x)}{2}+\ldots +a^m\frac{f^{(m)}(x)}{m!}.$$

Доказательство достаточно провести для многочлена вида $f(x)=x^n$ ввиду линейности. Для такого многочлена необходимое равенство приобретает вид $$(x+a)^n=x^n+nx^{n-1}a+\frac{n(n-1)}{2}x^{n-2}a^2+\ldots +\frac{n(n-1)\cdots 2\cdot 1}{n!}a^n,$$ так что оно представляет из себя в точности формулу бинома Ньютона. Лемма ??? доказана.

Доказательство леммы Гензеля проведём индукцией по $k$. При $k=1$ в произвольной полной системе вычетов по модулю $p$ найдётся единственный элемент, сравнимый по этому же модулю с $x_1$, а сравнение $f(x_1)\equiv 0\pmod{p}$ выполнено по условию. Пусть теперь $k>1$ и для $k-1$ утверждение верно. Мы ищем элемент $x_k$ с условиями $x_k\equiv x_1\pmod{p}$ и $f(x_k)\equiv 0\pmod{p^k}$. Но для этого элемента будет тогда также выполнено $f(x_k)\equiv 0\pmod{p^{k-1}}$. Ввиду единственности решения этого сравнения по модулю $p^{k-1}$ будем иметь $x_k\equiv x_{k-1}\pmod{p^{k-1}}$. Поэтому $x_k$ следует искать в виде $x_k=x_{k-1}+t\cdot p^{k-1}$ с некоторым целым числом $t$. В приведённой системе вычетов по модулю $p^{k}$ найдётся ровно $p$ элементов такого вида, причём соответствующие им значения $t$ составят полную систему вычетов по модулю $p$. Условие $x_k\equiv x_1\pmod{p}$ будет выполнено автоматически. Для проверки условия $f(x_k)\equiv 0\pmod{p^k}$ воспользуемся леммой ??? и запишем $$f(x_k)=f(x_{k-1}+t\cdot p^{k-1})=f(x_{k-1})+t\cdot p^{k-1}\cdot f'(x_{k-1})+\ldots\equiv f(x_{k-1})+t\cdot p^{k-1}\cdot f'(x_{k-1})\pmod{p^k}.$$ Таким образом, должно быть выполнено $$f(x_{k-1})+t\cdot p^{k-1}\cdot f'(x_{k-1})\equiv 0\pmod{p^k}.$$ Так как $f(x_{k-1})\equiv 0\pmod{p^{k-1}}$, то обе части и модуль этого сравнения можно поделить на $p^{k-1}$. Получим $$\frac{f(x_{k-1})}{p^{k-1}}+t\cdot f'(x_{k-1})\equiv 0\pmod{p}.$$ Поскольку $f(x_{k-1})\equiv f(x_1)\not\equiv 0\pmod{p}$, полученное сравнение относительно $t$ имеет единственное решение. А следовательно и $x_k$ существует и единственно. Лемма Гензеля доказана.

Применим лемму Гензеля для решения сравнения $x^2\equiv A\pmod{p^k}$, где $p$ – нечётное простое число. Если сравнение $x^2\equiv A\pmod{p}$ неразрешимо, то и наше сравнение не может иметь решений при любом натуральном $k$. Если сравнение $x^2\equiv A\pmod{p}$ имеет единственное решение, то $A\equiv 0\pmod{p}$, а значит и решением будет $x_1\equiv 0\pmod{p}$. В этом случае лемма Гензеля неприменима, так как при $f(x)=x^2$ будем иметь $f'(x)=2x$, но $2x_1\equiv 0\pmod{p}$. Однако этот случай достаточно прост, чтобы уделять ему внимание. Пусть теперь сравнение $x^2\equiv A\pmod{p}$ имеет два различных решения $x\equiv\pm x_1\pmod{p}$. Из того, что они различны, следует $2x_1\not\equiv 0\pmod{p}$ и лемма Гензеля может быть применена. Из неё следует, что для каждого натурального $k$ будет иметься ровно два различных решения сравнения $x^2\equiv A\pmod{p^k}$.

Из всего вышесказанного видно, что для нечётного числа $P=p_1^{k_1}\cdots p_m^{k_m}$ сравнение $x^2\equiv A\pmod{P}$ при $(A,P)=1$ будет разрешимо тогда и только тогда, когда разрешимо каждое из сравнений $x^2\equiv A\pmod{p_i},\ i=1,\ldots ,s$, так как отсутствие решений хотя бы по одному простому модулю гарантирует отсутствие решений и по модулю $P$, а наличие решений по каждому из простых модулей по Лемме Гензеля даёт также решения и по модулю степеней этих простых чисел: $x\equiv x_1\pmod{p_1^{k_1}},\ldots ,x\equiv x_m\pmod{p_m^{k_m}}$. Решая полученную систему сравнений (с помощью китайской теоремы об остатках), мы получим решение исходного сравнения по модулю $P$. Всего таких решений найдётся $2^m$, так как по каждому из модулей $p_1^{k_1},\ldots ,p_m^{k_m}$ будет два решения.

Для полноты картины изучим случай $p=2$, при котором лемма Гензеля для сравнения $x^2\equiv A\pmod{2^k}$ также неприменима, поскольку $2x_1\equiv 0\pmod{2}$ независимо от значения $x_1$. По модулям $2$ и $4$ ситуация прозрачна.

Предложение 4. Пусть $A\in\mathbb{Z}$ нечётно, $k\in\mathbb{N},\ k\geqslant 3$. Тогда сравнение $x^2\equiv A\pmod{2^k}$ имеет $4$ решения, если $A\equiv 1\pmod{8}$, и неразрешимо иначе.

Доказательство. Проведём индукцию по $k$. При $k=3$ четыре числа $\pm 1,\pm 3$ удовлетворяют сравнению $x^2\equiv 1\pmod{8}$, а так как они образуют приведённую систему вычетов по модулю $8$, то это все решения данного сравнения. Из этого же следует, что сравнения $x^2\equiv A\pmod{8}$ неразрешимы при $A=-1,\pm 3$.

Пусть теперь для некоторого $k\geqslant 3$ предложение верно. Выберем некоторое $A\equiv 1\pmod{8}$. По предположению индукции найдётся некоторое нечётное число $x_k$ такое, что $x_k^2\equiv A\pmod{2^k}$, то есть $x_k^2=A+c\cdot 2^k$. Если теперь $c$ чётно, то $x_k^2\equiv A\pmod{2^{k+1}}$. Если же $c$ нечётно, то $(x_k+2^{k-1})^2\equiv A\pmod{2^{k+1}}$, то есть сравнение $x^2\equiv A\pmod{2^{k+1}}$ будет иметь некоторое решение $x_{k+1}$. Но вместе с ним оно будет иметь по крайней мере четыре решения $\pm x_{k+1}\pm 2^k$. C другой стороны, поскольку в приведённой системе вычетов по модулю $2^{k+1}$ ровно каждое четвёртое число сравнимо с $1$ по модулю $8$, то, взяв для каждого из этих чисел по четыре решения соответствующего сравнения, мы уже исчерпаем всю приведённую систему вычетов по модулю $2^{k+1}$, а значит более четырёх решений ни у одного из этих сравнений быть не может. Более того, не может быть решений и у сравнений $x^2\equiv A\pmod{2^{k+1}}$ при $A\not\equiv 1\pmod{8}$. Предложение 4 доказано.