Как решать уравнения на функцию эйлера

Как решать уравнения на функцию эйлера

Пример 2.1. Рассмотрим пример, который легко решить аналитически. Требуется найти экстремум функционала

при граничных условиях

Найдём частные производные и

Вычислим полную производную по x от

Составляем дифференциальное уравнение Эйлера вида

или, после упрощений

Его общее решение имеет вид

Для нахождения произвольных постоянных C₁ и C₂ подставим решение (2.16) в граничные условия (2.11):

Видно, что система (2.17) имеет единственное решение. Решая эту систему, найдём значения C₁ и C₂:

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

Действительно ли на этой кривой достигается экстремум? И если да, то какой: минимум или максимум? Далее, в главе 13, мы рассмотрим достаточные условия экстремума . В частности, мы выведем условие Лежандра: если на экстремали выполняется условие а на функциях, близких к экстремали, для произвольных y‘ имеет место то достигается сильный минимум. В нашем случае это выполняется:

и, следовательно, на нашей экстремали достигается сильный минимум. Проверим этот результат: вычислим на нескольких функциях вида Эти функции удовлетворяют граничным условиям (2.11) и, следовательно, являются допустимыми. Для вычислений применим MATLAB.

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

Пример 2.2. Найти экстремаль функционала

при граничных условиях

Выводим уравнение Эйлера вида (2.9). Частные производные:

Уравнение Эйлера после упрощений имеет вид:

Его общее решение

Находим произвольные постоянные из граничных условий (3.22). Подставляем решение (3.25) в эти граничные условия:

Мы видим, что из полученной системы уравнений можно найти только а C₂ может быть произвольной. Поэтому данная вариационная задача имеет бесчисленное множество решений вида

На любой из этих функций функционал принимает постоянное значение (какое − мы сейчас посчитаем). Проверка по достаточному условию Лежандра даёт:

поэтому на экстремалях (3.27) достигается сильный минимум.

Посчитаем значение функционала (2.21) на функциях вида (2.27) и нарисуем несколько экстремалей с помощью MATLAB.

На каждой из наших функций функционал равен нулю.

2.2. Частные случаи уравнений Эйлера

Иногда решение уравнения Эйлера существенно упрощается. Рассмотрим соответствующие частные случаи.

2.2.1. Подынтегральная функция F не зависит явно от y‘

Материал этого подраздела изложен в книге.

2.2.2. Подынтегральная функция F линейно зависит от y‘

Материал этого подраздела изложен в книге.

2.2.3. Подынтегральная функция F не зависит явно от y

Материал этого подраздела изложен в книге.

2.2.4. Подынтегральная функция F зависит только от y‘

Материал этого подраздела изложен в книге.

2.2.5. Подынтегральная функция F не зависит явно от x

Материал этого подраздела изложен в книге.

2.3. Вопросы для самопроверки

1. Какую вариационную задачу мы решаем?
2. Как выводится дифференциальное уравнение Эйлера?
3. Где используется в выводе дифференциального уравнения Эйлера основная лемма вариационного исчисления?
4. Почему обращается в нуль внеинтегральное слагаемое в формуле (2.8) при интегрировании по частям?
5. Чем отличается частная производная от полной?
6. Какие Вы знаете методы решения дифференциальных уравнений порядка?
7. Всегда ли решение вариационной задачи будет единственным? От чего это зависит?
8. Какие частные случаи уравнения Эйлера Вы знаете?
9. В каких случаях уравнение Эйлера перестаёт быть дифференциальным и становится конечным?
10. В каких случаях вариационная задача теряет смысл?
11. Как записывается интеграл уравнения Эйлера, если подынтегральная функция F не зависит явно от y?
12. Каким будет решение уравнения Эйлера, если подынтегральная функция F зависит только от y‘?
13. Как решается уравнение Эйлера, если подынтегральная функция F не зависит явно от y‘?
14. Как решается задача о брахистохроне?

2.4. Примеры выполнения заданий

2.4.1. Задание 1

Найти экстремаль функционала

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

В этом примере подынтегральная функция является функцией общего вида, поэтому составим уравнение Эйлера в виде (2.9) и решим его. Затем построим график решения. Попутно исследуем на выполнение достаточных условий экстремума и вычислим значение функционала на экстремали и отрезке прямой M₁M₂. Применим для решения задачи MATLAB.

Очистим память. Напечатаем заголовок решаемой задачи. Если хотите, задайте другую строку для вывода (например, свою фамилию). Опишем символические переменные [58]. Для решения уравнения Эйлера используем принятые в MATLAB обозначения производных: Dy для y‘ и D2y для y». Аргумент обозначим x , а функцию − y .

Вводим подынтегральную функцию и граничные условия. Печатаем их. Здесь вы должны поставить свои исходные данные: подынтегральную функцию F и граничные условия x₁, y₁, x₂, y₂.

Начинаем вывод дифференциального уравнения Эйлера (2.9). Найдём частные производные F_y и F_y’. Напечатаем их.

В уравнение Эйлера (2.9) входит полная производная Вычислим её по обычной формуле дифференцирования сложной функции:

Напечатаем её. Напечатаем также величину необходимую для проверки достаточных условий экстремума по признаку Лежандра.

Составим левую часть дифференциального уравнения Эйлера (2.9) и упростим её. Преобразуем символическую переменную Euler в строку.

Мы составили уравнение Эйлера, теперь решим его. Команда dsolve позволяет находить как общее решение дифференциального уравнения, так и частное его решение, удовлетворяющее заданным начальным или граничным условиям. В следующих главах при решении других заданий нам нужно будет иметь общее решение уравнения Эйлера. Найдём его.

Сформируем теперь уравнения для граничных условий. Подставим в найденное аналитическое решение Sol граничные точки x1 и x2 , и приравняем их соответственно y1 и y2 .

Решаем полученную систему конечных уравнений − находим значения произвольных постоянных C1 и C2 . Присваиваем найденные решения символическим константам, полученным при решении дифференциального уравнения. Теперь вычисляем аналитическое решение Sol21 . Такое вычисление сводится к тому, что в него будут подставлены найденные значения констант C1 и C2 . Печатаем найденное уравнение экстремали.

Вычислим значения функционала (2.86) на найденной экстремали и на прямой, соединяющей точки M₁ и M₂. Подставим в подынтегральную функцию F аналитические выражения для этих линий и их производных, а затем проинтегрируем. Напечатаем результаты.

В данном примере условие Лежандра говорит о сильном минимуме, что подтверждается полученным результатом: значение функционала на экстремали меньше, чем на другой допустимой функции. А как в вашем варианте: какой экстремум достигается? И подтверждается ли этот результат сравнением величин Jextr и Jlin ? Если нет, то не забудьте, что найденный экстремум − только локальный, а не глобальный! Попробуйте вычислить значение функционала не на прямой M₁M₂, а на какой-нибудь другой допустимой кривой, достаточно близкой к экстремали. Например, можно наложить на экстремаль несколько полуволн синусоиды, смещённой и деформированной вдоль оси Ox так, что

И, наконец, строим график. Задаём массив аргументов для рисования графика функции и вычисляем значения функции. Рисуем график, подписываем заголовок и координатные оси установленным шрифтом.

2.4.2. Задание 2

Найти экстремаль функционала

Исследовать на выполнение достаточных условий экстремума. Построить график решения.

В этом примере подынтегральная функция не зависит явно от y. Первый интеграл уравнения Эйлера имеет вид (2.43). Составим программу для решения этой вариационной задачи. Вначале введём исходные данные. У нас будет первый интеграл уравнения Эйлера, поэтому ни сама функция y, ни её вторая производная y» нам не нужны, и мы их не описываем. Поставьте свою подынтегральную функцию и граничные условия.

Строим первый интеграл и решаем полученное дифференциальное уравнение. Названия констант C1 и C2 используются в команде dsolve , поэтому при составлении интеграла уравнения Эйлера обозначим константу C . Все использованные здесь функции и операторы MATLAB были описаны ранее, в примере 1.

В переменной Sol получено общее решение, произвольные постоянные обозначены C и C1 . Найдём их. Для этого подставим в Sol граничные точки. Приравняем полученные выражения соответственно y1 и y2 . Тем самым мы сформируем систему уравнений.

Решим полученную систему − найдём произвольные постоянные C и C1 . Подставим их в решение Sol . Ограничим решение 14 знаками. Напечатаем уравнение найденной экстремали.

Дальнейшие действия не отличаются от описанных в примере 1. Рисуем график и и вычисляем F_y’y’, которая нужна для проверки достаточных условий экстремума по признаку Лежандра.

Проанализируйте достаточное условие Лежандра. Достигается ли экстремум на вашей экстремали? Если да, то какой?

2.4.3. Задание 3

Решить задачу о брахистохроне, соединяющей точки и

Мы уже решили эту задачу аналитически. Нам осталось найти значение константы C₁ и параметра в конечной точке t₂ из решения системы уравнений (2.84). Составим программу для решения этого примера. Вначале введём исходные данные задачи. Подставьте свою правую точку.

Составляем систему уравнений (2.84). Левую часть каждого уравнения мы задаём сразу в виде строки. В правой части переводим числа x2 и y2 в их строковые представления с помощью функции num2str . Ранее мы использовали конструкцию char(sym(y2)) . Оба варианта работают правильно − вы можете это проверить. Решаем полученную систему уравнений аналитически. Печатаем решения.

Рисуем график полученной брахистохроны. Выбираем начало координат в левом верхнем углу с помощью команды axis . Задаём границы по оси Ox, чтобы график занимал всё место на рисунке. Выравниваем масштабы по осям координат, чтобы брахистохрона выглядела неискажённой. Надписываем заголовок и метки осей.

2.5. Задание

Для своего варианта функционалов 1, 2, 3 найти экстремали, построить их графики и исследовать на выполнение достаточных условий экстремума.

Дифференциальное уравнение Эйлера и методы его решения

Более общее уравнение Эйлера имеет вид:
.
Это уравнение подстановкой t = ax+b приводится к более простому виду, которое мы и будем рассматривать.

Приведение дифференциального уравнения Эйлера к уравнению с постоянными коэффициентами.

Рассмотрим уравнение Эйлера:
(1) .
Оно сводится к линейному уравнению с постоянными коэффициентами подстановкой:
x = e t .
Действительно, тогда
;
;
;

;
;
.

Таким образом, множители, содержащие x m , сокращаются. Остаются члены с постоянными коэффициентами. Однако на практике, для решения уравнений Эйлера, можно применять методы решения линейных ДУ с постоянными коэффициентами без использования указанной выше подстановки.

Решение однородного уравнения Эйлера

Рассмотрим однородное уравнение Эйлера:
(2) .
Ищем решение уравнения (2) в виде
.
;
;
.
.
Подставляем в (2) и сокращаем на x k . Получаем характеристическое уравнение:
.
Решаем его и получаем n корней, которые могут быть комплексными.

Рассмотрим действительные корни. Пусть k_i – кратный корень кратности m . Этим m корням соответствуют m линейно независимых решений:
.

Рассмотрим комплексные корни. Они появляются парами вместе с комплексно сопряженными. Пусть k_i – кратный корень кратности m . Выразим комплексный корень k_i через действительную и мнимую части:
.
Этим m корням и m комплексно сопряженным корням соответствуют 2 m линейно независимых решений:
;
;
.
.

После того как получены n линейно независимых решений, получаем общее решение уравнения (2):
(3) .

Примеры

Решение неоднородного уравнения Эйлера

Рассмотрим неоднородное уравнение Эйлера:
.
Метод вариации постоянных (метод Лагранжа) также применим и к уравнениям Эйлера.

Сначала мы решаем однородное уравнение (2) и получаем его общее решение (3). Затем считаем постоянные функциями от переменной x . Дифференцируем (3) n – 1 раз. Получаем выражения для n – 1 производных y по x . При каждом дифференцировании члены, содержащие производные приравниваем к нулю. Так получаем n – 1 уравнений, связывающих производные . Далее находим n -ю производную y . Подставляем полученные производные в (1) и получаем n -е уравнение, связывающее производные . Из этих уравнений определяем . После чего интегрируя, получаем общее решение уравнения (1).

Пример

Неоднородное уравнение Эйлера со специальной неоднородной частью

Рассмотрим уравнение Эйлера со специальной неоднородной частью:
(4)
,
где – многочлены от степеней и , соответственно.

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

Автор: Олег Одинцов . Опубликовано: 14-08-2013 Изменено: 24-10-2020

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

Литература

Обозначения

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

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

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

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

Делимость

Определение и свойства делимости

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

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

Определение простых и составных чисел

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

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

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

Замечание 1. Согласно определению у составного числа $n$ имеется хотя бы один делитель $d$ с условием $1 0\; |\; y_1,\ldots ,y_n\in\mathbb\>$. Оно не пусто, поскольку выбор $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 0$, то $r\in M$ и при этом $r 0$, то тогда $r$ – натуральное число, меньшее, чем $b$. Это противоречит тому, что $b$ – наименьшее общее кратное этих чисел. Значит $r=0$ и $c$ делится на $b$. Теорема 2 доказана.

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

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

Лемма 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$.

Следствие 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_)=1$ (если бы нашёлся общий простой делитель, то он делил бы одновременно $a_$ и какое-то из $a_i, i=1,\ldots ,n$, что противоречило бы условию $(a_i,a_)=1$). Вновь из леммы 3 следует, что $[[a_1,\ldots,a_n], a_]=a_1\cdots a_n\cdot a_$. Тогда по следствию 4 получаем $$[a_1,\ldots,a_n, a_]=[[a_1,\ldots,a_n], a_]= a_1\cdots a_n\cdot a_. $$ Следствие 6 доказано.

Алгоритм Евклида

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

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

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

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

Доказательство. Предположим, что у $n$ нет простых делителей, не превосходящих $[\sqrt]$. Покажем, что у него тогда не может быть и простых делителей, больших чем $[\sqrt]$, кроме него самого. Пусть $p|n,\ [\sqrt]+1\leqslant p (\sqrt)^2=n$. А так как $\frac

$ – число натуральное, то и $\frac

\leqslant [\sqrt]$. Но по лемме 4 у числа $\frac

$ есть простой делитель $q$. При этом очевидно, что $q\leqslant\frac

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

Основная теорема арифметики (единственность разложения на простые)

Теорема 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 \nu_p(n)$, то $\nu_p(m+n)=\nu_p(n)$

Мультипликативные функции

Определение и свойства мультипликативных функций. Свёртка Дирихле

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

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

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

Из определения следует, что если $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_f(d)\cdot g\left(\frac\right)=\prod_\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_\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_^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_f(d)\cdot g\left(\frac\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_f(d)\cdot g\left(\frac\right).$$ Эта функция называется свёрткой Дирихле функций $f$ и $g$.

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

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

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

Доказательство. По следствию 9 свёртка Дирихле двух мультипликативных функций есть также мультипликативная функция. Заметим, что $$f\circ g(n)=\sum_f(d)\cdot g\left(\frac\right)=\sum_f(d_1)\cdot g(d_2)=\sum_g(d_2)\cdot f(d_1)=g\circ f(n),$$ то есть свёртка Дирихле коммутативна. Аналогично доказывается ассоциативность свёртки Дирихле: $$f\circ \big(g\circ h\big)(n)=\sum_f(d_1)\cdot\big(g\circ h\big)(d’)= \sum_f(d_1)\cdot\left(\sum_g(d_2)\cdot h(d_3)\right)=$$ $$=\sum_f(d_1)\cdot g(d_2)\cdot h(d_3)=\sum_\left(\sum_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^)+\ldots +f(p^)\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(n)=n$ и $<\bf 1>(n)=1$, очевидно, тоже (вполне) мультипликативны.

Рассмотрим функцию $\tau(n)$, которая подсчитывает количество различных натуральных делителей числа $n$. Имеем $$\tau(n)=\sum_1=\sum_<\bf 1>(d)\cdot <\bf 1>\left(\frac\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=\sum_\textrm(d)\cdot <\bf 1>\left(\frac\right)=\textrm\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-1>\cdots\frac-1>.$$

Функция Мёбиуса. Формула обращения Мёбиуса

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

Её мультипликативность следует из определения. Действительно, пусть $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)^=(-1)^\cdot (-1)^=\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_(\mu(1)+\mu(p)+\mu(p^2)+\ldots+\mu(p^<\nu_p(n)>) )=\prod_(1-1+0+\ldots +0)=\varepsilon(n).$$ Так что функция Мёбиуса является обратной функцией к тождественной единице $<\bf 1>(n)$ относительно операции свёртки Дирихле. Также заметим, что $$\mu\circ\textrm(n)=\prod_(\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^<\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\circ<\bf 1>$. По формуле обращения Мёбиуса находим $\textrm=\sigma\circ\mu$, то есть $\sum_\sigma(d)\cdot\mu\left(\frac\right)=n$. Аналогично из $\tau=<\bf 1>\circ<\bf 1>$ получаем $<\bf 1>=\tau\circ\mu$, то есть $\sum_\tau(d)\cdot\mu\left(\frac\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_^n\varepsilon ( (k, n) )=\sum_^n\mu\circ <\bf 1>( (k, n) )=$$ $$=\sum_^n\sum_\mu(d)=\sum_\mu(d)\sum_<1\leqslant k\leqslant n,\ k\,\vdots\, d>1=\sum_\mu(d)\frac =\mu\circ\textrm (n). $$ По предложению 2, таким образом, функция $\varphi (n) $ мультипликативна. Здесь при перемене местами двух сумм мы воспользовались следующим соображением: если $d|(k, n)$, то $d|k$ и $d|n$. Так как $k$ меняется от $1$ до $n$, то $d$ пробежит все натуральные делители числа $n $, причём некоторые, возможно, по несколько раз. Каждое конкретное $d$ встречается столько раз, сколько найдётся чисел $k$, делящихся на это $d$. А их будет ровно $\frac$.

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

Покажем явную формулу для функции Эйлера. Имеем $$\varphi (n) =\mu\circ\textrm (n)=\prod_(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^<\nu_p(n)>-p^<\nu_p(n)-1>)=\prod_p^<\nu_p(n)>\cdot\left(1-\frac<1>

\right)=n\cdot\prod_\left(1-\frac<1>

\right).$$ Последнее равенство справедливо, так как $\prod_p^<\nu_p(n)>=n$.

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

Формула включений и исключений

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

Пусть имеется $N$ объектов, которые могут обладать (или нет) свойствами $ a_1,\ldots , a_k $. Будем обозначать через $N (a_,\ldots ,a_) $ количество тех из наших $N $ объектов, что обладают каждым из свойств $a_,\ldots ,a_,\ 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_,a_k)-$$ $$-N(a_1,a_2,a_3)-\ldots -N(a_,a_,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_$. Пусть $M$ – это количество всех тех из наших $N$ объектов, которые обладают свойством $a_$. Обозначим через $M (a_,\ldots ,a_)$ количество тех из только что выделенных $M$ объектов, что обладают каждым из свойств $a_,\ldots ,a_,\ 1\leqslant i_1,\ldots , i_j\leqslant k$. За $M_0$ обозначим количество тех из этих же $M$ объектов, которые не обладают ни одним из свойств $a_1,\ldots ,a_k$. Заметим, что, вообще говоря, $M=N(a_)$ и $M (a_,\ldots ,a_)=N(a_,\ldots ,a_,a_)$. Запишем формулу включений и исключений для этих выделенных $M$ объектов: $$M_0=M-M(a_1)-\ldots — M(a_k)+M(a_1,a_2)+\ldots +M(a_,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_$ равно количеству чисел, не обладающих ни одним из свойств $a_1,\ldots ,a_k$, за вычетом количества тех из них, что обладают свойством $a_$. Имеем $$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_,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_,a_k)+\ldots +(-1)^k\cdot M(a_1,\ldots ,a_k)\big)=$$ $$=N-N(a_1)-\ldots — N(a_k)-N(a_)+N(a_1,a_2)+\ldots +N(a_,a_k)+N(a_1,a_)+\ldots +N(a_k,a_)+\ldots +$$ $$+(-1)^\cdot N(a_1,\ldots ,a_k,a_).$$ Теорема 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_,\ldots ,a_) $, ведь некоторое число делится одновременно на $p_,\ldots ,p_$ тогда и только тогда, когда оно делится на $p_\cdots p_$, а таких чисел ровно $\frac\cdots p_>$. Заметим также, что $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_,a_k)+\ldots +(-1)^k\cdot N(a_1,\ldots ,a_k)=$$ $$=N-\frac-\ldots -\frac+\frac+\ldots+\frac\cdot p_k>+\ldots+(-1)^k\frac=$$ $$=N\cdot\Big(1-\frac<1>-\ldots -\frac<1>+\frac<1>+\ldots+\frac<1>\cdot p_k>+\ldots+(-1)^k\frac<1>\Big)=$$ $$=N\cdot\prod_^\left(1-\frac<1>\right)=N\cdot\prod_\left(1-\frac<1>

\right).$$ Заметим, что в сумме в предпоследней строчке перед каждым слагаемым вида $\frac<1>\cdots p_>$ стоит знак $(-1)^j$, что по определению функции Мёбиуса равно $\mu(p_\cdots p_)$.

Ещё о мультипликативности функции Эйлера

На самом деле, мультипликативность функции Эйлера можно доказать, пользуясь совсем простыми соображениями. Пусть $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

Сравнения

Классы вычетов. Полная и приведённая системы вычетов

Пусть $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.$$ Заметим, что $a\equiv b\pmod\Leftrightarrow m|(b-a)$.

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

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

Предложение 3. Пусть $a$ пробегает полную систему вычетов по модулю $m$, а также $k,n\in\mathbb$ и $(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$, где $a_1\not\equiv a_2\pmod$. Но тогда из первого и шестого свойств сравнений следует, что $a_1\cdot n\equiv a_2\cdot n\pmod$, и, так как $(m,n)=1$, то по четвёртому свойству сравнений $a_1\equiv a_2\pmod$. Противоречие. Предложение 3 доказано.

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

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

Теорема Эйлера

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

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

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

Обратный элемент по модулю $m$

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

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

Китайская теорема об остатках

Пусть $m_1,\ldots ,m_n$ натуральные попарно взаимно простые числа, и требуется решить систему сравнений $$x\equiv a_1\pmod;$$ $$\ldots$$ $$x\equiv a_n\pmod.$$ Положим $M=m_1\cdots m_n$ и $M_i=\frac,\ 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.$$

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

Далее, заметим, что при $j\neq i$ имеем $M_j\equiv 0\pmod $. Поэтому при любом $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 , $$ то есть данное число является решением нашей системы сравнений. Теорема 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$ решение, так как все решения уравнения $ax+py=b$ имеют вид $x=x_0+pt,\ y=y_0-at,\ t\in\mathbb$. Оказывается, имеет место более общее утверждение, а именно

Теорема 8 (теорема Лагранжа). Пусть $p$ простое число и $f(x)=a_nx^n+a_x^+\ldots +a_1x+a_0$, где $a_n,\ldots ,a_0\in\mathbb$, причём $a_n\not\equiv 0\pmod

$. Тогда сравнение $f(x)\equiv 0\pmod

$ имеет не более $n$ решений по модулю $p$.

Доказательство. Проведём индукцию по $n$. При $n=1$ справедливость теоремы уже установлена. Пусть утверждение теоремы верно для всех многочленов степени $n-1$. Покажем, что оно справедливо и для многочленов степени $n$. Пусть $f(x)$ – многочлен, описанный в условии теоремы. Если сравнение $f(x)\equiv 0\pmod

$ неразрешимо, то утверждение теоремы выполняется. Допустим указанное сравнение имеет некоторое решение $x_0$, то есть $f(x_0)\equiv 0\pmod

$. Тогда $$f(x)\equiv f(x)-f(x_0)=a_n(x^n-x_0^n)+a_(x^-x_0^)+\ldots +a_1(x-x_0)=(x-x_0)\cdot g(x)\pmod

,$$ где $g(x)=a_nx^+\ldots$ – многочлен степени $n-1$, и по предположению индукции сравнение $g(x)\equiv 0\pmod

$ имеет не более $n-1$ решения по модулю $p$. При этом из установленного сравнения следует, что $f(x)\equiv 0\pmod

$ тогда и только тогда, когда $g(x)\equiv 0\pmod

$ или $x-x_0\equiv 0\pmod

$. Второе из этих сравнений имеет единственное решение по модулю $p$, а значит сравнение $f(x)\equiv 0\pmod

$ имеет не более $n$ решений. Теорема 8 доказана.

Замечание 6. Если $m$ составное число, то сравнение $f(x)\equiv 0\pmod$ может иметь более $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$ решение. Очевидно, что при различных $a$ эти решения тоже будут различны, ведь из сравнений $a_1x\equiv a_2x\equiv b\pmod

$ следовало бы $a_1\equiv a_2\pmod

$, так как очевидно $(x,p)=1$. Заметим также, что если $a_1$ есть решение сравнения $ax\equiv b\pmod

$, то, наоборот, $a$ будет решением сравнения $a_1x\equiv b\pmod

$.

При некоторых $b$ возможно, что само $a$ будет решением сравнения $ax\equiv b\pmod

$. Это случится тогда и только тогда, когда разрешимо сравнение $x^2\equiv b\pmod

$. Сколько решений может иметь такое сравнение? Пусть $x$ – некоторое решение данного сравнения, тогда $-x$ – тоже его решение. При этом из $(b,p)=1$ следует $x\not\equiv 0\pmod

$, а значит $x\not\equiv -x\pmod

$, поскольку $p$ нечётно. По теореме Лагранжа более двух решений данное сравнение иметь не может. Следовательно $x$ и $-x$ – все решения данного сравнения. Если же $p|b$, то $x\equiv 0\pmod

$, очевидно, является единственным решением.

При $(b,p)=1$ получается, что если сравнение $x^2\equiv b\pmod

$ неразрешимо, то приведённая система вычетов по модулю $p$ разбивается на пары чисел $a,a_1$ таких, что $aa_1\equiv b\pmod

$, а значит произведение всех $p-1$ элементов приведённой системы вычетов будет сравнимо с $b^<\frac<2>>$ по модулю $p$. Если же сравнение $x^2\equiv b\pmod

$ разрешимо, то приведённая система вычетов по модулю $p$ разбивается на пары чисел $a,a_1$ таких, что $aa_1\equiv b\pmod

$ за исключением двух решений $x$ и $-x$ сравнения $x^2\equiv b\pmod

$, произведение которых сравнимо с $-b$ по модулю $p$. Таким образом, произведение всех $p-1$ элементов приведённой системы вычетов будет сравнимо с $-b^<\frac<2>>$ по модулю $p$.

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

$\left(\frac

\right)=1$, если $(b,p)=1$ и сравнение $x^2\equiv b\pmod

$ разрешимо;

$\left(\frac

\right)=0$, если $(b,p)\neq 1$, то есть $p|b$;

$\left(\frac

\right)=-1$, если сравнение $x^2\equiv b\pmod

$ неразрешимо.

Пример 5. $\left(\frac<1>

\right)=1$, так как $(1,p)=1$ и сравнение $x^2\equiv 1\pmod

$ имеет очевидные решения $x\equiv 1\pmod

$ и $x\equiv -1\pmod

$.

Рассмотрим как раз случай $b=1$ в проведённых выше рассуждениях. Так как сравнение $x^2\equiv 1\pmod

$ разрешимо, то произведение всех $p-1$ элементов приведённой системы вычетов будет сравнимо с $-1^<\frac<2>>$, то есть с $-1$ по модулю $p$. Это позволяет доказать ряд известных теорем.

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

$.

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

Критерий Эйлера. Пусть $b\in\mathbb$. Тогда $\left(\frac

\right)\equiv b^<\frac<2>>\pmod

$.

Доказательство. Пусть $b\in\mathbb, (b,p)=1$. Мы знаем, что если сравнение $x^2\equiv b\pmod

$ неразрешимо, то $b^<\frac<2>>$ сравнимо с произведением всех элементов приведённой системы вычетов по модулю $p$, которое, в свою очередь, сравнимо с $-1$. Но и символ Лежандра $\left(\frac

\right)$ в этом случае тоже равен $-1$. Если же сравнение $x^2\equiv b\pmod

$ разрешимо, то $-b^<\frac<2>>$ сравнимо с произведением всех элементов приведённой системы вычетов по модулю $p$, а значит $b^<\frac<2>>\equiv 1\pmod

$. При этом символ Лежандра $\left(\frac

\right)$ в этом случае также равен $1$. Пусть теперь $p|b$. Но тогда $b^<\frac<2>>\equiv 0\pmod

$, и символ Лежандра $\left(\frac

\right)$ тоже равен $0$. Таким образом, во всех случаях критерий Эйлера доказан.

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

$.

Доказательство. Это очевидно следует из критерия Эйлера, поскольку при $(b,p)=1$ будет $b^<\frac<2>>\equiv\pm 1\pmod

$, и утверждение теоремы Ферма получится при возведении обеих частей данного сравнения в квадрат. Теорема Ферма доказана.

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

Заметим, что при $(b,p)\neq 1$, то есть когда $p|b$, будет $b^\equiv 0\pmod

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

.$$

Свойства символа Лежандра. Лемма Гаусса. Квадратичный закон взаимности

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

Если $p\nmid b$, то $\left(\frac

\right)=1$, в частности $\left(\frac<1>

\right)=1$;

$\left(\frac<-1>

\right)=1$, если $p\equiv 1\pmod<4>$,

$\left(\frac<-1>

\right)=-1$, если $p\equiv -1\pmod<4>$;

$\left(\frac<2>

\right)=1$, если $p\equiv\pm 1\pmod<8>$,

$\left(\frac<2>

\right)=-1$, если $p\equiv\pm 3\pmod<8>$;

$\left(\frac

\right)=-\left(\frac

\right)$, если $p\equiv q\equiv -1\pmod<4>$,

Докажем эти свойства символа Лежандра. Пусть $a\equiv b\pmod

$, тогда, если $p\nmid b$, то и $p\nmid a$, и сравнение $x^2\equiv a\pmod

$ разрешимо тогда и только тогда, когда разрешимо сравнение $x^2\equiv b\pmod

$. Если же $p|b$, то также $p|a$. В обоих случаях по определению символа Лежандра получаем, что $\left(\frac

\right)=\left(\frac

\right)$. Первое свойство доказано.

При $p\nmid b$ сравнение $x^2\equiv b^2\pmod

$ имеет два очевидных решения $x\equiv b\pmod

$ и $x\equiv -b\pmod

$, откуда по определению символа Лежандра получаем, что $\left(\frac

\right)=1$. Третье свойство доказано.

По критерию Эйлера имеем $$\left(\frac<-1>

\right)\equiv (-1)^<\frac<2>>\pmod

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

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

Лемма Гаусса. Пусть $p$ нечётное простое число, $b\in\mathbb,\ p\nmid b$. Тогда $$\left(\frac

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

$, где $\varepsilon_k=\pm 1$ и $r_k\in\<1, 2,\ldots ,\frac<2>\>$.

Доказательство. Покажем, что среди чисел $r_1, r_2,\ldots ,r_<\frac<2>>$ нет равных друг другу, то есть они представляют собой перестановку чисел $1, 2,\ldots ,\frac<2>$. От противного, если $i 1$ нечётное натуральное число, $P=p_1\cdots p_s$ – его разложение на простые множители (возможно совпадающие, но все нечётные) и $A\in\mathbb$. Тогда символ Якоби определяется так: $$\left(\frac

\right)=\left(\frac\right)\cdots\ \left(\frac\right).$$ Свойства символа Лежандра переносятся и на символ Якоби. Пусть $P$ нечётное число, $A,B\in\mathbb$. Тогда

Если $(P,B)=1$, то $\left(\frac

\right)=1$, в частности $\left(\frac<1>

\right)=1$;
$\left(\frac<-1>

\right)=1$, если $P\equiv 1\pmod<4>$,
$\left(\frac<-1>

\right)=-1$, если $P\equiv -1\pmod<4>$;
$\left(\frac<2>

\right)=1$, если $P\equiv\pm 1\pmod<8>$,
$\left(\frac<2>

\right)=-1$, если $P\equiv\pm 3\pmod<8>$;
$\left(\frac

\right)=-\left(\frac

\right)$, если $P\equiv Q\equiv -1\pmod<4>$,

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

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

\right)=-1$. Если же $P\equiv 1\pmod<4>$, то в разложении $P=p_1\cdots p_s$ количество простых, сравнимых с $-1$ по модулю $4$, чётно, и $\left(\frac<-1>

\right)=1$.

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

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

Поэтому главным предназначением символа Якоби является ускорение процедуры вычисления символа Лежандра. Пусть требуется определить количество решений сравнения $$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

$ необходимо обладать большей информацией, нежели просто значение символа Якоби $\left(\frac

\right)$. Чтобы понять, что это за информация для начала рассмотрим сравнения вида $x^2\equiv A\pmod$. Следующий результат описывает даже более полную ситуацию.

Лемма Гензеля. Пусть $p$ простое число, многочлен $f(x)$ имеет целые коэффициенты. Допустим имеется целое число $x_1$ такое, что $f(x_1)\equiv 0\pmod

$ и $f'(x_1)\not\equiv 0\pmod

$, где $f'(x)$ – производная многочлена $f(x)$. Тогда для любого натурального числа $k$ в любой полной системе вычетов по модулю $p^k$ найдётся единственный элемент $x_k$ с условиями $x_k\equiv x_1\pmod

$ и $f(x_k)\equiv 0\pmod$.

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

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

Доказательство достаточно провести для многочлена вида $f(x)=x^n$ ввиду линейности. Для такого многочлена необходимое равенство приобретает вид $$(x+a)^n=x^n+nx^a+\frac<2>x^a^2+\ldots +\fraca^n,$$ так что оно представляет из себя в точности формулу бинома Ньютона. Лемма 5 доказана.

Доказательство леммы Гензеля проведём индукцией по $k$. При $k=1$ в произвольной полной системе вычетов по модулю $p$ найдётся единственный элемент, сравнимый по этому же модулю с $x_1$, а сравнение $f(x_1)\equiv 0\pmod

$ выполнено по условию. Пусть теперь $k>1$ и для $k-1$ утверждение верно. Мы ищем элемент $x_k$ с условиями $x_k\equiv x_1\pmod

$ и $f(x_k)\equiv 0\pmod$. Но для этого элемента будет тогда также выполнено $f(x_k)\equiv 0\pmod>$. Ввиду единственности решения этого сравнения по модулю $p^$ будем иметь $x_k\equiv x_\pmod>$. Поэтому $x_k$ следует искать в виде $x_k=x_+t\cdot p^$ с некоторым целым числом $t$. В приведённой системе вычетов по модулю $p^$ найдётся ровно $p$ элементов такого вида, причём соответствующие им значения $t$ составят полную систему вычетов по модулю $p$. Условие $x_k\equiv x_1\pmod

$ будет выполнено автоматически. Для проверки условия $f(x_k)\equiv 0\pmod$ воспользуемся леммой 5 и запишем $$f(x_k)=f(x_+t\cdot p^)=f(x_)+t\cdot p^\cdot f'(x_)+\ldots\equiv f(x_)+t\cdot p^\cdot f'(x_)\pmod.$$ Таким образом, должно быть выполнено $$f(x_)+t\cdot p^\cdot f'(x_)\equiv 0\pmod.$$ Так как $f(x_)\equiv 0\pmod>$, то обе части и модуль этого сравнения можно поделить на $p^$. Получим $$\frac)>>+t\cdot f'(x_)\equiv 0\pmod

.$$ Поскольку $f'(x_)\equiv f'(x_1)\not\equiv 0\pmod

$, полученное сравнение относительно $t$ имеет единственное решение. А следовательно и $x_k$ существует и единственно. Лемма Гензеля доказана.

Применим лемму Гензеля для решения сравнения $x^2\equiv A\pmod$, где $p$ – нечётное простое число. Если сравнение $x^2\equiv A\pmod

$ неразрешимо, то и наше сравнение не может иметь решений при любом натуральном $k$. Если сравнение $x^2\equiv A\pmod

$ имеет единственное решение, то $A\equiv 0\pmod

$, а значит и решением будет $x_1\equiv 0\pmod

$. В этом случае лемма Гензеля неприменима, так как при $f(x)=x^2$ будем иметь $f'(x)=2x$, но $2x_1\equiv 0\pmod

$. Однако этот случай достаточно прост, чтобы уделять ему внимание. Пусть теперь сравнение $x^2\equiv A\pmod

$ имеет два различных решения $x\equiv\pm x_1\pmod

$. Очевидно $2x_1\not\equiv 0\pmod

$ и лемма Гензеля может быть применена. Из неё следует, что для каждого натурального $k$ будет иметься ровно два различных решения сравнения $x^2\equiv A\pmod$.

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

Предложение 4. Пусть $A\in\mathbb$ нечётно, $k\in\mathbb,\ 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^>$. Если же $c$ нечётно, то $(x_k+2^)^2\equiv A\pmod<2^>$, то есть сравнение $x^2\equiv A\pmod<2^>$ будет иметь некоторое решение $x_$. Но вместе с ним оно будет иметь по крайней мере четыре решения $\pm x_\pm 2^k$. C другой стороны, поскольку в приведённой системе вычетов по модулю $2^$ ровно каждое четвёртое число сравнимо с $1$ по модулю $8$, то, взяв для каждого из этих чисел по четыре решения соответствующего сравнения, мы уже исчерпаем всю приведённую систему вычетов по модулю $2^$, а значит более четырёх решений ни у одного из этих сравнений быть не может. Более того, не может быть решений и у сравнений $x^2\equiv A\pmod<2^>$ при $A\not\equiv 1\pmod<8>$. Предложение 4 доказано.

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

Из всего вышесказанного видно, что если $P=p_1^\cdots p_m^$, сравнение $x^2\equiv A\pmod

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

Первообразные корни

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

Наименьшее натуральное $d$, с которым выполняется сравнение $a^d\equiv 1\pmod$, называется показателем числа $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$. Тогда $d|n$.

Доказательство. От противного, пусть $n=qd+r,\ 0 2$, уже показано.

Существование первообразных корней по модулям $p^$ и $2p^$ с нечётным простым $p$

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

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

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

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

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

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

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

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

Как видно из теорем 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^\cdots q_s^$ – разложение на простые множители. Тогда, если для каждого $i=1,\ldots ,s$ выполнено $g^<\varphi(m)/q_i>\not\equiv 1\pmod$, то $g$ – первообразный корень по модулю $m$.

Доказательство. Если $g$ – не первообразный корень по модулю $m$, то найдётся натуральное число $d$, меньшее чем $\varphi(m)$, такое что $g^d\equiv 1\pmod$. По предложению 5 $d|\varphi(m)$, а значит $d=q_1^\cdots q_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$. Противоречие. Теорема 11 доказана.

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

убедиться, что символ Лежандра $\displaystyle\left(\frac

\right)=-1$

проверять, выполняется ли условие $g^\not\equiv 1\pmod

$ для каждого $i=1,\ldots ,s$

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

Условие $\displaystyle\left(\frac

\right)=-1$ является проверкой эквивалентного ему условия $g^\not\equiv 1\pmod

$. Дело в том, что по критерию Эйлера $g^\equiv \displaystyle\left(\frac

\right)\pmod

$, а ненулевой символ Лежандра, если он не сравним с $1$, должен равняться $-1$.

В качестве первого кандидата имеет смысл брать $g=2$. Нет необходимости рассматривать заведомые квадратичные вычеты, например $4$ или вообще какие бы то ни было квадраты. Число $-1$ является первообразным корнем по модулям $2,\ 3,\ 4,\ 6$ и ни по каким другим модулям его рассматривать не нужно, поскольку $(-1)^2\equiv 1\pmod$ при любом $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^$. В этом легко убедиться, ведь для первообразного корня всегда выполнено $\displaystyle\left(\frac

\right)=-1$, а $\displaystyle\left(\frac

\right)\equiv g^\pmod

$ по критерию Эйлера. При этом ни в какой другой степени от $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>$.