1.2 Теоремы сравнения

В предыдущем пункте было отмечено, что отношение є _m сравнимости по произвольному модулю m есть отношение эквивалентности на множестве целых чисел. Это отношение эквивалентности индуцирует разбиение множества целых чисел на классы эквивалентных между собой элементов, т.е. в один класс объединяются числа, дающие при делении на m одинаковые остатки. Число классов эквивалентности є _m(знатоки скажут - "индекс эквивалентности є _m ") в точности равно m.

Определение. Любое число из класса эквивалентности є _m будем называть вычетом по модулю m. Совокупность вычетов, взятых по одному из каждого класса эквивалентности є _m, называется полной системой вычетов по модулю m (в полной системе вычетов, таким образом, всего m штук чисел). Непосредственно сами остатки при делении на m называются наименьшими неотрицательными вычетами и, конечно, образуют полную систему вычетов по модулю m. Вычет r называется абсолютно наименьшим, если пrп наименьший среди модулей вычетов данного класса.

Пример: Пусть m = 5. Тогда:

0, 1, 2, 3, 4 - наименьшие неотрицательные вычеты;

-2, -1, 0, 1, 2 - абсолютно наименьшие вычеты.

Обе приведенные совокупности чисел образуют полные системы вычетов по модулю 5.

Лемма 1. 

1. Любые m штук попарно не сравнимых по модулю m чисел образуют полную систему вычетов по модулю m.

2. Если а и m взаимно просты, а x пробегает полную систему вычетов по модулю m, то значения линейной формы аx+b, где b — любое целое число, тоже пробегают полную систему вычетов по модулю m.

Доказательство. 

Утверждение 1 – очевидно.

Докажем утверждение 2.

Чисел аx+b ровно m штук. Покажем, что они между собой не сравнимы по модулю m. Ну пусть для некоторых различных x ₁ и x ₂ из полной системы вычетов оказалось, что ax ₁ +b є ax ₂ +b(mod m). Тогда, по свойствам сравнений из предыдущего пункта, получаем:

ax ₁ є ax ₂ (mod m)

x ₁ є x ₂ (mod m) – противоречие с тем, что x ₁ и x ₂ различны и взяты из полной системы вычетов.

Поскольку все числа из данного класса эквивалентности є получаются из одного числа данного класса прибавлением числа, кратного m, то все числа из данного класса имеют с модулем m один и тот же наибольший общий делитель. По некоторым соображениям, повышенный интерес представляют те вычеты, которые имеют с модулем m наибольший общий делитель, равный единице, т.е. вычеты, которые взаимно просты с модулем.

Определение. Приведенной системой вычетов по модулю m называется совокупность всех вычетов из полной системы, взаимно простых с модулем m.

Приведенную систему обычно выбирают из наименьших неотрицательных вычетов. Ясно, что приведенная система вычетов по модулю m содержит φ (m) штук вычетов, где φ (m) — функция Эйлера – число чисел, меньших m и взаимно простых с m. Если к этому моменту вы уже забыли функцию Эйлера, загляните в пункт 14 и убедитесь, что про нее там кое-что говорилось.

Пример. Пусть m = 42. Тогда приведенная система вычетов суть:

1, 5, 11, 13, 17, 19, 23, 25, 29, 31, 37, 41.

Лемма 2. 

1. Любые φ (m) чисел, попарно не сравнимые по модулю m и взаимно простые с модулем, образуют приведенную систему вычетов по модулю m.

2. Если (a,m) = 1 и x пробегает приведенную систему вычетов по модулю m, то аx так же пробегает приведенную систему вычетов по модулю m.

Доказательство. 

Утверждение 1 – очевидно.

Докажем утверждение 2.

Числа аx попарно несравнимы (это доказывается так же, как в лемме 1 этого пункта), их ровно φ (m) штук. Ясно также, что все они взаимно просты с модулем, ибо (a,m)=1, (x,m)=1 (ax.m)=1. Значит, числа аx образуют приведенную систему вычетов.

Лемма 3. Пусть m ₁, m ₂,..., m _k — попарно взаимно просты и m ₁ m ₂...m _k =M ₁ m ₁ =M ₂ m ₂ =...=M _k m _k, где M _φ =m ₁...m _φ-1 m _φ+1...m_k

1. Если x ₁, x ₂,..., x _k пробегают полные системы вычетов по модулям m ₁, m ₂,..., m _k соответственно, то значения линейной формы M ₁x ₁ +M ₂ x ₂ +...+M _k x _k пробегают полную систему вычетов по модулю m=m ₁ m ₂...m _k.

2. Если ξ ₁, ξ ₂,..., ξ _k пробегают приведенные системы вычетов по модулям m ₁, m ₂,..., m _k соответственно, то значения линейной формы M ₁ ξ ₁ +M ₂ ξ ₂ +...+M _k ξ _k пробегают приведенную систему вычетов по модулю m=m ₁ m ₂...m _k.

Доказательство.

1. Форма  M ₁ x ₁ +M ₂ x ₂ +...+M _k x _k  принимает,  m ₁ m ₂...m _k =m значений. Покажем, что эти значения попарно несравнимы.

M ₁ x ₁ +M ₂ x ₂ +...+M _k x _k   є M ₁ x ₁ ^∆ +M ₂ x ₂ ^∆ +...+M _k x _k ^∆ (mod m)

Всякое M _φ, отличное от M _s, кратно m _s. Убирая слева и справа в последнем сравнении слагаемые, кратные m _s, получим:

M _s x _s   є M _s x _s ^∆ (mod m _s)  x _s   є x _s ^∆ (mod m _s) — противоречие с тем, что x _s пробегает полную систему вычетов по модулю m _s.

2. Форма  M ₁ ξ ₁ +M ₂ ξ ₂ +...+M _k ξ _k  принимает, очевидно, φ (m ₁) φ (m ₂) • ... • φ (m _k) = φ (m ₁ m ₂ • ... • m _k)= φ (m) (функция Эйлера мультипликативна!) различных значений, которые между собой по модулю m=m ₁ m ₂...m _k попарно несравнимы. Последнее легко доказывается рассуждениями, аналогичными рассуждениям, проведенным при доказательстве утверждения 1 этой леммы. Так как (M ₁ ξ ₁+M ₂ ξ ₂ +...+M _k ξ _k,m _s)=(M _s ξ _s,m _s)=1 для каждого  1 ≤ s ≤ k, то (M ₁ ξ ₁ +M ₂ ξ ₂ +...+M _k ξ _k,m _s)=1, следовательно множество значений формы M ₁ ξ ₁ +M ₂ ξ ₂ +...+M _k ξ _k образует приведенную систему вычетов по модулю m.

Лемма 4. Пусть x ₁, x ₂,..., x _k,x пробегают полные, а ξ ₁, ξ ₂,..., ξ _k, ξ – пробегают приведенные системы вычетов по модулям m ₁, m ₂,..., m _k и m=m ₁ m ₂...m _k соответственно, где (m _i m _j)=1 при i ≠ j. Тогда дроби {x ₁ /m ₁ +x ₂ /m ₂ +...+x _k /m _k} совпадают с дробями {x/m}, а дроби { ξ ₁ /m ₁ + ξ ₂ /m ₂ +...+ ξ _k /m _k } совпадают с дробями {ξ/m}.

Доказательство. Доказательство обоих утверждений леммы 4 легко получается применением предыдущей леммы 3 после того, как вы приведете каждую сумму {x ₁ /m ₁ +x ₂ /m ₂ +...+x _k /m _k }  и { ξ ₁ /m ₁ + ξ ₂ /m ₂ +...+ ξ _k /m _k }  к общему знаменателю:

{x ₁ /m ₁ +x ₂ /m ₂ +...+x _k /m _k }={(M ₁ x ₁ +M ₂ x ₂ +...+M _k x _k)/m} ;

{ ξ ₁ /m ₁ + ξ ₂ /m ₂ +...+ ξ _k /m _k }={(M ₁ ξ ₁ +M ₂ ξ ₂ +...+M _k ξ _k)/m},

где M_j =m ₁...m_j-1 m_j+1...m _k.

Если теперь принять во внимание, что дробные части чисел, получающихся при делении на модуль m любых двух чисел, сравнимых по модулю m, одинаковы (они равны r/m, где r — наименьший неотрицательный вычет из данного класса), то утверждения настоящей леммы становятся очевидными.

Обозначим через ɛ _k k -ый корень m- ой степени из единицы:

— эти формы записи комплексных чисел мы хорошо помним с первого курса. Здесь k=0,1,...,m-1 — пробегает полную систему вычетов по модулю m.

Напомню, что сумма ɛ ₀ + ɛ ₁ +...+ ɛ _m-1 всех корней m-ой степени из единицы равна нулю для любого m. Действительно, пусть ɛ ₀+ ɛ ₁ +...+ ɛ _m-1 =a. Умножим эту сумму на ненулевое число ɛ ₁. Такое умножение геометрически в комплексной плоскости означает поворот правильного m-угольника, в вершинах которого расположены корни ɛ ₀, ɛ ₁,..., ɛ _m-1, на ненулевой угол 2 π/m. Ясно, что при этом корень ɛ ₀ перейдет в корень ɛ ₁, корень ɛ ₁ перейдет в корень ɛ ₂, и т.д., а корень ɛ _m-1 перейдет в корень ɛ₀, т.е. сумма ɛ ₀+ ɛ ₁ +...+ ɛ _m-1 не изменится. Имеем ɛ ₁ a=a, откуда a=0.

Теорема 1. Пусть m>0 — целое число, a ϵ Z, x пробегает полную систему вычетов по модулю m. Тогда, если а кратно m, то

в противном случае, при а не кратном m,

.

Доказательство. 

При а кратном m имеем: a=md и .

При а не делящемся на m, разделим числитель и знаменатель дроби a/m на d – наибольший общий делитель а и m, получим несократимую дробь a ₁ /m ₁. Тогда, по лемме 1, a ₁ x будет пробегать полную систему вычетов по модулю m. Имеем:

ибо сумма всех корней степени m ₁ из единицы равна нулю.

Напомню, что корень ɛ _k m -ой степени из единицы называется первообразным, если его индекс k взаимно прост с m. В этом случае, как доказывалось на первом курсе, последовательные степени ɛ_k ¹, ɛ_k ²,..., ɛ_k ^m-1  корня ɛ _k образуют всю совокупность корней m-ой степени из единицы или, другими словами, ɛ _k является порождающим элементом циклической группы всех корней m-ой степени из единицы.

Очевидно, что число различных первообразных корней m -ой степени из единицы равно  φ (m), где φ  — функция Эйлера, так как индексы у первообразных корней образуют приведенную систему вычетов по модулю m.

Теорема 2. Пусть m>0 – целое число, ξ пробегает приведенную систему вычетов по модулю m. Тогда (сумма первообразных корней степени m):

где μ (m) — функция Мебиуса.

Доказательство. Пусть m=p ₁ ^α ₁ p ₂ ^α₂...p _k ^α _k – каноническое разложение числа m ; m ₁ =p ₁ ^α ₁, m ₂ =p ₂ ^α ₂, m ₃ =p ₃ ^α ₃ ; ξ_i пробегает приведенную систему вычетов по модулю m_i. Имеем:

При α_s =1 получается, что только корень ɛ ₀ =1 не является первообразным, поэтому сумма всех первообразных корней есть сумма всех корней минус единица:

стало быть, если m свободно от квадратов (т.е. не делится на r ², при r >1), то

Если же какой-нибудь показатель α _s больше единицы (т.е. m делится на r ², при r>1), то сумма всех первообразных корней степени m_s есть сумма всех корней степени m_s минус сумма всех не первообразных корней, т.е. всех корней некоторой степени, меньшей m_s. Именно, если m_s = p_s m_s ^*, то:

Теорема (Эйлер). 

Пусть m>1, (a,m)=1, φ (m) — функция Эйлера. Тогда:

a ^φ (m) = 1(mod m).

Доказательство. Пусть х пробегает приведенную систему вычетов по mod m:

x=r₁,r₂,...,r_c, где c= φ (m) их число, r ₁,r ₂,..., r _c — наименьшие неотрицательные вычеты по mod m. Следовательно, наименьшие неотрицательные вычеты, соответствующие числам ax суть соответственно:

р₁, р₂,..., р_c — тоже пробегают приведенную систему вычетов, но в другом порядке.

Значит:

a • r ₁ ≡ р_φ 1 (mod m)

a • r ₂ ≡ р_φ 2 (mod m)

...

a • r _c ≡ р_φ χ (mod m)

Перемножим эти с штук сравнений. Получится:

a ^c r ₁ r ₂...r _c ≡ r _φ 1 r _φ 2... r _φ c (mod m)

Так как r ₁ r ₂...r _c = р ₁ р ₂... р _c ≠ 0 и взаимно просто с модулем m, то, поделив последнее сравнение на r ₁ r ₂...r _c, получим a ^φ (m) ≡ 1(mod m).

Вторая теорема этого пункта — теорема Ферма — является непосредственным следствием теоремы Эйлера.

Теорема (Ферма). 

Пусть р — простое число, р не делит a. Тогда:

a ^p-1 ≡ 1(mod p).

Доказательство 1. 

Положим в условии теоремы Эйлера m=p, тогда φ (m)=p-1. Получаем a ^p-1 ≡ 1(mod p).

Необходимо отметить важность условия взаимной простоты модуля и числа a в формулировках теорем Эйлера и Ферма. Простой пример: сравнение 6 ² ≡ 1(mod 3) очевидно не выполняется. Однако можно легко подправить формулировку теоремы Ферма, чтобы снять ограничение взаимной простоты.

Следствие 1. 

Без всяких ограничений на a ϵ Z,

a ^p ≡ a(mod p).

Доказательство. 

Умножим обе части сравнения a ^p-1 ≡ 1(mod p) на a. Ясно, что получится сравнение, справедливое и при a, кратном р.

Доказательство 2. 

Так как р — простое число, то все биномиальные коэффициенты: (кроме C ₀ ^p и C _p ^p) делятся на р, ибо числитель выписанного выражения содержит р, а знаменатель не содержит этого множителя.

Если вспомнить бином Ньютона, то становится понятно, что разность (A+B) ^p -A ^p -B ^p =C _p ¹ A ^p-1 B ¹ +C _p ² A ^p-2 B ² +...+C _p ^p-2 A ²B ^p-2 +C _p ^p-1 A ¹ B ^p-1, где А и В – какие угодно целые числа, всегда делится на р. Последовательным применением этого наблюдения получаем, что (A+B+C) ^p -A ^p -B ^p -C ^p ={[(A+B)+C] ^p -(A+B) ^p -C ^p}+(A+B) ^p -A ^p -B ^p всегда делится на р ;(A+B+C+D) ^p -A ^p -B ^p -C ^p -D ^p всегда делится на р ; и вообще, (A+B+C+...+K) ^p -A ^p -B ^p -C ^p -...-K ^p всегда делится на р. Положим теперь в последнем выражении A=B=C=...=K=1 и возьмем количество этих чисел равным a. Получится, что a ^p -a делится на р, а это и есть теорема Ферма в более общей формулировке.

Следствие 2. (a+b) ^p є a ^p +b ^p (mod p).

Эффективность применения теорем Ферма и Эйлера отчасти основывается на том, что сравнения, даваемые этими теоремами, удобно возводить в степень, так как справа в них стоит единица, которая на возведение в степень не реагирует.

В этом пункте мы рассмотрим сравнения вида f(x) ≡ 0(mod p), где р — простое число, f(x)=ax ⁿ +a ₁ x ^n-1 +…+a _n  — многочлен с целыми коэффициентами, и попытаемся научиться решать такие сравнения.

Лемма 1. Произвольное сравнение f(x) ≡ 0(mod p), где р - простое число, равносильно некоторому сравнению степени не выше p-1.

Доказательство. Разделим f(x) на многочлен x ^p -x (такой многочлен алгебраисты иногда называют «многочлен деления круга») с остатком: f(x)=(x ^p -x) • Q(x)+R(x), где, как известно, степень остатка R(x) не превосходит р-1. Но ведь, по теореме Ферма, x ^p -x ≡ 0(mod p). Это означает, что f(x) ≡ R(x)(mod p), а исходное сравнение равносильно сравнению R(x) ≡ 0(mod p).

Лемма 2. Если сравнение ax ⁿ +a ₁ x ^n-1 +…+a _n ≡ 0(mod p) степени n по простому модулю р имеет более n различных решений, то все коэффициенты a,a ₁,…,a _n кратны р.

Доказательство. Пусть сравнение ax ⁿ +a ₁ x ^n-1 +…+a _n ≡ 0(mod p), имеет n+1 решение и x ₁,x ₂,…,x _n,x _n+1 — наименьшие неотрицательные вычеты этих решений. Тогда, очевидно, многочлен f(x) представим в виде:

f(x)=a(x-x 1)(x-x 2)…(x-x n -2)(x-x n-1)(x-x n)+ +b(x-x 1)(x-x 2)…(x-x n -2)(x-x n-1)+ +c(x-x 1)(x-x 2)…(x-x n -2)+ +…+ +k(x-x 1)(x-x 2)+ +l(x-x 1)+ +m.

Действительно, коэффициент b нужно взять равным коэффициенту при x ^n-1 в разности f(x)-a(x-x ₁)(x-x ₂)…(x-x _n); коэффициент  с  — это коэффициент перед x ^n-2 в разности f(x)-a(x-x ₁)(x-x ₂)…(x-x _n)- b(x-x ₁)(x-x ₂)…(x-x _n-1), и т.д.

Теперь положим последовательно x=x ₁,x ₂,…,x _n,x _n+1. Имеем:

1. f(x ₁)=m ≡ 0(mod p), следовательно, р делит m.

2. f(x ₂)=m+l(x ₂ -x ₁) ≡ l(x ₂ -x ₁) ≡ 0(mod p), следовательно, р делит l, ибо р не может делить x ₂ -x ₁, так как x ₂ <p, x ₁ <p.

3. f(x ₃) ≡ k(x ₃ -x ₁)(x ₃ -x ₂) ≡ 0(mod p), следовательно, р делит k и т.д.

Получается, что все коэффициенты a, b, c,...,k, l кратны р. Это означает, что все коэффициенты a,a ₁,…,a _n тоже кратны р, ведь они являются суммами чисел, кратных р.

Подведем итог. Всякое нетривиальное сравнение по mod p равносильно сравнению степени не выше p-1 и имеет не более p-1решений.

Теорема (Вильсон). Сравнение, (p-1)!+1 ≡0(mod p) выполняется тогда и только тогда, когда р — простое число.

Доказательство. Пусть р  — простое число. Если р=2, то, очевидно, 1!+1 ≡ 0(mod 2). Если р>2, то рассмотрим сравнение:

[(x-1)(x-2)…(x-(p-1))]-(x ^p-1 -1) ≡ 0(mod p).

Ясно, что это сравнение степени не выше р-2, но оно имеет р-1 решение: 1, 2, 3,..., р-1, т.к. при подстановке любого из этих чисел, слагаемое в квадратных скобках обращается в ноль, а (x ^p-1) сравнимо с нулем по теореме Ферма (х и р взаимно просты, т.к. х<р). Это означает, по лемме 2, что все коэффициенты выписанного сравнения кратны р, в частности, на р делится его свободный член, равный 1 • 2 • 3 • ... • (р–1)+1.

Так как коэффициенты многочлена являются значениями симметрических многочленов от его корней, то здесь наметился путь для доказательства огромного числа сравнений для симметрических многочленов.

Если р — не простое, то найдется делитель d числа р, 1<d<p. Тогда (р–1)! делится на d, поэтому (р–1)!+1 не может делиться на d и, значит, не может делиться также и на р. Следовательно, сравнение, (p-1)!+1 ≡ 0(mod 2) не выполняется.

Теорема 1. Если числа m ₁, m ₂,… m _k попарно взаимно просты, то сравнение f (x) ≡ 0(mod m ₁ m ₂ … m _k) равносильно системе сравнений:

При этом, если Т₁, Т₂,..., Т_к  — числа решений отдельных сравнений этой системы по соответствующим модулям, то число решений Т исходного сравнения равно Т₁ Т₂...Т_к.

Доказательство. Первое утверждение теоремы (о равносильности системы и сравнения) очевидно, т.к. если a ≡ b (mod m), то a ≡ b (mod d), где d делит m. Если же a ≡ b (mod m₁) и a ≡ b (mod m₂), то a ≡ b (mod HOK (m₁, m₂)), где НОК (m₁,  m₂) — наименьшее общее кратное m₁ и m₂.

Каждое сравнение f (x) ≡ 0(mod m_s) выполняется тогда и только тогда, когда выполняется одно из T _s штук сравнений вида x є b _s (mod m_s), где b _s пробегает вычеты решений сравнения f (x) є 0(mod m _s). Всего различных комбинаций таких простейших сравнений Т ₁ Т ₂...Т _к штук. Все эти комбинации приводят к различным классам вычетов по mod(m ₁ m ₂ … m _k).

Итак, решение сравнения   сводится к решению сравнений вида f (x) ≡ 0(mod p ^a). Оказывается, что решение этого последнего сравнения, в свою очередь, сводится к решению некоторого сравнения g (x) ≡ 0(mod p) c другим многочленом в левой части, но уже с простым модулем, а это, просто напросто, приводит нас в рамки предыдущего пункта.

Процесс сведения.

Очевидно, выполнение сравнения f (x) ≡ 0(mod p ^a) влечет, что х подходит в сравнение f (x) ≡ 0(mod p). Пусть x ≡ x ₁ (mod p) — какое-нибудь решение сравнения f (x) ≡ 0(mod p). Это означает, что x = x ₁ + p • t ₁, где t ₁ ϵ Z.

Вставим это х в сравнение f (x) ≡ 0(mod p ²). Получим сравнение f (x ₁ + p • t ₁) ≡ 0(mod p ²), которое тоже, очевидно, выполняется.

Разложим далее левую часть полученного сравнения по формуле Тейлора по степеням (х - х ₁):

Но, ведь, x = x ₁ + p • t ₁, следовательно,

.

Заметим, что число f ^(k) (x ₁)/ k! всегда целое, т.к. f (x ₁ + p • t ₁) — многочлен с целыми коэффициентами. Теперь в сравнении f (x ₁ + p • t ₁) ≡ 0(mod p ²) можно слева отбросить члены, кратные р ² :

.

Разделим последнее сравнение и его модуль на р:

.

Заметим, опять, что f (x ₁)/ p  — целое число, т.к. f (x ₁) є 0(mod p). Далее ограничимся случаем, когда значение производной f ´ (x ₁) не делится на р. В этом случае имеется всего одно решение сравнения первой степени

 относительно t₁:

t ₁ ≡ t ₁   (mod p).

Это, опять-таки, означает, что t ₁ = t ₁   + p • t ₂, где t ₂ ϵ Z, и

.

Снова вставим это x = x ₂ + p ² t ₂ в сравнение f (x) ≡ 0(mod p ³) (но теперь это сравнение уже по mod p ³, разложим его левую часть по формуле Тейлора по степеням (х-х ₂) и отбросим члены, кратные p ³:

f (x ₂) +(f ´ (x ₂)/1!) • p ² t ₂ ≡ 0(mod p ³).

Делим это сравнение и его модуль на р ² :

f (x ₂)/ p ² + f ´ (x ₂) • t ₂ ≡ 0(mod p).

Опять-таки f (x ₂)/ p ²  — целое число, ведь число t ₁   такое, что f (x ₁ + p • t ₁  ) ≡ 0(mod p ²). Кроме того, x ₂ ≡ x ₁ (mod p), значит f ´ (x ₂) ≡ f ´ (x ₁)(mod p), т.е. f ´ (x ₂), как и f ´ (x ₁), не делится на р. Имеем единственное решение сравнения первой степени f (x ₂)/ p ² + f´ (x ₂) • t ₂) ≡ 0(mod p) относительно t ₂ :

t ₂ ≡ t ₂   (mod p).

Это, опять-таки, означает, что t ₂ = t ₂   + p • t ₃, где t ₃ ϵ Z, и

и процесс продолжается дальше и дальше, аналогично предыдущим шагам, до достижения степени p ^a, в которой стоит простое число р в модуле исходного сравнения f (x) ≡ 0(mod p ^a).

Итак:

Всякое решение x ≡ x ₁ (mod p) сравнения f (x) ≡ 0(mod p), при условии  p/ f ´ ´ (x ₁), дает одно решение сравнения  f (x) ≡ 0(mod p ^a)  вида  x ≡ x _a + p ^a t _a, т.е. x ≡ x _a (mod p ^a).

Теорема 2. Пусть A, m, n — натуральные числа; (A, m)=1,

x ≡ x ₀ (mod m) — одно из решений сравнения

x ⁿ ≡ A (mod m).

Тогда все решения этого сравнения получаются умножением x ₀ на вычеты решений сравнения y ⁿ ≡ 1(mod m).

Доказательство. Перемножим сравнения:

откуда видно, что x ₀ y  — решения сравнения x ⁿ ≡ A (mod m).

Если теперь, то. Действительно, предположим, что x ₀ y ₁ ≡ x ₀ y ₂ (mod m). Очевидно, что (x ₀, m)=1, т.к. иначе было бы:

x₀ = d • x₀  , m = d • m  ,

x₀ = d ⁿ (x₀  ) ⁿ ≡ A (mod d m  ),

cледовательно d делит А и делит m, что противоречит взаимной простоте  А и m. Значит (x₀, m)=1 и сравнение x₀ y₁ ≡ x₀ y₂ (mod m) можно поделить на x ₀ : y ₁ ≡ y ₂ (mod m) — а это противоречит исходному предположению. Таким образом, для разных y ₁ и y ₂, получаются разные решения.

Осталось убедиться, что каждое решение сравнения x ⁿ ≡ A (mod m) получается именно таким способом. Имеем:

x ⁿ ≡ A (mod m)

x₀ ⁿ ≡ A (mod m),

следовательно, x ⁿ ≡ x ₀ ⁿ (mod m). Возьмем число y такое, что x ≡ y • x₀ (mod m). Тогда y ⁿ x₀ ⁿ ≡ x₀ ⁿ (mod m), т.е. y ⁿ ≡ 1(mod m).

В этом пункте мы будем подробно рассматривать простейшие двучленные сравнения второй степени вида x ² ≡ a (mod p), где а и р взаимно просты, а р — нечетное простое число.

Определение. Если сравнение x ² ≡ a (mod p) имеет решения, то число а называется квадратичным вычетом по модулю р. В противном случае, число а называется квадратичным невычетом по модулю р.

Итак, если а — квадрат некоторого числа по модулю р, то а —«квадратичный вычет», если же никакое число в квадрате не сравнимо с а по модулю р, то а — «квадратичный невычет».

Простое наблюдение: Если а — квадратичный вычет по модулю р, то сравнение x ² ≡ a (mod p) имеет в точности два решения. Действительно, если а — квадратичный вычет по модулю р, то у сравнения x ² ≡ a (mod p) есть хотя бы одно решение x є x ₁ (mod p). Тогдаx ₂ = - x ₁ — тоже решение, ведь (- x ₁) ² =x ₁ ². Эти два решения не сравнимы по модулю р >2, так как из x ₁ ≡ - x ₁ (mod p) следует 2 x ₁ ≡ 0(mod p), т.е. (поскольку р ≠ 2) x ₁ ≡ 0(mod p), что невозможно, ибо а ≠ 0.

Поскольку сравнение x ² ≡ a (mod p) есть сравнение второй степени по простому модулю, то больше двух решений оно иметь не может.

Еще одно простое наблюдение: Приведенная (т.е. без нуля) система вычетов

–

p-1 2

,..., -2, -1, 1, 2,...,

p-1 2

по модулю р состоит из (p -1)/2 квадратичных вычетов, сравнимых с числами 1 ²,2 ²,…,((p -1)/2) ², и (p -1)/2 квадратичных невычетов, т.е. вычетов и невычетов поровну.

Действительно, квадратичные вычеты сравнимы с квадратами чисел

–

p-1 2

,..., -2, -1, 1, 2,...,

p-1 2

т.е. с числами 1 ²,2 ²,…,((p -1)/2) ², при этом все эти квадраты различны по модулю р, ибо из k ² ≡ l ² (mod p), где 0< k < l ≤ (p -1)/2, следует, что нетривиальное сравнение x ² є k ² (mod p) имеет аж четыре решения: l, –l, k, –k, что невозможно.

Знаменитый французский математик Адриен-Мари Лежандр предложил изящный выход, введя в рассмотрение удобный символ (a / p), заменяющий длинную фразу «квадратичный вычет». Этот символ носит теперь фамилию Лежандра и читается: «символ Лежандра а по пэ».

Определение. Пусть а не кратно р. Тогда символ Лежандра определяется как:

если а - квадратичный вычет по модулю р. если а - квадратичный невычет по модулю р.

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

Теорема. (Критерий Эйлера) Пусть а не кратно р. Тогда:

a ^(p -1)/2 ≡ (a / p)(mod p).

Доказательство. По теореме Ферма, a ^p -1 ≡ 1(mod p) т.е.

. В левой части последнего сравнения в точности один сомножитель делится на р, ведь оба сомножителя на рделиться не могут, иначе их разность, равная двум, делилась бы на р >2. Следовательно, имеет место одно и только одно из сравнений:

a ^(p -1)/2 ≡ 1(mod p)

a ^(p -1)/2 ≡ -1(mod p)

Но всякий квадратичный вычет а удовлетворяет при некотором  х сравнению a ≡ x ² (mod p) и, следовательно, удовлетворяет также получаемому из него почленным возведением в степень (p -1)/2 сравнению a ^(p -1)/2 ≡ x ^p-1 ≡ 1(mod p) (теорема Ферма).

При этом квадратичными вычетами и исчерпываются все решения сравнения a ^(p -1)/2 ≡ 1(mod p), т.к., будучи сравнением степени (p -1)/2, оно не может иметь более (p -1)/2 решений. Это означает, что квадратичные невычеты удовлетворяют сравнению a ^(p -1)/2 ≡ -1(mod p).

Перечислим простейшие свойства символа Лежандра.

Свойство 1. Если a ≡ b (mod p), то (a / p)=(b / p).

Это свойство следует из того, что числа одного и того же класса по модулю р будут все одновременно квадратичными вычетами либо квадратичными невычетами.

Свойство 2. (1/ p)=1. Доказательство очевидно, ведь единица является квадратом.

Свойство 3.

.

Доказательство этого свойства следует из критерия Эйлера при а =-1. Так как (p -1)/2 — четное, если р вида 4 n +1, и нечетное, если р вида 4 n +3, то число -1 является квадратичным вычетом по модулю р тогда и только тогда, когда р вида 4 n +1.

Свойство 4.

. Действительно, . Cвойство 4, очевидно, распространяется на любое конечное число сомножителей в числителе символа Лежандра, взаимно простых с р.

Свойство 5. , т.е. в числителе символа Лежандра можно отбросить любой квадратный множитель. Действительно:

Нам понадобится несколько дополнительных свойств символа Лежандра (a / p), которые я сформулирую в виде лемм.

Пусть р — нечетное простое число, S ={1,2,…,(p -1)/2} — множество всех положительных чисел из приведенной системы вычетов по модулю р.

Рассмотрим сравнение a · s ≡ ɛ _s r _s (mod p), где а — числитель исследуемого символа Лежандра, s ϵ S, ɛ _s r _s — абсолютно наименьший вычет числа as по модулю р (т.е. вычет, абсолютная величина которого наименьшая), r _s — абсолютная величина этого вычета, а ɛ_σ, стало быть, его знак. Таким образом, r _s ϵ S, а ɛ _s = ± 1.

Лемма 1 (Гаусс).

Доказательство. Рассмотрим сравнения:

 

Множество чисел:

является приведенной системой вычетов по модулю р. Их абсолютно наименьшие вычеты соответственно суть:

 

положительные же из них, т.е. r ₁, r ₂,…, r _(p -1)/2, совпадают с числами 1,2,…,(p -1)/2, т.е. образуют множество S. Перемножим теперь почленно сравнения и сократим произведение на:

.

Получим: a ^(p -1)/2 ≡ ɛ _1 ɛ 2 … ɛ _(p -1)/2 (mod p). Согласно критерию Эйлера из предыдущего пункта, a ^(p -1)/2 ≡ (a/p)(mod p) т.е. , что и требовалось.

Лемма 2. 

При нечетном а, , где [as/p] — целая часть числа as/p.

Доказательство. Имеем:

,

что будет четным или нечетным, в зависимости от того, будет ли наименьший неотрицательный вычет числа as меньше или больше числа p/2, т.е. будет ли ɛ _s =1 или ɛ _s = -1. Отсюда, очевидно, поэтому, в силу леммы Гаусса.

Преобразуем это равенство (помним, что а + р — четное, а квадратичный множитель из числителя символа Лежандра можно отбрасывать):

Поскольку(2 a / p)=(2/ p)(a / p), а , то лемма 2 доказана.

Лемма 3.

.

Доказательство. Непосредственно следует из леммы 2 при а =1.

Так как число

(8 n + k ) 2 -1		k 2 -1
	=8 n +2 +2 nk +
8		8

будет четным при k =1 и k =7, то 2 будет квадратичным вычетом по модулю р, если р вида 8 n +1 или 8 n +7. Если же р вида 8 n +3 или 8n +5, то 2 будет квадратичным невычетом.

Теорема (Закон взаимности квадратичных вычетов). Если p и q — нечетные простые числа, то

.

Другими словами, если хоть одно из чисел p или q вида 4 n +1, то р квадрат по модулю q тогда и только тогда, когда q квадрат по модулю р. Если же оба числа p и q вида 4 n +3, то р квадрат по модулю q тогда и только тогда, когда q не является квадратом по модулю р.

Доказательство. 

Поскольку , то формула из леммы 2 принимает вид:

.

Рассмотрим два множества: S ={1,2,…, (p -1)/2} и K ={1,2,…,(q -1)/2}.

Образуем (p -1)/2 · (q -1)/2 штук пар чисел (qx,py), где х пробегает S, a y пробегает К.

Первая и вторая компонента одной пары никогда не совпадают, ибо из py = qx следует, что py кратно q. Но ведь это невозможно, так как (p,q)=1 и, поскольку 0< y < q, то (y, q)=1.

Положим, поэтому, (p -1)/2 · (q -1)/2= V ₁ + V ₂, где V ₁ — число пар, в которых первая компонента меньше второй (qx < py), V ₂ — число пар, в которых вторая компонента меньше первой (qx > py).

Очевидно, что V ₁ есть число пар, в которых x < (p / q) y. (Вообще-то, x ≤ (p -1)/2, но (p / q) y < p /2 т.к. y/q < 1/2, следовательно [(p /q) y] ≤ [p/ 2]= (p -1)/2, и неравенство x <(p / q) y не противоречит неравенству x ≤ (p -1)/2.) Поэтому,

.

Аналогично, . Тогда равенство из леммы 2, отмеченное в начале этого доказательства, дает:

.

Это означает, что

, а это, собственно, и требовалось.