Элементы теории чисел

Элементы теории чисел - дополнение

1. Задачник О. Н. Василенко и А. И. Галочкина
2. Задачник Н. Б. Алфутовой и А. В. Устинова
3. Учебник Ю. В. Нестеренко
4. Учебник И. М. Виноградова
5. Учебник Ш. Х. Михеловича
6. Учебник А. Я. Хинчина

$\mathbb{N}$ — множество натуральных чисел $1, 2, 3, 4, 5, 6, \ldots$

$\mathbb{Z}$ — множество целых чисел $0, \pm 1, \pm 2, \pm 3, \pm 4, \ldots$

$[x]$ — целая часть числа $x$ (наибольшее целое число, не превосходящее $x$)

$sgn(x)$ — знак числа $x$ ($sgn(0)=0$ и $sgn(x)=\frac{x}{|x|}$ при $x\neq 0$)

Пусть имеются два целых числа $a$ и $b$. Говорят, что $b$ делит $a$, если существует целое число $b_1$ такое, что $a=b\cdot b_1$. Обозначается это так $b|a$. Также в этом случае ещё говорят, что $a$ делится на $b$. Это обозначается $a\,\vdots\, b$.

Рассмотрим некоторые свойства делимости целых чисел:

1. Пусть $c|b$ и $b|a$. Тогда $c|a$.
   Действительно, по определению имеются целые числа $b_1$ и $c_1$ такие, что $a=b\cdot b_1$ и $b=c\cdot c_1$. Но тогда $a=c\cdot c_1b_1$, то есть $c|a$.
2. Пусть $c|a,\ c|b$ и $k,l\in\mathbb{Z}$. Тогда $c|(ka+lb)$.
   Действительно, по определению имеются целые числа $c_1$ и $c_2$ такие, что $a=c\cdot c_1$ и $b=c\cdot c_2$. Но тогда $ka+lb=c\cdot (kc_1+lc_2)$, что и требуется. Это свойство можно распространить и на произвольное количество чисел.
3. Пусть $k\in\mathbb{Z},k\neq 0$. Тогда $b|a$ тогда и только тогда, когда $kb|ka$.
   Действительно, если $k\in\mathbb{Z},k\neq 0$, то $a=b\cdot b_1$ тогда и только тогда, когда $k\cdot a=k\cdot b\cdot b_1$, где $b_1$ – произвольное целое число.

У числа $1$ есть только один натуральный делитель — оно само. У любого натурального числа $n>1$ имеется как минимум два натуральных делителя – это $1$ и $n$. Если других натуральных делителей у числа $n$ больше нет, то оно называется простым. Примерами простых чисел являются $2,3,5,7,11,13,\ldots$

Таким образом, простые числа — это натуральные числа, имеющие ровно два натуральных делителя. Можно ввести специальную функцию $\tau(n)$, считающую количество натуральных делителей натурального числа $n$. $$\tau(n)=\sum\limits _{d|n}\;1.$$ Тогда натуральное число $n$ простое тогда и только тогда, когда $\tau(n)=2$. Натуральные числа, большие единицы, будем называть составными, если они не являются простыми.

Пример 1. Число $4$ делится на $1,2$ и $4$, а значит $\tau(4)=3$ и это число составное. Число $17$ делится только на $1$ и $17$, а значит $\tau(17)=2$ и это число простое.

Замечание 1. Согласно определению у составного числа $n$ имеется хотя бы один делитель $d$ с условием $1<d<n$. Например, у числа $4$ таким делителем является $2$.

Замечание 2. Целые числа, делящиеся на $2$, называются чётными, а не делящиеся на $2$ — нечётными. Из этого определения видно, что среди чётных натуральных чисел только число $2$ является простым, а все остальные простые числа являются нечётными.

Пусть имеется несколько целых чисел. Их общим делителем называется целое число, делящее каждое из них. Наибольшим общим делителем нескольких целых чисел, не все из которых равны нулю, называется наибольший из их общих делителей. Наибольший общий делитель чисел $a_1,\ldots ,a_n$ обозначается $\textrm{НОД}(a_1,\ldots ,a_n)$ или, чаще всего, просто $(a_1,\ldots ,a_n)$. Заметим, что он будет положительным, то есть натуральным числом.

Пример 2. Пусть $p$ – простое число, $a$ – натуральное. Найдём $(a,p)$. Согласно последнему замечанию достаточно найти лишь натуральные общие делители рассматриваемых чисел и среди них выбрать наибольший. Но у числа $p$ лишь два натуральных делителя – это число $1$ (которое также делит и $a$) и само $p$. Поэтому, если $p\nmid a$ ($p$ не делит $a$), то есть лишь один общий делитель, и $(a,p)=1$. Если же $p|a$, то общих делителей два – $1$ и $p$. Тогда $(a,p)=p$.

Пример 3. Пусть даны натуральные числа $a$ и $b$ и $b|a$. Тогда $(a,b)=b$. Это следует из того, что $b$ является общим делителем чисел $a$ и $b$, но при этом у $b$ не может быть делителей, больших, чем $b$.

Теорема 1. Наибольший общий делитель целых чисел $a_1,\ldots ,a_n$, не все из которых равны нулю, может быть представлен с некоторыми целыми числами $x_1,\ldots ,x_n$ в виде $$(a_1,\ldots ,a_n)=x_1a_1+\ldots +x_na_n.$$

Доказательство. Рассмотрим множество $M=\{y_1a_1+\ldots +y_na_n>0\; |\; y_1,\ldots ,y_n\in\mathbb{Z}\}$. Оно не пусто, поскольку выбор $y_i=a_i,\ i=1,\ldots ,n$ гарантирует, что $y_1a_1+\ldots +y_na_n>0$. Так как это множество состоит из натуральных чисел, то в нём есть наименьший элемент. Пусть он равен $x_1a_1+\ldots +x_na_n$. Положим $d=(a_1,\ldots ,a_n)$. Так как $d|a_1,\ldots ,d|a_n$, то $d|(x_1a_1+\ldots +x_na_n)$, а значит $x_1a_1+\ldots +x_na_n\geqslant d$. Покажем, что $x_1a_1+\ldots +x_na_n$ является общим делителем чисел $a_1,\ldots ,a_n$, тогда по определению наибольшего общего делителя будем иметь $x_1a_1+\ldots +x_na_n\leqslant d$, и из сравнения двух полученных неравенств будет следовать $x_1a_1+\ldots +x_na_n=d$. Поделим $a_1$ на $x_1a_1+\ldots +x_na_n$ с остатком: $$a_1=q(x_1a_1+\ldots +x_na_n)+r,\quad 0\leqslant r<x_1a_1+\ldots +x_na_n.$$ Получаем $r=a_1(1-qx_1)+a_2(-qx_2)+\ldots +a_n(-qx_n)$, и если $r>0$, то $r\in M$ и при этом $r<x_1a_1+\ldots +x_na_n$. Это противоречит выбору $x_1a_1+\ldots +x_na_n$ как наименьшего элемента множества $M$. Значит $r=0$, и $a_1$ делится нацело на $x_1a_1+\ldots +x_na_n$. Аналогично доказывается, что $x_1a_1+\ldots +x_na_n$ делит $a_2,\ldots ,a_n$. Теорема 1 доказана.

Следствие 1. Для любого натурального $n\geqslant 2$ множество всех общих делителей целых чисел $a_1,\ldots ,a_n$ совпадает с множеством всех делителей числа $\textrm{НОД}(a_1,\ldots ,a_n)$. В частности, любой общий делитель нескольких целых чисел делит их наибольший общий делитель.

Доказательство. Согласно теореме 1 существуют целые числа $x_1,\ldots ,x_n$, такие что $(a_1,\ldots ,a_n)=x_1a_1+\ldots +x_na_n$. Тогда по второму свойству делимости $(a_1,\ldots ,a_n)$ делится на любой общий делитель целых чисел $a_1,\ldots ,a_n$. При этом из первого свойства делимости следует, что любой делитель $(a_1,\ldots ,a_n)$ будет являться общим делителем чисел $a_1,\ldots ,a_n$. Таким образом, множество всех общих делителей нескольких целых чисел совпадает с множеством всех делителей их наибольшего общего делителя. Следствие 1 доказано.

Следствие 2. Имеет место формула $$(a_1,\ldots ,a_{n+1})=( (a_1,\ldots ,a_n), a_{n+1}).$$

Доказательство. Множество общих делителей числа $(a_1,\ldots ,a_n)$ и числа $a_{n+1}$ по следствию 1 состоит из множества всех общих делителей чисел $a_1,\ldots ,a_n$, которые одновременно делят ещё и число $a_{n+1}$. Получается, что это множество состоит из всех общих делителей чисел $a_1,\ldots ,a_{n+1}$. Но если два множества совпадают, то и наибольшие элементы этих множеств равны. Получаем $(a_1,\ldots ,a_{n+1})=((a_1,\ldots ,a_n), a_{n+1})$. Следствие 2 доказано.

Лемма 1. Пусть $a,b,c$ – целые числа, $c|ab$ и $(a,c)=1$. Тогда $c|b$.

Доказательство. По теореме 1 найдутся целые числа $x,y$ такие, что $1=ax+cy$. Домножим обе части этого равенства на $b$, получим $b=abx+bcy$. По условию $c|ab$, а значит и $c|abx$. Очевидно, что также $c|bcy$. Из второго свойства делимости имеем $c|b$. Лемма 1 доказана.

Следствие 3. Пусть $a,b$ – целые числа, $p$ – простое число, $p|ab$ и $p\nmid a$. Тогда $p|b$.

Доказательство. Согласно примеру 2, если $p\nmid a$, то $(a,p)=1$, так что все условия леммы 1 соблюдены. Следствие 3 доказано.

Далее

Пусть имеется несколько целых чисел. Их общим кратным называется целое число, делящееся на каждое из них. Наименьшим общим кратным нескольких целых чисел называется наименьшее натуральное из их общих кратных. Наименьшее общее кратное чисел $a_1,\ldots ,a_n$ обозначается $\textrm{НОК}[a_1,\ldots ,a_n]$ или, чаще всего, просто $[a_1,\ldots ,a_n]$.

Теорема 2. Наименьшее общее кратное целых чисел $a_1,\ldots ,a_n$ делит любое общее кратное этих чисел.

Доказательство. Пусть $b=[a_1,\ldots ,a_n]$ и $c$ – произвольное общее кратное этих же чисел. Поделим $c$ на $b$ с остатком: $c=qb+r,\ 0\leqslant r<b$. Тогда $r=c-qb$, и, так как $c$ и $b$ делятся на каждое из чисел $a_1,\ldots ,a_n$, то по второму свойству делимости $r$ также делится на каждое из них, то есть является их общим кратным. Но если $r>0$, то тогда $r$ – натуральное число, меньшее, чем $b$. Это противоречит тому, что $b$ – наименьшее общее кратное этих чисел. Значит $r=0$ и $c$ делится на $b$. Теорема 2 доказана.

С помощью сравнения совокупностей общих кратных из теоремы 2 легко выводится

Следствие 4. $$[a_1,\ldots,a_n, a_{n+1}]=[[a_1,\ldots,a_n], a_{n+1}]. $$

Лемма 2. Пусть $a$ и $b$ натуральные числа. Тогда $\displaystyle\left(\frac{a}{(a,b)},\frac{b}{(a,b)}\right)=1,\quad \left[\frac{a}{(a,b)},\frac{b}{(a,b)}\right]=\frac{[a,b]}{(a,b)}$.

Доказательство. Пусть $d$ – наибольший общий делитель чисел $\displaystyle \frac{a}{(a,b)}$ и $\displaystyle \frac{b}{(a,b)}$. Тогда по третьему свойству делимости число $d\cdot(a,b)$ будет делить $a$ и $b$, то есть будет их общим делителем. Но так как $(a,b)$ является наибольшим из их общих делителей, то $d=1$. Пусть теперь $k$ – наименьшее общее кратное чисел $\displaystyle \frac{a}{(a,b)}$ и $\displaystyle \frac{b}{(a,b)}$. По третьему свойству делимости число $\displaystyle \frac{[a,b]}{(a,b)}$ также будет их общим кратным, поэтому $k\: | \displaystyle \frac{[a,b]}{(a,b)}$, а значит $k\leqslant\displaystyle \frac{[a,b]}{(a,b)}$. C другой стороны, также по третьему свойству делимости, $k\cdot(a,b)$ будет делиться на $a$ и на $b$, то есть будет их общим кратным. Следовательно $[a,b]\: |\: (k\cdot(a,b) )$, и $[a,b]\leqslant(k\cdot(a,b) )$. Из двух полученных неравенств следует $k=\displaystyle \frac{[a,b]}{(a,b)}$. Лемма 2 доказана.

Лемма 3. Пусть $a$ и $b$ натуральные числа, $(a,b)=1$. Тогда $[a,b]=ab$.

Доказательство. Так как $[a,b]$ делится на $a$ и на $b$, то существуют натуральные числа $a_1$ и $b_1$ такие, что $$[a,b]=a\cdot a_1=b\cdot b_1.$$ Значит $b|a\cdot a_1$ и $(a,b)=1$. По лемме 1 имеем $b|a_1$, но тогда $ab|aa_1=[a,b]$ и следовательно $ab\leqslant [a,b]$. C другой стороны $ab$ является общим кратным чисел $a$ и $b$, и по теореме 2 $[a,b]|(ab)$, откуда $[a,b]\leqslant ab$. Из двух полученных неравенств вытекает, что $[a,b]=ab$. Лемма 3 доказана.

Следствие 5. Пусть $a$ и $b$ натуральные числа. Тогда $[a,b](a,b)=ab$.

Доказательство. Из лемм 2 и 3 находим $$\displaystyle\frac{[a,b]}{(a,b)}=\left[\frac{a}{(a,b)},\frac{b}{(a,b)}\right]=\frac{a}{(a,b)}\cdot\frac{b}{(a,b)}.$$ Домножим левую и правую части полученного равенства на $(a,b)^2$, получится в точности требуемое равенство. Следствие 5 доказано.

Следствие 6. Пусть $a_1,\ldots ,a_n$ натуральные числа, и $(a_i,a_j)=1$ для всех $i,j=1,\ldots ,n,\ i\neq j$. Тогда $[a_1,\ldots ,a_n]=a_1\cdots a_n$.

Доказательство. Проведём индукцию по $n$ (покажем, что утверждение верно при $n=2$, а также, что из справедливости утверждения при произвольном $n\geqslant 2$ вытекает его справедливость и при $n+1$, тогда это будет означать, что утверждение верно при всех $n\geqslant 2$). При $n=2$ утверждение следует из леммы 3. Пусть утверждение верно для некоторого $n\geqslant 2$. По предположению индукции $[a_1,\ldots,a_n]=a_1\cdots a_n$. Кроме того, из следствия 3 очевидно вытекает, что $(a_1\cdots a_n, a_{n+1})=1$ (если бы нашёлся общий простой делитель, то он делил бы одновременно $a_{n+1}$ и какое-то из $a_i, i=1,\ldots ,n$, что противоречило бы условию $(a_i,a_{n+1})=1$). Вновь из леммы 3 следует, что $[[a_1,\ldots,a_n], a_{n+1}]=a_1\cdots a_n\cdot a_{n+1}$. Тогда по следствию 4 получаем $$[a_1,\ldots,a_n, a_{n+1}]=[[a_1,\ldots,a_n], a_{n+1}]= a_1\cdots a_n\cdot a_{n+1}. $$ Следствие 6 доказано.

Пусть для двух натуральных чисел $p$ и $q$ необходимо найти их наибольший общий делитель. Для этого применяется следующая процедура. Поделим с остатком $p$ на $q$: $$p=a_0q+r_1,\quad 0\leqslant r_1<q.$$ Из этого равенства и второго свойства делимости видно, что множество всех общих делителей $p$ и $q$ совпадает с множеством всех общих делителей $q$ и $r_1$, а значит $(p,q)=(q,r_1)$. Поделим теперь $q$ на $r_1$ с остатком: $$q=a_1r_1+r_2,\quad 0\leqslant r_2<r_1.$$ Затем $r_1$ на $r_2$ и так далее.

Заметим, что последовательность неотрицательных целых чисел $r_1,r_2,r_3,\ldots$ строго убывающая, так что при некотором $n\geqslant 0$ будет выполнено $r_{n+1}=0$, то есть $$r_{n-2}=a_{n-1}r_{n-1}+r_n,\quad 0\leqslant r_n<r_{n-1}.$$ $$r_{n-1}=a_nr_n.$$ При $n=0$ надо рассматривать лишь последнюю строчку, полагая в ней $r_{-1}=p,r_0=q$. Из последовательности построенных равенств и второго свойства делимости будет следовать цепочка равенств $$(p,q)=(q,r_1)=(r_1,r_2)=\ldots =(r_{n-1},r_n)=r_n.$$ Последнее из этих равенств следует из того, что $r_n|r_{n-1}$ и примера 3. Таким образом, наибольший общий делитель найден и равен $r_n$.

Теорема 1 утверждает, что с некоторыми целыми $x,y$ можно записать $r_n=(p,q)=px+qy$. Алгоритм Евклида позволяет отыскать эти числа явно. Из первого равенства имеем $r_1=p+q(-a_0)$. Из второго $r_2=q-a_1r_1=p(-a_1)+q(1+a_0a_1)$. И так далее последовательно каждое из чисел $r_1,\ldots ,r_n$ выразится в виде линейной комбинации чисел $p$ и $q$ с целыми коэффициентами.

Замечание 3. Из первого в цепочке делений с остатком равенства имеем $$\frac{p}{q}=a_0+\frac{r_1}{q}=a_0+\frac{1}{\frac{q}{r_1}}.$$ Из второго равенства $$\frac{q}{r_1}=a_1+\frac{r_2}{r_1}=a_1+\frac{1}{\frac{r_1}{r_2}}\ldots$$ Из последнего равенства будем иметь $$\frac{r_{n-1}}{r_n}=a_n.$$ Получается представление $\frac{p}{q}$ в виде многоэтажной дроби $$\frac{p}{q}=a_0+\frac{1}{a_1+\frac{1}{a_2+\frac{1}{\ldots\ +\frac{1}{a_n}}}}.$$ Такая конструкция называется цепной дробью и обозначается $[a_0;a_1,a_2,\ldots ,a_n]$. Подробнее о них речь пойдёт в следующих главах. Упомянем лишь, что числа $x,y$, для которых $r_n=px+qy$, могут быть найдены из равенства $$-\frac{x}{y}=a_0+\frac{1}{a_1+\frac{1}{\ldots\ +\frac{1}{a_{n-1}}}}.$$

Пусть $p,q,r$ – целые числа и требуется найти все целые $x,y$, удовлетворяющие уравнению $px+qy=r$.

Предложение 1. Решение данного уравнения существует тогда и только тогда, когда $(p,q)|r$.

Доказательство. Если какое-либо решение $x,y$ существует, то по второму свойству делимости любой общий делитель чисел $p$ и $q$ делит $r$. В частности $(p,q)|r$. Обратно, если $(p,q)|r$, то найдётся целое число $s$ такое, что $(p,q)s=r$. По теореме 1 найдутся целые числа $x_0,y_0$ с условием $px_0+qy_0=(p,q)$, но тогда $p(x_0s)+q(y_0s)=r$. Предложение 1 доказано.

Итак, если $(p,q)\nmid r$, то решений не существует. Если же $(p,q)|r$, то имеется как минимум одно решение, скажем $x_1,y_1$. Чтобы его явно найти, можно с помощью алгоритма Евклида отыскать числа $x_0,y_0$ такие, что $px_0+qy_0=(p,q)$. Тогда, согласно предложению 1, будем иметь $$x_1=x_0\frac{r}{(p,q)},\quad y_1= y_0\frac{r}{(p,q)}.$$ В некоторых простых случаях частное решение $x_1,y_1$ можно просто подобрать.

Пусть $x,y$ – произвольное решение нашего уравнения. Тогда $px+qy=px_1+qy_1$. Поделим обе части равенства на $(p,q)$ и перегруппируем слагаемые. Получим$$\frac{p}{(p,q)}(x-x_1)=-\frac{q}{(p,q)}(y-y_1),$$ то есть $\frac{p}{(p,q)}$ делит $\frac{q}{(p,q)}(y-y_1)$, и по лемме 2 $$\left(\frac{p}{(p,q)},\frac{q}{(p,q)}\right)=1.$$ Отсюда по лемме 1 $\frac{p}{(p,q)}$ делит $(y-y_1)$, или же $y-y_1=\frac{p}{(p,q)}t$ с некоторым целым числом $t$. Но тогда, деля обе части исходного равенства на $\frac{p}{(p,q)}$, находим $x-x_1=-\frac{q}{(p,q)}t$. Получаем, что произвольное решение должно иметь вид $$x=x_1-\frac{q}{(p,q)}t, \qquad y=y_1+\frac{p}{(p,q)}t, \quad t\in\mathbb{Z}.$$ Поскольку подстановка такой пары $x,y$ при любом $t\in\mathbb{Z}$ даёт решение рассматриваемого уравнения, то полученная формула описывает все его решения.

Диофантовым называют уравнение, которое требуется решить в целых числах. Пусть $a_1,\ldots ,a_n$ и $b$ – целые числа и требуется решить диофантово уравнение $a_1x_1+\ldots +a_nx_n=b$. Положим $d=(a_1,\ldots ,a_n)$, тогда повторение рассуждений, проведённых при доказательстве предложения 1, покажет, что если $d\nmid b$, то решений нет, а если $d|b$, то есть. Найти решение можно с помощью следующей процедуры. Необходимо составить матрицу из $n+1$ строки и $n$ столбцов: $$a_1\ a_2\ \ldots\ a_{n-1}\ a_n$$ $$ 1\quad 0\ \ldots\quad 0\quad 0$$ $$0\quad 1\ \ldots\quad 0\quad 0$$ $$\ldots\, \ldots\, \ldots\, \ldots\, \ldots $$ $$ 0\quad 0\ \ldots\quad 1\quad 0$$ $$0\quad 0\ \ldots\quad 0\quad 1$$ и с помощью трёх допустимых операций

• Прибавление к любому столбцу любого другого столбца, умноженного на произвольное целое число (при этом прибавляемый столбец остаётся нетронутым)
• Замена местами любых двух столбцов
• Умножение любого столбца на $-1$

привести эту матрицу к виду $$d\hspace{2.8mm} 0\hspace{2.8mm} \ldots\ 0$$ $$ c_{11} c_{12}\ \ldots c_{1n}$$ $$c_{21} c_{22}\ \ldots c_{2n}$$ $$\ldots\ldots\ldots\ldots $$ $$c_{n1} c_{n2}\ \ldots c_{nn}$$ Добиться этого можно всегда. Например, можно сделать все элементы первой строки неотрицательными (домножая на $-1$ столбцы, в которых первый элемент отрицателен). После этого можно выбрать наименьший ненулевой элемент в первой строке, поделить остальные элементы первой строки на него с остатком и вычесть из всех столбцов столбец, в котором находится этот наименьший элемент, домноженный на подходящее целое число так, чтобы первыми элементами в столбцах оказались уже остатки от деления. В результате наименьший натуральный элемент первой строки будет уменьшаться и, так как процедуру можно продолжать неограниченное число раз, то всё большее количество элементов первой строки будет обнуляться. В итоге станут равны нулю все элементы первой строки, кроме одного, который действительно окажется равен определённому нами выше числу $d$. Это видно из того, что ни одна из трёх допустимых операций со столбцами матрицы не меняет наибольшего общего делителя всех элементов первой строки. Заметим также следующее свойство столбцов изначально построенной матрицы. Верхний элемент столбца равен результату подстановки стоящих под ним элементов вместо $x_1,\ldots , x_n$ в выражение $a_1x_1+\ldots +a_nx_n.$ Например, $a_1=a_1\cdot 1+a_2\cdot 0\ldots +a_n\cdot 0$. Это свойство также сохраняется при любой из трёх допустимых операций со столбцами матрицы. Таким образом $$a_1\cdot c_{11}+a_2\cdot c_{21}\ldots +a_n\cdot c_{n1}=d$$ и $$a_1\cdot c_{1j}+a_2\cdot c_{2j}\ldots +a_n\cdot c_{nj}=0,\quad j=2,\ldots ,n.$$ Значит при любых $t_2,\ldots ,t_n$ вектор $$x_1\hspace{13mm}c_{11}\hspace{11mm}c_{12}\hspace{24mm}c_{1n}$$ $$x_2\hspace{13mm}c_{21}\hspace{11mm}c_{22}\hspace{24mm}c_{2n}$$ $$\cdot\hspace{3mm} =\hspace{.9mm} \frac{b}{d}\hspace{1.9mm} \cdot\hspace{2.4mm} +\hspace{2mm} t_2\hspace{1.9mm} \cdot\hspace{2.7mm} +\hspace{1.5mm}\ldots\hspace{.5mm} +\ t_n\hspace{2.3mm} \cdot$$ $$\cdot\hspace{15mm}\cdot\hspace{14.5mm}\cdot\hspace{27.2mm}\cdot$$ $$x_n\hspace{12.9mm}c_{n1}\hspace{10.9mm}c_{n2}\hspace{23.9mm}c_{nn}$$ будет являться решением уравнения $a_1x_1+\ldots +a_nx_n=b$.

Теперь заметим, что мы выразили векторы $$c_{11}\hspace{11mm}c_{12}\hspace{24mm}c_{1n}$$ $$c_{21}\hspace{11mm}c_{22}\hspace{24mm}c_{2n}$$ $$\cdot\hspace{14.5mm}\cdot\hspace{27.2mm}\cdot$$ $$\cdot\hspace{14.5mm}\cdot\hspace{10.9mm}\ldots\hspace{10.4mm}\cdot$$ $$c_{n1}\hspace{10.9mm}c_{n2}\hspace{23.9mm}c_{nn}$$ с помощью трёх допустимых операций в виде линейных комбинаций векторов $$1\hspace{11mm}0\hspace{24mm}0$$ $$0\hspace{11mm}1\hspace{24mm}0$$ $$\cdot\hspace{11.2mm}\cdot\hspace{24mm}\cdot$$ $$\cdot\hspace{11.2mm}\cdot\hspace{9.1mm}\ldots\hspace{9mm}\cdot$$ $$0\hspace{11mm}0\hspace{24mm}1$$ Значит, если последовательно обратить все эти допустимые операции, то уже векторы $$1\hspace{11mm}0\hspace{24mm}0$$ $$0\hspace{11mm}1\hspace{24mm}0$$ $$\cdot\hspace{11.2mm}\cdot\hspace{24mm}\cdot$$ $$\cdot\hspace{11.2mm}\cdot\hspace{9.1mm}\ldots\hspace{9mm}\cdot$$ $$0\hspace{11mm}0\hspace{24mm}1$$ будут выражены в виде линейных комбинаций векторов $$c_{11}\hspace{11mm}c_{12}\hspace{24mm}c_{1n}$$ $$c_{21}\hspace{11mm}c_{22}\hspace{24mm}c_{2n}$$ $$\cdot\hspace{14.5mm}\cdot\hspace{27.2mm}\cdot$$ $$\cdot\hspace{14.5mm}\cdot\hspace{10.9mm}\ldots\hspace{10.4mm}\cdot$$ $$c_{n1}\hspace{10.9mm}c_{n2}\hspace{23.9mm}c_{nn}$$ Тогда, если мы имеем произвольное решение нашего уравнения, скажем вектор $$x_1\hspace{13mm}1\hspace{11mm}0\hspace{24mm}0$$ $$x_2\hspace{13mm}0\hspace{11mm}1\hspace{24mm}0$$ $$\cdot\hspace{4.5mm} =\hspace{0.4mm} x_1\hspace{0.2mm} \cdot\hspace{1.4mm} +\hspace{1mm} x_2\hspace{0.2mm} \cdot\hspace{1.3mm} +\hspace{1.0mm}\ldots\hspace{.5mm} +\ x_n\hspace{0.2mm} \cdot$$ $$\cdot\hspace{14.7mm}\cdot\hspace{11.5mm}\cdot\hspace{24mm}\cdot$$ $$x_n\hspace{13mm}0\hspace{11mm}0\hspace{23.8mm}1,$$ то он выразится с некоторыми целыми коэффициентами $t_1,t_2,\ldots ,t_n$ в виде $$x_1\hspace{13mm}c_{11}\hspace{11mm}c_{12}\hspace{24mm}c_{1n}$$ $$x_2\hspace{13mm}c_{21}\hspace{11mm}c_{22}\hspace{24mm}c_{2n}$$ $$\cdot\hspace{3mm} =\hspace{.9mm} t_1\hspace{1.9mm} \cdot\hspace{2.4mm} +\hspace{2mm} t_2\hspace{1.9mm} \cdot\hspace{2.7mm} +\hspace{1.5mm}\ldots\hspace{.5mm} +\ t_n\hspace{2.3mm} \cdot$$ $$\cdot\hspace{15mm}\cdot\hspace{14.5mm}\cdot\hspace{27.2mm}\cdot$$ $$x_n\hspace{12.9mm}c_{n1}\hspace{10.9mm}c_{n2}\hspace{23.9mm}c_{nn}$$ Подставив же полученный вектор в уравнение, получим $a_1x_1+\ldots +a_nx_n=t_1\cdot d=b.$ Откуда $t_1=\frac{b}{d}.$

Итак, мы доказали, что все решения нашего уравнения и только они имеют вид $$x_1\hspace{13mm}c_{11}\hspace{11mm}c_{12}\hspace{24mm}c_{1n}$$ $$x_2\hspace{13mm}c_{21}\hspace{11mm}c_{22}\hspace{24mm}c_{2n}$$ $$\cdot\hspace{3mm} =\hspace{.9mm} \frac{b}{d}\hspace{1.9mm} \cdot\hspace{2.4mm} +\hspace{2mm} t_2\hspace{1.9mm} \cdot\hspace{2.7mm} +\hspace{1.5mm}\ldots\hspace{.5mm} +\ t_n\hspace{2.3mm} \cdot$$ $$\cdot\hspace{15mm}\cdot\hspace{14.5mm}\cdot\hspace{27.2mm}\cdot$$ $$x_n\hspace{12.9mm}c_{n1}\hspace{10.9mm}c_{n2}\hspace{23.7mm}c_{nn},$$ где $t_2,\ldots ,t_n$ принимают произвольные целые значения.

Лемма 4. Пусть $n>1$ натуральное число. Тогда у него есть простой делитель.

Доказательство. Рассмотрим наименьший превышающий единицу делитель числа $n$. Обозначим его через $p$. Если это число составное, то, согласно замечанию 1, существует число $d$ такое, что $d|p$ и $1<d<p$. По первому свойству делимости $d|n$. Но тогда получаем противоречие с тем, что $p$ являлось наименьшим из превышающих единицу делителем числа $n$. Значит $p$ – простое, и лемма 4 доказана.

Следствие 7. Пусть $n>1$ натуральное число. Тогда оно представляется в виде произведения простых чисел (некоторые из которых могут совпадать).

Доказательство. По лемме 4 у числа $n$ есть простой делитель, скажем $p_1$. Если $\frac{n}{p_1}>1$, то у этого числа тоже найдётся простой делитель, скажем $p_2$ (при этом допускается и случай $p_2=p_1$). Если и $\frac{n}{p_1p_2}>1$, то у этого числа также найдётся простой делитель, скажем $p_3$. Поскольку последовательность натуральных чисел $n,\frac{n}{p_1},\frac{n}{p_1p_2},\frac{n}{p_1p_2p_3},\ldots $ строго убывает, то за конечное число шагов (гарантированно не более $n-1$ шага) в этой последовательности возникнет наименьшее натуральное число, то есть $1$. Значит, с некоторым $k$ будем иметь $n=p_1\cdot p_2\cdots p_k$, что и требовалось. Следствие 7 доказано.

Следствие 8. Пусть $n>1$ натуральное число. Тогда оно является простым, если у него нет простых делителей, не превосходящих $[\sqrt{n}]$.

Доказательство. Предположим, что у $n$ нет простых делителей, не превосходящих $[\sqrt{n}]$. Покажем, что у него тогда не может быть и простых делителей, больших чем $[\sqrt{n}]$, кроме него самого. Пусть $p|n,\ [\sqrt{n}]+1\leqslant p<n$. Тогда $1<\frac{n}{p}\leqslant\frac{n}{[\sqrt{n}]+1}< [\sqrt{n}]+1$, поскольку $([\sqrt{n}]+1)^2>(\sqrt{n})^2=n$. А так как $\frac{n}{p}$ – число натуральное, то и $\frac{n}{p}\leqslant [\sqrt{n}]$. Но по лемме 4 у числа $\frac{n}{p}$ есть простой делитель $q$. При этом очевидно, что $q\leqslant\frac{n}{p}\leqslant [\sqrt{n}]$ и по первому свойству делимости $q|n$. Противоречие. Следовательно, $n$ не имеет простых делителей, меньших чем $n$. Однако по лемме 4 число $n$ обязано иметь хотя бы один простой делитель. Значит само $n$ необходимо является простым. Следствие 8 доказано.

Теорема 3. Простых чисел бесконечно много.

Доказательство. Предположим, у нас имеется несколько простых чисел $p_1, p_2,\ldots ,p_k$. Рассмотрим число $N=p_1\cdot p_2\cdots p_k+1$. Это число не делится ни на одно из имеющихся простых чисел, так как остаток от деления $N$ на любое из них равен $1$. Вместе с тем, по лемме 4, у числа $N$ должен быть хотя бы один простой делитель. Следовательно, помимо чисел $p_1, p_2,\ldots ,p_k$ существуют и другие простые числа. Поскольку по доказанному мы можем к любой совокупности простых чисел всегда добавить ещё хотя бы одно простое число, то простых чисел бесконечно много. Теорема 3 доказана.

На основе результата леммы 4 возникает следующий алгоритм нахождения всех простых чисел, не превышающих некоторого числа $n$, если известны все простые числа, скажем $p_1,p_2,\ldots ,p_k$, не превосходящие $\sqrt{n}$. Этот алгоритм именуется решетом Эратосфена. Для осуществления алгоритма нужно выписать все числа от $2$ до $n$ включительно. После этого нужно для каждого $i=1,2,\ldots ,k$ вычеркнуть числа $2p_i, 3p_i,\ldots ,\left[\frac{n}{p_i}\right] p_i$. Тогда все невычеркнутые числа и составят список всех простых, не превышающих $n$. Действительно, пусть число $m\leqslant n$ не вычеркнуто. Тогда либо это одно из простых, не превосходящих $\sqrt{n}$, либо оно не делится ни на одно из этих простых. В последнем случае $m$ не делится ни на одно из простых, не превосходящих $\sqrt{m}$, так как $\sqrt{m}\leqslant \sqrt{n}$, поэтому по следствию 8 число $m$ – простое. Очевидно, что каждое простое число, не превосходящее $n$, попадёт в список невычеркнутых, так как оно либо не превосходит $\sqrt{n}$ и не вычеркнуто по условию алгоритма, либо оно больше $\sqrt{n}$ и тогда оно не вычеркнуто, так как по определению не делится на отличные от себя простые числа.

Теорема 4 (основная теорема арифметики). Пусть $n>1$ натуральное число. Тогда $n$ раскладывается в произведение простых чисел, причём единственным образом с точностью до перестановки сомножителей.

Доказательство. Существование разложения показано в следствии 7. Докажем, что разложение единственно. Пусть $n$ – наименьшее из чисел, которые раскладываются в произведение простых более чем одним способом, и два из его разложений имеют вид $$p_1\cdot p_2\cdots p_k=q_1\cdot q_2\cdots q_l.$$ Ни одно из чисел $p_1, p_2,\ldots ,p_k$ не равно ни одному из чисел $q_1, q_2,\ldots ,q_l$, так как в противном случае обе части равенства можно было бы сократить на совпадающие простые, и число $n$ было бы не наименьшим из чисел, которые раскладываются в произведение простых более чем одним способом. Поэтому можно считать, что $p_1<q_1$. Рассмотрим число $m=n-p_1\cdot q_2\cdots q_l$. Оно может быть представлено двумя способами: $$p_1(p_2\cdots p_k - q_2\cdots q_l)=(q_1-p_1)\cdot q_2\cdots q_l.$$ Так как $q_1$ не делится на $p_1$, то по второму свойству делимости и $q_1-p_1$ не делится на $p_1$. Тогда $p_1$ не входит в разложение на простые множители $q_1-p_1=r_1\cdots r_i$. Выпишем также разложение на простые множители числа $p_2\cdots p_k - q_2\cdots q_l=t_1\cdots t_j$. Тогда получим, что число $m$, меньшее чем $n$, имеет два разложения на простые множители $$p_1\cdot t_1\cdots t_j=r_1\cdots r_i\cdot q_2\cdots q_l,$$ в одно из которых входит $p_1$, а в другое – нет. Противоречие с тем, что $n$ – наименьшее из чисел, которые раскладываются в произведение простых более чем одним способом. Следовательно, чисел, раскладывающихся в произведение простых более чем одним способом, не существует. Теорема 4 доказана.

Замечание 4. Разложение числа на простые множители, согласно основной теореме арифметики, единственно с точностью до порядка сомножителей. Один способ упорядочивания сомножителей является общепринятым и называется каноническим. Он подразумевает упорядочивание сомножителей по возрастанию, при этом равные сомножители объединяются в единый множитель в виде простого числа в некоторой степени. В общем виде это выглядит так: $$n=p_1^{\alpha_1}\cdot p_2^{\alpha_2}\cdots p_k^{\alpha_k},\quad p_1<p_2<\ldots <p_k.$$ При этом для каждого простого числа $p$ вводится понятие показателя $\nu_p(n)$ – это та степень, в которой $p$ входит в каноническое разложение числа $n$. Например $\nu_2(12)=2,\ \nu_3(12)=1,\ \nu_5(12)=0$. Убедитесь, что

• $\nu_p(m\cdot n)=\nu_p(m)+\nu_p(n)$
• $\nu_p(m+n)\geqslant\min\{\nu_p(m),\nu_p(n)\}$, причём, если $\nu_p(m)>\nu_p(n)$, то $\nu_p(m+n)=\nu_p(n)$

Пусть $f$ – функция натурального аргумента, принимающая действительные (или даже комплексные) значения. Тогда $f$ называется мультипликативной, если

1. $f$ принимает не только нулевые значения;
2. $f(m\cdot n)=f(m)\cdot f(n)$ при $(m,n)=1$.

Очень важно запомнить, что достаточно, чтобы второе свойство выполнялось только при взаимной простоте чисел $m$ и $n$.

Функция $f$ называется вполне мультипликативной, если

1. $f$ принимает не только нулевые значения;
2. $f(m\cdot n)=f(m)\cdot f(n)$ при любых $m,n$.

Из определения следует, что если $f$ – мультипликативная функция, то $f(1)=1$. Действительно, $$f(1)=f(1\cdot 1)=f(1)\cdot f(1).$$ Отсюда либо $f(1)=0$, либо $f(1)=1$. Но если $f(1)=0$, то для любого натурального $n$ имеем $f(n)=f(n\cdot 1)=f(n)\cdot f(1)=0$, то есть $f$ принимает только нулевые значения, что противоречит определению мультипликативной функции. Значит, $f(1)=1$.

Предложение 2. Пусть $f,g$ – мультипликативные функции. Тогда для любого натурального числа $n$ $$\sum_{d|n}f(d)\cdot g\left(\frac{n}{d}\right)=\prod_{p|n}\left(f(1)\cdot g(p^{\nu_p(n)})+f(p)\cdot g(p^{\nu_p(n)-1})+\ldots +f(p^{\nu_p(n)-1})\cdot g(p)+f(p^{\nu_p(n)})\cdot g(1)\right).$$ Здесь в левой части равенства стоит сумма по всем различным натуральным делителям числа $n$, а справа стоит произведение по всем различным простым делителям числа $n$, $\nu_p(n)$ – показатель, определённый после доказательства основной теоремы арифметики. Например, при $n=12$ данное равенство выглядит так: $$f(1)\cdot g(12)+f(2)\cdot g(6)+f(3)\cdot g(4)+f(4)\cdot g(3)+f(6)\cdot g(2)+f(12)\cdot g(1)=$$ $$=\big(f(1)\cdot g(4)+f(2)\cdot g(2)+f(4)\cdot g(1)\big)\cdot\big(f(1)\cdot g(3)+f(3)\cdot g(1)\big).$$

Доказательство. Пусть $n=p_1^{\alpha_1}\cdots p_k^{\alpha_k}$. Тогда $$\prod_{p|n}\left(f(1)\cdot g(p^{\nu_p(n)})+f(p)\cdot g(p^{\nu_p(n)-1})+\ldots +f(p^{\nu_p(n)-1})\cdot g(p)+f(p^{\nu_p(n)})\cdot g(1)\right)=$$ $$=\prod_{i=1}^k\left(\sum_{\beta_i=0}^{\alpha_i}f(p_i^{\beta_i})\cdot g(p_i^{\alpha_i-\beta_i})\right)=\sum_{\beta_1=0}^{\alpha_1}\ldots\sum_{\beta_k=0}^{\alpha_k}f(p_1^{\beta_1})\cdot g(p_1^{\alpha_1-\beta_1})\cdots f(p_k^{\beta_k})\cdot g(p_k^{\alpha_k-\beta_k}).$$ Воспользуемся мультипликативностью функций $f$ и $g$. Тогда полученное выражение запишется в виде $$\sum_{\beta_1=0}^{\alpha_1}\ldots\sum_{\beta_k=0}^{\alpha_k}f(p_1^{\beta_1}\cdots p_k^{\beta_k})\cdot g(p_1^{\alpha_1-\beta_1}\cdots p_k^{\alpha_k-\beta_k})=\sum_{d|n}f(d)\cdot g\left(\frac{n}{d}\right).$$ Последнее равенство выполняется потому, что $d$ является делителем $n$ тогда и только тогда, когда $d=p_1^{\beta_1}\cdots p_k^{\beta_k}$ и $0\leqslant\beta_i\leqslant\alpha_i$ для каждого $i=1,\ldots ,k$. Предложение 2 доказано.

По двум заданным функциям $f$ и $g$ натурального аргумента всегда можно построить третью функцию, которую мы будем обозначать $f\circ g$, определяемую для каждого натурального числа $n$ так: $$f\circ g(n)=\sum_{d|n}f(d)\cdot g\left(\frac{n}{d}\right).$$ Эта функция называется свёрткой Дирихле функций $f$ и $g$.

Следствие 9. Если функции $f$ и $g$ мультипликативны, то мультипликативна и их свёртка Дирихле.

Доказательство. Пусть $(m,n)=1$. Это значит, что данные числа раскладываются в произведения простых так, что ни одно простое из разложения одного числа не встречается в разложении другого. Пусть $n=p_1^{\alpha_1}\cdots p_k^{\alpha_k},\ m=p_{k+1}^{\alpha_{k+1}}\cdots p_{k+l}^{\alpha_{k+l}}$. Тогда по предложению 2 $$f\circ g(m\cdot n)=\sum_{d|m\cdot n}f(d)\cdot g\left(\frac{m\cdot n}{d}\right)=\prod_{i=1}^{k+l}\left(\sum_{\beta_i=0}^{\alpha_i}f(p_i^{\beta_i})\cdot g(p_i^{\alpha_i-\beta_i})\right)=$$ $$=\prod_{i=1}^{k}\left(\sum_{\beta_i=0}^{\alpha_i}f(p_i^{\beta_i})\cdot g(p_i^{\alpha_i-\beta_i})\right)\prod_{i=k+1}^{k+l}\left(\sum_{\beta_i=0}^{\alpha_i}f(p_i^{\beta_i})\cdot g(p_i^{\alpha_i-\beta_i})\right)=$$ $$=\sum_{d|n}f(d)\cdot g\left(\frac{n}{d}\right)\cdot\sum_{d|m}f(d)\cdot g\left(\frac{m}{d}\right)=f\circ g(m)\cdot f\circ g(n).$$ Следствие 9 доказано.

Теорема 5. Множество всех мультипликативных функций образует абелеву группу относительно операции свёртки Дирихле.

Доказательство. По следствию 9 свёртка Дирихле двух мультипликативных функций есть также мультипликативная функция. Заметим, что $$f\circ g(n)=\sum_{d|n}f(d)\cdot g\left(\frac{n}{d}\right)=\sum_{d_1\cdot d_2=n}f(d_1)\cdot g(d_2)=\sum_{d_2\cdot d_1=n}g(d_2)\cdot f(d_1)=g\circ f(n),$$ то есть свёртка Дирихле коммутативна. Аналогично доказывается ассоциативность свёртки Дирихле: $$f\circ \big(g\circ h\big)(n)=\sum_{d_1\cdot d'=n}f(d_1)\cdot\big(g\circ h\big)(d')= \sum_{d_1\cdot d'=n}f(d_1)\cdot\left(\sum_{d_2\cdot d_3=d'}g(d_2)\cdot h(d_3)\right)=$$ $$=\sum_{d_1\cdot d_2\cdot d_3=n}f(d_1)\cdot g(d_2)\cdot h(d_3)=\sum_{d\cdot d_3=n}\left(\sum_{d_1\cdot d_2=d}f(d_1)\cdot g(d_2)\right)\cdot h(d_3)=\big(f\circ g\big)\circ h(n).$$ Определим функцию $\varepsilon(n)$ так, что $\varepsilon(1)=1$ и $\varepsilon(n)=0$ при всех $n>1$. Тогда очевидно, что $\varepsilon(n)$ мультипликативна, и для любой функции $f$ $$f\circ\varepsilon=\varepsilon\circ f=f.$$ Осталось показать, что для любой мультипликативной функции $f$ существует мультипликативная функция $f'$ такая, что $$f\circ f'=\varepsilon.$$ Поскольку $f\circ f'(1)=f(1)\cdot f'(1)=1\cdot 1=1=\varepsilon(1)$, то благодаря мультипликативности достаточно, чтобы для любого простого числа $p$ для каждого $i=1,2,\ldots$ выполнялось $$f\circ f'(p^i)=f(1)\cdot f'(p^i)+f(p)\cdot f'(p^{i-1})+\ldots +f(p^{i-1})\cdot f'(p)+f(p^i)\cdot f'(1)=0=\varepsilon(p^i).$$ Ясно как подобрать функцию $f'$. Нужно задать $f'(p)$ так, чтобы выписанное равенство выполнялось при $i=1$. После этого нужно задать $f'(p^2)$ так, чтобы равенство выполнялось при $i=2$. Продолжая эту процедуру, можно задать (причём единственным образом) значение функции $f'$ на $p^i$ при любом $i$. Теорема 5 доказана.

В доказательстве теоремы 5 уже появился первый пример мультипликативной (и даже вполне мультипликативной) функции — это нейтральный элемент группы мультипликативных функций — функция $\varepsilon(n)$.

Функции $\textrm{id}(n)=n$ и ${\bf 1}(n)=1$, очевидно, тоже (вполне) мультипликативны.

Рассмотрим функцию $\tau(n)$, которая подсчитывает количество различных натуральных делителей числа $n$. Имеем $$\tau(n)=\sum_{d|n}1=\sum_{d|n}{\bf 1}(d)\cdot {\bf 1}\left(\frac{n}{d}\right)={\bf 1}\circ{\bf 1}(n).$$ Теперь по следствию 9 функция $\tau(n)$ мультипликативна. Легко увидеть, что $$\tau(p_1^{\alpha_1}\cdots p_k^{\alpha_k})=(\alpha_1+1)\cdots(\alpha_k+1).$$

Для функции $\sigma(n)$, которая подсчитывает сумму различных натуральных делителей числа $n$, находим $$\sigma(n)=\sum_{d|n}d=\sum_{d|n}\textrm{id}(d)\cdot {\bf 1}\left(\frac{n}{d}\right)=\textrm{id}\circ{\bf 1}(n).$$ Отсюда по следствию 9 функция $\sigma(n)$ также мультипликативна. При этом $$\sigma(p_1^{\alpha_1}\cdots p_k^{\alpha_k})=(1+p_1+p_1^2+\ldots +p_1^{\alpha_1})\cdots(1+p_k+p_k^2+\ldots +p_k^{\alpha_k})=\frac{p_1^{\alpha_1+1}-1}{p_1-1}\cdots\frac{p_k^{\alpha_k+1}-1}{p_k-1}.$$

Функция Мёбиуса $\mu(n)$ определяется так:

• $\mu(1)=1$;
• $\mu(n)=0$, если $m^2|n$ при некотором $m>1$;
• $\mu(n)=(-1)^k$, если $n$ есть произведение первых степеней $k$ различных простых чисел.

Её мультипликативность следует из определения. Действительно, пусть $p^2|m$ или $p^2|n$. Тогда $\mu(m\cdot n)=0=\mu(m)\cdot\mu(n)$. Если же $(m,n)=1,\ m=q_1\cdots q_l,\ n=p_1\cdots p_k$, то $\mu(m\cdot n)=(-1)^{l+k}=(-1)^{l}\cdot (-1)^{k}=\mu(m)\cdot\mu(n)$. При этом $\mu(n)$ не является вполне мультипликативной, так как при простом $p$ имеем $\mu (p\cdot p)=0$, но $\mu(p)\cdot\mu (p)=(-1)\cdot (-1)=1$.

Пользуясь предложением 2, можно заметить, что $$\mu\circ {\bf 1}(n)=\prod_{p|n}(\mu(1)+\mu(p)+\mu(p^2)+\ldots+\mu(p^{\nu_p(n)}) )=\prod_{p|n}(1-1+0+\ldots +0)=\varepsilon(n).$$ Так что функция Мёбиуса является обратной функцией к тождественной единице ${\bf 1}(n)$ относительно операции свёртки Дирихле. Также заметим, что $$\mu\circ\textrm{id}(n)=\prod_{p|n}(\mu(1)\cdot p^{\nu_p(n)}+\mu(p)\cdot p^{\nu_p(n)-1}+\mu(p^2)\cdot p^{\nu_p(n)-2}+\ldots+\mu(p^{\nu_p(n)})\cdot 1)=\prod_{p|n}(p^{\nu_p(n)}-p^{\nu_p(n)-1}).$$

Из равенства $\mu\circ {\bf 1}=\varepsilon$ и ассоциативности свёртки Дирихле вытекает знаменитая формула обращения Мёбиуса: $$f=g\circ {\bf 1}\Longleftrightarrow g=f\circ\mu .$$

Пример 4. Какая функция получится в результате свёртки Дирихле функции Мёбиуса с функцией суммы делителей? Мы уже показали, что $\sigma=\textrm{id}\circ{\bf 1}$. По формуле обращения Мёбиуса находим $\textrm{id}=\sigma\circ\mu$, то есть $\sum_{d|n}\sigma(d)\cdot\mu\left(\frac{n}{d}\right)=n$. Аналогично из $\tau={\bf 1}\circ{\bf 1}$ получаем ${\bf 1}=\tau\circ\mu$, то есть $\sum_{d|n}\tau(d)\cdot\mu\left(\frac{n}{d}\right)=1$.

Функция Эйлера $\varphi (n) $ подсчитывает количество натуральных чисел, не превосходящих $n$ и взаимно простых с $n$. Например, среди чисел от $1$ до $6$ только числа $1$ и $5$ взаимно просты с числом $6$, поэтому $\varphi (6)=2$.

Для функции Эйлера можно найти следующее представление. $$\varphi (n) =\sum_{1\leqslant k\leqslant n, (k, n)=1} 1=\sum_{k=1}^n\varepsilon ( (k, n) )=\sum_{k=1}^n\mu\circ {\bf 1} ( (k, n) )=$$ $$=\sum_{k=1}^n\sum_{d|(k, n)}\mu(d)=\sum_{d|n}\mu(d)\sum_{1\leqslant k\leqslant n,\ k\,\vdots\, d}1=\sum_{d|n}\mu(d)\frac {n}{d}=\mu\circ\textrm {id}(n). $$ По предложению 2, таким образом, функция $\varphi (n) $ мультипликативна. Здесь при перемене местами двух сумм мы воспользовались следующим соображением: если $d|(k, n)$, то $d|k$ и $d|n$. Так как $k$ меняется от $1$ до $n$, то $d$ пробежит все натуральные делители числа $n $, причём некоторые, возможно, по несколько раз. Каждое конкретное $d$ встречается столько раз, сколько найдётся чисел $k$, делящихся на это $d$. А их будет ровно $\frac{n}{d}$.

Из равенства $\varphi=\mu\circ\textrm {id} $ по формуле обращения Мёбиуса находим $\textrm {id}=\varphi\circ {\bf 1} $, то есть $\sum_{d|n}\varphi(d)=n$.

Покажем явную формулу для функции Эйлера. Имеем $$\varphi (n) =\mu\circ\textrm {id}(n)=\prod_{p|n}(p^{\nu_p(n)}-p^{\nu_p(n)-1}). $$ Последнее равенство доказано выше в разделе про функцию Мёбиуса.

Поясним отдельно эту формулу в двух простых случаях. Пусть $p$ – простое число. Тогда среди чисел $1,\ldots ,p$ с ним взаимно просты все, кроме него самого. Получаем $\varphi(p)=p-1$. Среди же чисел $1,\ldots ,p^{\alpha}$ взаимно просты с $p^{\alpha}$ будут все, кроме тех, что делятся на $p$. А таких чисел ровно $p^{\alpha-1}$. Следовательно, $\varphi(p^{\alpha})=p^{\alpha}-p^{\alpha-1}$.

Иногда в формуле для функции Эйлера избегают использования показателя $\nu_p(n)$. Заметим, что $$\varphi (n) =\prod_{p|n}(p^{\nu_p(n)}-p^{\nu_p(n)-1})=\prod_{p|n}p^{\nu_p(n)}\cdot\left(1-\frac{1}{p}\right)=n\cdot\prod_{p|n}\left(1-\frac{1}{p}\right).$$ Последнее равенство справедливо, так как $\prod_{p|n}p^{\nu_p(n)}=n$.

Замечание 5. Равенство $\varphi\circ {\bf 1}=\textrm {id} $ можно получить самостоятельно из очень простых соображений, если уже установлена мультипликативность функции Эйлера. Воспользуемся предложением 2: $$\sum_{d|n}\varphi(d)=\prod_{p|n}(\varphi(1)+\varphi(p)+\varphi(p^2)+\ldots +\varphi(p^{\nu_p(n)}) ) =\prod_{p|n}(1+p-1+p^2-p+\ldots +p^{\nu_p(n)}-p^{\nu_p(n)-1})=\prod_{p|n}p^{\nu_p(n)}=n.$$

Полученная выше формула для функции Эйлера может быть доказана и с помощью формулы включений и исключений. Сформулируем последнюю.

Пусть имеется $N$ объектов, которые могут обладать (или нет) свойствами $ a_1,\ldots , a_k $. Будем обозначать через $N (a_{i_1},\ldots ,a_{i_j}) $ количество тех из наших $N $ объектов, что обладают каждым из свойств $a_{i_1},\ldots ,a_{i_j},\ 1\leqslant i_1,\ldots , i_j\leqslant k$ (но при этом, возможно, и какими-то ещё свойствами). За $ N_0^{(k)}$ обозначим количество тех из наших $N $ объектов, которые не обладают ни одним из свойств $a_1,\ldots ,a_k$.

Теорема 6 (формула включений и исключений). $$N_0^{(k)}=N-N(a_1)-N(a_2)-\ldots - N(a_k)+N(a_1,a_2)+N(a_1,a_3)+\ldots +N(a_{k-1},a_k)-$$ $$-N(a_1,a_2,a_3)-\ldots -N(a_{k-2},a_{k-1},a_k)+\ldots +(-1)^k\cdot N(a_1,\ldots ,a_k).$$

Доказательство. Проведём индукцию по $k$ (если мы покажем, что утверждение верно при $k=1$, а также, что из справедливости утверждения при произвольном натуральном $k$ следует его справедливость и при $k+1$, то утверждение будет справедливо при всех натуральных $k$).

При $k=1$ утверждается, что количество объектов, не обладающих свойством $a_1$, есть количество всех объектов за вычетом количества объектов, которые обладают этим свойством: $$N_0^{(1)}=N-N(a_1).$$ Это очевидно. Пусть для некоторого $k\geqslant 1$ утверждение теоремы верно и пусть имеется ещё одно свойство $a_{k+1}$. Пусть $M$ – это количество всех тех из наших $N$ объектов, которые обладают свойством $a_{k+1}$. Обозначим через $M (a_{i_1},\ldots ,a_{i_j})$ количество тех из только что выделенных $M$ объектов, что обладают каждым из свойств $a_{i_1},\ldots ,a_{i_j},\ 1\leqslant i_1,\ldots , i_j\leqslant k$. За $M_0$ обозначим количество тех из этих же $M$ объектов, которые не обладают ни одним из свойств $a_1,\ldots ,a_k$. Заметим, что, вообще говоря, $M=N(a_{k+1})$ и $M (a_{i_1},\ldots ,a_{i_j})=N(a_{i_1},\ldots ,a_{i_j},a_{k+1})$. Запишем формулу включений и исключений для этих выделенных $M$ объектов: $$M_0=M-M(a_1)-\ldots - M(a_k)+M(a_1,a_2)+\ldots +M(a_{k-1},a_k)+\ldots +(-1)^k\cdot M(a_1,\ldots ,a_k).$$ Очевидно, что $N_0^{(k+1)}=N_0^{(k)}-M_0$, так как количество чисел, не обладающих ни одним из свойств $a_1,\ldots ,a_k,a_{k+1}$ равно количеству чисел, не обладающих ни одним из свойств $a_1,\ldots ,a_k$, за вычетом количества тех из них, что обладают свойством $a_{k+1}$. Имеем $$N_0^{(k+1)}=N_0^{(k)}-M_0=N-N(a_1)-\ldots - N(a_k)+N(a_1,a_2)+\ldots +N(a_{k-1},a_k)+\ldots +(-1)^k\cdot N(a_1,\ldots ,a_k)-$$ $$-\big(M-M(a_1)-\ldots - M(a_k)+M(a_1,a_2)+\ldots +M(a_{k-1},a_k)+\ldots +(-1)^k\cdot M(a_1,\ldots ,a_k)\big)=$$ $$=N-N(a_1)-\ldots - N(a_k)-N(a_{k+1})+N(a_1,a_2)+\ldots +N(a_{k-1},a_k)+N(a_1,a_{k+1})+\ldots +N(a_k,a_{k+1})+\ldots +$$ $$+(-1)^{k+1}\cdot N(a_1,\ldots ,a_k,a_{k+1}).$$ Теорема 6 доказана.

Пусть теперь у нас есть натуральное число $N=p_1^{\alpha_1}\cdots p_k^{\alpha_k}$. Рассмотрим $N$ объектов, которыми будут числа $1,2,\ldots ,N$. Введём свойства $ a_1,\ldots , a_k $ так: натуральное число обладает свойством $a_i, i=1,\ldots ,k$, если $p_i$ делит данное число. Очень легко сосчитать $N (a_{i_1},\ldots ,a_{i_j}) $, ведь некоторое число делится одновременно на $p_{i_1},\ldots ,p_{i_j}$ тогда и только тогда, когда оно делится на $p_{i_1}\cdots p_{i_j}$, а таких чисел ровно $\frac{N}{p_{i_1}\cdots p_{i_j}}$. Заметим также, что $N_0^{(k)}=\varphi(N)$, поскольку число не делится ни на одно из простых $p_1,\ldots ,p_k$ тогда и только тогда, когда это число взаимно просто с $N$. Имеем $$\varphi(N)=N_0^{(k)}=N-N(a_1)-\ldots - N(a_k)+N(a_1,a_2)+\ldots +N(a_{k-1},a_k)+\ldots +(-1)^k\cdot N(a_1,\ldots ,a_k)=$$ $$=N-\frac{N}{p_1}-\ldots -\frac{N}{p_k}+\frac{N}{p_1\cdot p_2}+\ldots+\frac{N}{p_{k-1}\cdot p_k}+\ldots+(-1)^k\frac{N}{p_1\cdots p_k}=$$ $$=N\cdot\Big(1-\frac{1}{p_1}-\ldots -\frac{1}{p_k}+\frac{1}{p_1\cdot p_2}+\ldots+\frac{1}{p_{k-1}\cdot p_k}+\ldots+(-1)^k\frac{1}{p_1\cdots p_k}\Big)=$$ $$=N\cdot\prod_{i=1}^{k}\left(1-\frac{1}{p_i}\right)=N\cdot\prod_{p|N}\left(1-\frac{1}{p}\right).$$ Заметим, что в сумме в предпоследней строчке перед каждым слагаемым вида $\frac{1}{p_{i_1}\cdots p_{i_j}}$ стоит знак $(-1)^j$, что по определению функции Мёбиуса равно $\mu(p_{i_1}\cdots p_{i_j})$.

На самом деле, мультипликативность функции Эйлера можно доказать, пользуясь совсем простыми соображениями. Пусть $m,n$ – натуральные числа и $(m,n)=1$. Тогда натуральное число взаимно просто с $m\cdot n$ тогда и только тогда, когда оно взаимно просто как с $m$, так и с $n$. Запишем числа $1,2,\ldots ,m\cdot n$ в несколько строк одинаковой длины: $${}\hspace{10mm}1\hspace{28mm}2\hspace{28mm}3\hspace{8mm}\ldots\hspace{9mm}n$$ $${}\hspace{6mm}n+1\hspace{20mm}n+2\hspace{20mm}n+3\hspace{7mm}\ldots\hspace{7mm}2n$$ $${}\hspace{11mm}\vdots\hspace{29mm}\vdots\hspace{29mm}\vdots\hspace{7mm}\ldots\hspace{10mm}\vdots$$ $$(m-1)n+1\hspace{5mm}(m-1)n+2\hspace{5mm}(m-1)n+3\hspace{6mm}\ldots\hspace{5mm}m\cdot n$$ По второму свойству делимости в каждой строке столько же взаимно простых с $n$ чисел, сколько и в первой строке, а именно $\varphi(n)$, причём взаимно простые с $n$ числа из каждой строки стоят в одних и тех же столбцах, то есть для каждого столбца либо все элементы взаимно просты с $n$ (и таких столбцов $\varphi(n)$), либо все элементы не взаимно просты с $n$. Покажем теперь, что все числа, которые стоят в любом из столбцов, дают различные остатки при делении на $m$. Поскольку в каждом столбце находится $m$ чисел, то это будет означать, что при делении на $m$ они дают все $m$ остатков, какие только бывают. А значит, снова по второму свойству делимости, среди них будет столько же чисел, взаимно простых с $m$, сколько их среди чисел $0,1,2,\ldots ,m-1$, а именно $\varphi(m)$. Тогда всего в нашей таблице чисел, взаимно простых одновременно с $m$ и с $n$, будет $\varphi(m)\cdot\varphi(n)$. С другой стороны, это количество чисел среди $1,2,\ldots ,m\cdot n$, взаимно простых с $m\cdot n$, что равно $\varphi(m\cdot n)$.

Итак, числа в $k$-м столбце имеют вид $a\cdot n+k,\ a=0,1,2,\ldots ,m-1$. Допустим, у двух из них совпали остатки при делении на $m$. То есть $a_1\cdot n+k=q_1\cdot m+r$ и $a_2\cdot n+k=q_2\cdot m+r$, где $0\leqslant a_1<a_2<m$. Но тогда $(a_2-a_1)n=(q_2-q_1)m$, и, так как $(m,n)=1$, то $m|(a_2-a_1)$, однако же $0< a_2-a_1<m$. Полученное противоречие показывает, что остатки у всех чисел в столбце различны.

Пусть $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)$ имеет целые коэффициенты. Допустим имеется целое число $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}$.

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

Лемма 5. Пусть $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,$$ так что оно представляет из себя в точности формулу бинома Ньютона. Лемма 5 доказана.

Доказательство леммы Гензеля проведём индукцией по $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}$ воспользуемся леммой 5 и запишем $$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=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 доказано.

Замечание 8. Пусть многочлен $f(x)$ имеет целые коэффициенты, и требуется решить сравнение $f(x)\equiv 0\pmod{p_1^{k_1}\cdots p_m^{k_m}}$, где одно из $p_i$ может быть и чётным. Для этого нужно найти решения сравнений $f(x)\equiv 0\pmod{p_i^{k_i}}$ при всех $i=1,\ldots ,m$, и если хотя бы одно из них неразрешимо, то и у исходного сравнения решений нет. Если же каждое из указанных сравнений имеет, скажем, $T_i$ различных решений вида $x\equiv x_1\pmod{p_1^{k_1}},\ldots ,x\equiv x_m\pmod{p_m^{k_m}}$, то, решая такую систему сравнений (с помощью китайской теоремы об остатках), мы получим решение исходного сравнения по модулю $P$. Всего, действуя таким образом, найдётся $T_1\cdots T_m$ решений исходного сравнения.

Из всего вышесказанного видно, что если $P=p_1^{k_1}\cdots p_m^{k_m}$, сравнение $x^2\equiv A\pmod{P}$ будет разрешимо тогда и только тогда, когда разрешимо каждое из сравнений $x^2\equiv A\pmod{p_i},\ i=1,\ldots ,s$. При этом, если, скажем, $p_1=2$, то по модулю $p_1^{k_1}$ количество решений определяется с учётом предложения 4, а если $p_i^{k_i}$ – число нечётное, то в соответствии с рассуждениями, идущими после леммы Гензеля. При этом случаи $p_i|A$ нужно аккуратно разбирать индивидуально.

Пусть $m$ натуральное число. Если целое число $a$ не взаимно просто с $m$, то сравнение $$a^d\equiv 1\pmod{m}$$ невозможно ни при каком натуральном $d$, так как левая часть сравнения и модуль будут делиться на одно и то же отличное от $1$ натуральное число. Если же $(a,m)=1$, то натуральное число $d$, с которым это сравнение будет выполняться, обязательно найдётся. Например по теореме Эйлера подойдёт $d=\varphi(m)$.

Наименьшее натуральное $d$, с которым выполняется сравнение $a^d\equiv 1\pmod{m}$, называется показателем числа $a$ по модулю $m$. Из теоремы Эйлера видно, что показатель любого числа не превосходит $\varphi(m)$, но он может быть и меньше этого числа. Например, показатель числа $2$ по модулю $7$ равен $3$, поскольку $2^3\equiv 1\pmod{7}$ и $2^1\not\equiv 1\pmod{7},\ 2^2\not\equiv 1\pmod{7}$. При этом $\varphi(7)=6$.

Но если всё же показатель числа $a$ оказался равен $\varphi(m)$, то это число $a$ называется первообразным корнем по модулю $m$. Например, $3^1\not\equiv 1\pmod{7},\ 3^2\not\equiv 1\pmod{7},\ 3^3\not\equiv 1\pmod{7},\ 3^4\not\equiv 1\pmod{7},\ 3^5\not\equiv 1\pmod{7}$. С другой стороны, очевидно, что $3^6\equiv 1\pmod{7}$, а значит $3$ является первообразным корнем по модулю $7$.

Предложение 5. Пусть $d$ – показатель числа $a$ по модулю $m$ и также с некоторым целым числом $n$ выполняется сравнение $a^n\equiv 1\pmod{m}$. Тогда $d|n$.

Доказательство. От противного, пусть $n=qd+r,\ 0<r<d$. Тогда $a^r=a^{n-qd}=a^n(a^d)^{-q}\equiv 1\pmod{m}$, причём $0<r<d$, но это противоречит тому, что $d$ является показателем числа $a$. Предложение 5 доказано.

Следствие 11. Пусть $d$ – показатель числа $a$ по модулю $m$. Тогда $d|\varphi(m)$.

Доказательство. Рассуждения в начале данного параграфа показывают, что наличие у числа $a$ показателя означает, что $(a,m)=1$, а значит применима теорема Эйлера и $a^{\varphi(m)}\equiv 1\pmod{m}$. По предложению 5 теперь $d|\varphi(m)$. Следствие 11 доказано.

Следствие 12. Если $(a,m)=1$ и $d$ – показатель числа $a$ по модулю $m$, то $a^k\equiv a^n\pmod{m}$ тогда и только тогда, когда $k\equiv n\pmod{d}$.

Доказательство. Если $k\equiv n\pmod{d}$, то с некоторым $s$ будет $k=n+sd$. Тогда $a^k=a^n(a^d)^s\equiv a^n\pmod{m}$. Обратно, если $a^k\equiv a^n\pmod{m}$, то $a^n(a^{k-n}-1)\equiv 0\pmod{m}$, и так как $(a,m)=1$, то $a^{k-n}\equiv 1\pmod{m}$, откуда по предложению 5 $d|k-n$, то есть $k\equiv n\pmod{d}$. Следствие 12 доказано.

Следствие 13. Если $a$ – первообразный корень по модулю $m$, то числа $a^0,a^1,\ldots ,a^{\varphi(m)-1}$ образуют приведённую систему вычетов по модулю $m$.

Доказательство. По следствию 12, если $a^k\equiv a^n\pmod{m},\ 0\leqslant n<k<\varphi(m)$, то $k-n$ делится на показатель числа $a$, что невозможно, так как по определению первообразного корня показателем числа $a$ является $\varphi(m)$, но $0<k-n<\varphi(m)$. Значит мы имеем $\varphi(m)$ попарно не сравнимых по модулю $m$ чисел, каждое из которых взаимно просто с $m$. Очевидно они образуют приведённую систему вычетов по модулю $m$. Следствие 13 доказано.

Пусть $p$ простое число. Согласно следствию 13 показателем какого бы то ни было числа может быть только натуральное число $d$, делящее $p-1$. Допустим найдётся какое-то число $a$, имеющее данный показатель $d$. Тогда каждое из чисел $a^0,a^1,\ldots ,a^{d-1}$ является решением сравнения $x^d-1\equiv 0\pmod{p}$, которое не может иметь более $d$ решений по теореме Лагранжа. С другой стороны, по аналогичным с доказательством следствия 13 рассуждениям все эти числа попарно не сравнимы по модулю $p$, а значит это все решения указанного сравнения и только среди них могут присутствовать числа, имеющие показатель $d$. Но если $(k,d)=s$, то $(a^k)^{d/s}\equiv 1\pmod{p}$, поэтому показатель $d$ могут иметь только такие числа $a^k$, для которых $(k,d)=1$, а таких чисел всего $\varphi(d)$. Следовательно, показатель $d$ могут иметь не более чем $\varphi(d)$ некоторых чисел. Если мы обозначим за $\chi(d)$ количество чисел, имеющих по модулю $p$ показатель $d$, то можно записать $$0\leqslant\chi(d)\leqslant\varphi(d).$$ Поскольку каждое из чисел $1,2,\ldots ,p-1$ имеет некоторый показатель, то будем иметь $$\sum_{d|p-1}\chi(d)=p-1.$$ Но для функции Эйлера мы также выводили соотношение $$\sum_{d|p-1}\varphi(d)=p-1.$$ Из этих двух тождеств и выписанного чуть выше неравенства следует, что для каждого $d$, делящего $p-1$, выполнено $\chi(d)=\varphi(d)$, в том числе и $\chi(p-1)=\varphi(p-1)$, то есть существуют числа, имеющие показателем $p-1$. По определению это и означает, что существуют первообразные корни по модулю $p$. Причём их найдётся ровно $\varphi(p-1)$ штук (не сравнимых друг с другом по модулю $p$).

По предыдущему параграфу существует первообразный корень по модулю $2$. Им является, например, число $1$.

По модулю $2^2$ также можно предъявить первообразный корень, скажем $3$.

По модулю же $2^3$ не может существовать первообразный корень, так как мы видели, что любое нечётное число $a$ удовлетворяет сравнению $a^2\equiv 1\pmod{8}$.

Покажем индукцией по $k$, что для любого $k\geqslant 3$ и нечётного $a$ будет выполнено $$a^{2^{k-2}}\equiv 1\pmod{2^k},$$ то есть при таких $k$ по модулю $2^k$ первообразных корней нет. Действительно, при $k=3$ это верно. Если это верно при некотором $k\geqslant 3$, то можно записать $$a^{2^{k-1}}-1=(a^{2^{k-2}}-1)(a^{2^{k-2}}+1).$$ По предположению индукции первая из скобок в получившемся произведении делится на $2^k$, а вторая делится на $2$. Тогда всё произведение делится на $2^{k+1}$ и требуемое сравнение выполняется для $k+1$. Доказательство завершено.

Пусть $m=p_1^{k_1}\cdots p_s^{k_s}$. Покажем, что при $N=[\varphi(p_1^{k_1}),\ldots,\varphi(p_s^{k_s})]$ будем иметь $a^N\equiv 1\pmod{m}$ для любого взаимно простого с $m$ числа $a$. Действительно, число $a$ будет также взаимно просто с каждым из чисел $p_i^{k_i}$ и по теореме Эйлера будем иметь $a^{\varphi(p_i^{k_i})}\equiv 1\pmod{p_i^{k_i}}$. А так как $\varphi(p_i^{k_i})|N$, то для каждого $i=1,\ldots,s$ будет выполнено $a^N\equiv 1\pmod{p_i^{k_i}}$. По китайской теореме об остатках из этой системы сравнений будет следовать $a^N\equiv 1\pmod{p_1^{k_1}\cdots p_s^{k_s}}$, что и требовалось.

Заметим, что когда $m=p_1^{k_1}\cdots p_s^{k_s}$ не имеет вид $2^k,\ p^{k}$ или $2p^{k}$ с нечётным простым $p$, то среди чисел, от которых берётся наименьшее общее кратное, обязательно будет несколько чётных чисел, и $$N=[\varphi(p_1^{k_1}),\ldots,\varphi(p_s^{k_s})]<\varphi(p_1^{k_1})\cdots\varphi(p_s^{k_s})=\varphi(m),$$ а это означает что по модулю $m$ не может быть первообразных корней. При этом отсутствие первообразных корней по модулю $2^k$, где $k>2$, уже показано.

При $k=1$ существование первообразного корня нами уже показано.

Теорема 9. Пусть $g$ – первообразный корень по модулю нечётного простого числа $p$. Если $g^{p-1}\not\equiv 1\pmod{p^2}$, то $g$ будет первообразным корнем по модулю $p^k$ при любом натуральном $k$.

Доказательство. Покажем индукцией по $k$, что $g^{p^{k-1}(p-1)}\not\equiv 1\pmod{p^{k+1}}$ и что $g$ будет первообразным корнем по модулю $p^k$. По условию теоремы оба эти утверждения выполняются при $k=1$. Пусть они выполняются для некоторого $k$. Покажем, что будут они выполнены и для $k+1$.

Поскольку $g^{p^{k-1}(p-1)}\not\equiv 1\pmod{p^{k+1}}$, но по теореме Эйлера $g^{p^{k-1}(p-1)}\equiv 1\pmod{p^{k}}$, то можно записать $g^{p^{k-1}(p-1)}=1+cp^{k}$, где $c$ не делится на $p$. Возведём обе части полученного равенства в степень $p$ и, применив формулу бинома Ньютона, увидим, что $g^{p^{k}(p-1)}=1+cp^{k+1}+c_1p^{k+2}$, откуда $g^{p^{k}(p-1)}\not\equiv 1\pmod{p^{k+2}}$.

Пусть теперь $g$ не первообразный корень по модулю $p^{k+1}$. Тогда найдётся $d$, меньшее чем $\varphi(p^{k+1})$, такое что $g^d\equiv 1\pmod{p^{k+1}}$. По предложению 5 число $d$ является делителем $\varphi(p^{k+1})=p^{k}(p-1)$. Но так как $g$ – первообразный корень по модулю $p^{k}$, то $d\geqslant\varphi(p^{k})=p^{k-1}(p-1)$, а из того, что $g^{p^{k-1}(p-1)}\not\equiv 1\pmod{p^{k+1}}$ следует $d\neq p^{k-1}(p-1)$. Значит $d=p^kd'$, где $d'|p-1,\ d'<p-1$. Так как $g^d\equiv 1\pmod{p^{k+1}}$, то и $g^d\equiv 1\pmod{p}$. Получаем $$g^d=(g^{p^k})^{d'}\equiv g^{d'}\equiv 1\pmod{p}.$$ Это противоречит тому, что $g$ – первообразный корень по модулю $p$, поскольку $d'<p-1$. При этом тот факт, что $g^{p^k}\equiv g\pmod{p}$ следует из $k$-кратного применения теоремы Ферма. Теорема 9 доказана.

Покажем как найти первообразный корень, удовлетворяющий условию теоремы 9. Если выбрать произвольный первообразный корень $g$ по модулю $p$, то либо $g^{p-1}\not\equiv 1\pmod{p^2}$, и тогда $g$ удовлетворяет всем условиям теоремы, либо $g^{p-1}\equiv 1\pmod{p^2}$, но тогда рассмотрим число $g_1=g+p$. Очевидно, что это также будет первообразный корень по модулю $p$. Однако по формуле бинома Ньютона $$g_1^{p-1}=(g+p)^{p-1}=g^{p-1}+(p-1)pg^{p-2}+cp^2$$ с некоторым числом $c$. Тогда $g_1^{p-1}\equiv 1-pg^{p-2}\not\equiv 1\pmod{p^2}$, так как $p$ не делит первообразный корень $g$. Таким образом, достаточно взять произвольный первообразный корень $g$ по модулю $p$ и если $g^{p-1}\not\equiv 1\pmod{p^2}$, то $g$ удовлетворяет всем условиям теоремы 9, а иначе $g+p$ удовлетворяет всем условиям теоремы 9.

Теорема 10. Пусть $g$ – первообразный корень по модулю $p^k$ для некоторого нечётного простого числа $p$. Если $g$ нечётное число, то $g$ будет первообразным корнем по модулю $2p^k$.

Доказательство. Так как $g$ нечётное число, то оно взаимно просто с $2p^k$. Если оно не первообразный корень по этому модулю, то существует натуральное число $d$, меньшее чем $\varphi(2p^{k})=p^{k-1}(p-1)$, такое что $g^d\equiv 1\pmod{2p^{k}}$. Но тогда и $g^d\equiv 1\pmod{p^{k}}$. Это противоречит тому, что $g$ – первообразный корень по модулю $p^k$, поскольку $d<p^{k-1}(p-1)=\varphi(p^{k})$. Теорема 10 доказана.

Как видно из теорем 9 и 10, если $g$ – первообразный корень по модулю $p^2$, то это же число будет первообразным корнем и по модулю $p^k$ при любом натуральном $k$, а если $g$ нечётно, то и по модулю $2p^k$. При этом, если $g$ – чётное число, то $g+p^2$ будет уже нечётным и при этом останется первообразным корнем по модулю $p^2$.

Таким образом, чтобы для нечётного простого числа $p$ предъявить первообразный корень по модулю $2p^k$, нужно найти первообразный корень $g$ по модулю $p^2$, и если $g$ нечётно, то это и есть искомый первообразный корень, а иначе это будет $g+p^2$.

Теорема 11. Пусть $m$ натуральное число и $g$ целое, взаимно простое с $m$ число. Пусть $\varphi(m)=q_1^{k_1}\cdots q_s^{k_s}$ – разложение на простые множители. Тогда, если для каждого $i=1,\ldots ,s$ выполнено $g^{\varphi(m)/q_i}\not\equiv 1\pmod{m}$, то $g$ – первообразный корень по модулю $m$.

Доказательство. Если $g$ – не первообразный корень по модулю $m$, то найдётся натуральное число $d$, меньшее чем $\varphi(m)$, такое что $g^d\equiv 1\pmod{m}$. По предложению 5 $d|\varphi(m)$, а значит $d=q_1^{n_1}\cdots q_s^{n_s}$, где $0\leqslant n_i\leqslant k_i$ при всех $i=1,\ldots ,s$, причём при некотором $j$ будет $n_j\leqslant k_j-1$. Но тогда $d|\varphi(m)/q_j$ и $g^{\varphi(m)/q_j}\equiv 1\pmod{m}$. Противоречие. Теорема 11 доказана.

Отыскивать первообразные корни с помощью теоремы 11 рекомендуется только по простому модулю $p$, после чего разумнее находить (если это требуется) первообразные корни по модулям $p^{k}$ и $2p^{k}$, пользуясь процедурами, описанными в предыдущем параграфе.

Итак, требуется

• разложить на простые множители число $p-1=2^kq_1^{k_1}\cdots q_s^{k_s}$
• выбрать какое-нибудь число $g$ (кандидата в первообразные корни), причём необходимо $p\nmid g$
• убедиться, что символ Лежандра $\displaystyle\left(\frac{g}{p}\right)=-1$
• проверять, выполняется ли условие $g^{p-1/q_i}\not\equiv 1\pmod{p}$ для каждого $i=1,\ldots ,s$

Если все проверки пройдены успешно, то $g$ – первообразный корень по модулю $p$.

Условие $\displaystyle\left(\frac{g}{p}\right)=-1$ является проверкой эквивалентного ему условия $g^{p-1/2}\not\equiv 1\pmod{p}$. Дело в том, что по критерию Эйлера $g^{p-1/2}\equiv \displaystyle\left(\frac{g}{p}\right)\pmod{p}$, а ненулевой символ Лежандра, если он не сравним с $1$, должен равняться $-1$.

В качестве первого кандидата имеет смысл брать $g=2$. Нет необходимости рассматривать заведомые квадратичные вычеты, например $4$ или вообще какие бы то ни было квадраты. Число $-1$ является первообразным корнем по модулям $2,\ 3,\ 4,\ 6$ и ни по каким другим модулям его рассматривать не нужно, поскольку $(-1)^2\equiv 1\pmod{m}$ при любом $m$.

Пример 6. Найти первообразный корень по модулю $31$.

Решение. Разложим на простые множители $31-1=2\cdot 3\cdot 5$. Не будем брать в качестве кандидата число $2$, так как $31\equiv -1\pmod{8}$ и $\displaystyle\left(\frac{2}{31}\right)=1$. Зато $\displaystyle\left(\frac{-2}{31}\right)=-1$. Но $(-2)^{30/3}=(-2)^{10}=(-32)^2\equiv 1\pmod{31}$.

Возьмём $3$ в качестве кандидата. Имеем $$\left(\frac{3}{31}\right)=-\left(\frac{31}{3}\right)=-1.$$ Кроме того $$3^{30/3}=(3^3)^3\cdot 3\equiv (-4)^3\cdot 3\equiv -64\cdot 3\equiv -6\not\equiv 1\pmod{31}$$ и $$ 3^{30/5}=(3^3)^2\equiv (-4)^2\equiv 16\not\equiv 1\pmod{31}.$$ Значит $3$ – первообразный корень по модулю $31$.

Пример 7. Найти первообразный корень по модулю $1637$.

Решение. Разложим на простые множители $1637-1=2^2\cdot 409$. Возьмём 2 в качестве кандидата. Так как $1637\equiv 5\pmod{8}$, то $\displaystyle\left(\frac{2}{1637}\right)=-1$. Кроме того $2^{1636/409}=16\not\equiv 1\pmod{1637}$. Значит $2$ – первообразный корень по модулю $1637$.

Пример 8. Найти первообразный корень по модулю $2\cdot 23^{19}$.

Решение. Достаточно найти нечётный первообразный корень по модулю $23^2$. Для начала найдём первообразный корень по модулю $23$. Разложим на простые множители $23-1=2\cdot 11$. Не будем брать в качестве кандидата число $2$, так как $23\equiv -1\pmod{8}$ и $\displaystyle\left(\frac{2}{23}\right)=1$. Зато $\displaystyle\left(\frac{-2}{23}\right)=-1$. Кроме того $(-2)^{22/11}=4\not\equiv 1\pmod{23}$. Значит $-2$ – первообразный корень по модулю $23$.

Теперь проверим, что $(-2)^{22}\not\equiv 1\pmod{23^2}$. Это действительно так, поскольку $$(-2)^{22}-1=2^{22}-1=(2^{11}-1)(2^{11}+1)=2047\cdot 2049,$$ но $2047=23\cdot 89$, а значит, во-первых, $23$ не делит $2049$, а во-вторых, $23^2$ не делит $(-2)^{22}-1$. Это означает, что $-2$ является первообразным корнем и по модулю $23^2$. Но тогда число $23^2-2=527$ будет нечётным первообразным корнем по модулю $23^2$, а значит и по модулю $2\cdot 23^{19}$.

Пользуясь следствием 13 можно решать сравнения некоторого вида. Допустим необходимо найти все решения сравнения $$x^{17}\equiv 5\pmod{31}.$$ Мы знаем, что $3$ – первообразный корень по модулю $31$. Все его степени от нулевой до двадцать девятой образуют приведённую систему вычетов по модулю $31$ (всего в ней $\varphi(31)=30$ элементов). Находим $3^5=243\equiv -5\pmod{31}$, следовательно $5\equiv 3^{20}\pmod{31}$.

Это связано с тем, что для любого первообразного корня $g$ по любому простому модулю $p$ выполнено $-1\equiv g^{p-1/2}$. В этом легко убедиться, ведь для первообразного корня всегда выполнено $\displaystyle\left(\frac{g}{p}\right)=-1$, а $\displaystyle\left(\frac{g}{p}\right)\equiv g^{p-1/2}\pmod{p}$ по критерию Эйлера. При этом ни в какой другой степени от $0$ до $p-2$ первообразный корень не даст $-1$, поскольку по следствию 13 все его степени попарно не сравнимы по модулю $p$.

Положим теперь $x\equiv 3^y\pmod{31}$. Мы можем это сделать, так как из самого условия задачи очевидно, что $x$ не делится на $31$, а значит сравним с одной (и только одной) из степеней первообразного корня (по следствию 13). Исходное сравнение теперь перепишется в виде $$ 3^{17y}\equiv 3^{20}\pmod{31}.$$ По следствию 12 это равносильно сравнению уже по модулю $\varphi(31)=30$ $$17y\equiv 20\pmod{30}.$$ Решая это сравнение, находим $y\equiv 10\pmod{30}$, откуда $x\equiv 3^y\equiv -6\pmod{31}$.