10. Полная и приведенная системы вычетов
Определение. Числа образуют полную систему вычетов по модулю
, если любое целое число сравнимо по модулю
с одним и только одним из этих чисел.
Любая полная система вычетов по модулю состоит из
чисел, которые попарно не сравнимы по модулю
.
Теорема. Пусть — полная система вычетов по модулю
. Пусть
— целое число, взаимно простое с
. Тогда
— тоже полная система вычетов по модулю
.
Доказательство. Нужно доказать, что эти числа попарно не сравнимы по модулю . Предположим противное. Пусть
Так как НОД, то
, что противоречит условию.
Теорема. Пусть — полная система вычетов по модулю
. Пусть
— целое число. Тогда
— тоже полная система вычетов по модулю
.
Лемма. Если , то НОД
НОД
.
Доказательство.
– целое число.
Отсюда . Любой общий делитель
и
является делителем
. Отсюда НОД
НОД
.
Определение. Числа образуют приведенную систему вычетов по модулю
, если они взаимно просты с
и любое целое число, взаимно простое с
, сравнимо с одним и только одним из этих чисел по модулю
.
Пример. Приведенная система вычетов по модулю :
.
Лемма. Все приведенные системы вычетов по модулю состоят из одного и того же количества чисел, которое обозначается
— функция Эйлера.
Доказательство. Действительно, пусть есть две приведенные системы вычетов по модулю , состоящие из разного количества чисел:
Тогда так как числа образуют приведенную систему вычетов по модулю
, то каждое из чисел
сравнимо с одним и только одним из этих чисел. Поскольку
, то, по принципу Дирихле, по крайней мере два числа из
будут сравнимы с каким-то числом
, а значит, будут сравнимы между собой по модулю
. А это противоречит тому, что
— приведенная система вычетов по модулю
. Значит,
.
Докажем теперь, что . В самом деле, числа, меньшие
и взаимно простые с
, образуют приведенную систему вычетов по модулю
. Это следует из леммы.
Определение. Функция Эйлера (или тотиент) обозначает количество чисел, меньших и взаимно простых с
.
Теорема. Если — приведенная система вычетов по модулю
и
— число, взаимно простое с
, то
— тоже приведенная система вычетов по модулю
.
Если — простое, то
.
Лемма. Если — простое, то
.
Доказательство. Действительно, чисел, меньших простого и имеющих с ним общий делитель, всего
.
Лемма. Пусть НОД. Тогда
. Функция Эйлера мультипликативна.
Доказательство. Запишем все числа от до
следующим образом:
Числа в каждой строке образуют полную систему вычетов по модулю . Значит, взаимно простых с
среди них
. При этом эти числа расположены по столбцам — друг под другом, поскольку в каждом столбце стоят числа, сравнимые по модулю
.
Числа в каждом столбце образуют полную систему вычетов по модулю . Действительно,
-й столбец получается, если взять числа
, образующие полную систему вычетов по модулю
, умножить их на число
, взаимно простое с
, и прибавить к каждому из них
.
Таким образом, в каждом столбце ровно чисел, взаимно простых с
.
Так как число будет взаимно простым с тогда и только тогда, когда оно взаимно просто с
и взаимно просто с
, то количество чисел, взаимно простых с
, равно
.
Теорема. Пусть
— каноническое разложение числа . Тогда
Доказательство. По лемме о мультипликативности функции Эйлера
А далее каждое вычисляем по лемме о вычислении функции Эйлера для простых чисел.
Пример.
Теорема (Эйлера). Если
Пусть — какая-нибудь приведенная система вычетов по модулю
.
. Тогда
— тоже приведенная система вычетов по модулю
. Следовательно, каждое из чисел первой последовательности сравнимо с одним из чисел второй последовательности по модулю
, а каждое из чисел второй последовательности сравнимо с одним из чисел первой последовательности. Тогда
Так как каждое из чисел взаимно просто с
, то на них сравнение можно сократить:
Следствие. Пусть – целые числа,
– натуральные. Если
,
, НОД
, то
.
Доказательство. Пусть . Так как
, то
— натуральное число. Тогда
.
Значит, .
Именем Леонарда Эйлера (1707–1783) в современной математике названы: критерий, метод, многочлены, подстановки, постоянная, преобразование, произведение, ряд, теоремы, тождества, уравнения, формулы, функции, характеристика, интегралы, углы, числа и т.д. Гений XVIII в. — Леонард Эйлер — обрел в России вторую родину и проработал в Петербургской академии наук более 30 лет. Французский математик П.С. Лаплас советовал: “Читайте, читайте Эйлера — он учитель нас всех”.
Рассказывают, что однажды Эйлер во время бессонницы вычислил шестую степень первых 100 чисел, а результаты повторил на память через много дней. В другой раз Эйлер, испытывая полученный им ряд, вычислил в течение часа первые 20 десятичных знаков числа .
В 1741 году Эйлер, по приглашению Фридриха II, приезжает из Петербурга в Берлинскую академию наук. Ученого приняли с большими почестями. На одном из королевских приемов во дворце мать короля обратила внимание Эйлера, что он отвечает ей односложно “да” и “нет”. “Почему же Вы не хотите со мной говорить?” — спросила она Эйлера. “Сударыня, — ответил ученый, — я приехал из страны, где тех, кто говорит, вешают”. Ответ Эйлера показывает, в каких трудных условиях приходилось работать в Петербургской академии того времени.
Выдающийся французский математик Пьер Ферма (1601–1665) был по профессии юрист. В теории чисел с его именем связаны знаменитые теоремы: великая теорема Ферма и малая теорема Ферма. В геометрии Ферма явился непосредственным предшественником Декарта. Важную роль сыграл Ферма в зарождении теории вероятности. В трудах Ферма получили систематическое развитие операции дифференцирования и интегрирования. С именем Ферма связано установление вариационного принципа геометрической оптики.
Задачи.
1. Докажите, что если — приведенная система вычетов по модулю
, то
.
2. Докажите,что если — простое число, то
(теорема Вильсона).
3. Докажите, что если — простое число и
, то найдется такое целое число
, что
делится на
.
4. Докажите, что если — целое число и
— нечетный простой делитель числа
, то
.
5. Докажите, что если > — приведенная система вычетов по модулю
, то
.
6. Докажите, что если — приведенная система вычетов по модулю
и существует
, такое что
, то
.
7. Найдите остатки от деления на
.
8. Докажите, что если — целые числа и
делится на
, то
делится на
.
9. Докажите, что если и
— целые числа и
— простое число, то
.
10. Пусть и
— различные простые числа. Докажите, что
.
11. Докажите, что при всех число
не делится на
.
1 Вася Пупкин:
Что-то с версткой не в порядке )
[Ответить]
29 Май 2012, 0:252 Елизавета Александровна Калинина:
У Вас какой браузер? У меня все хорошо (Opera, Explorer).
[Ответить]
29 Май 2012, 8:393 Вася Пупкин:
Google Chrome
[Ответить]
29 Май 2012, 10:344 Константин:
Вы об адаптивном дизайне и верстке ничего не слышали?мда…тяжелый случай
[Ответить]
Елизавета Александровна Калинина Reply:
Ноябрь 18th, 2015 at 22:18
Это должен знать каждый?
Проблему поняла, исправила
[Ответить]
5 Ян Альбертович Дененберг:
Спасибо Вам за интересный урок, уважаемая Елизавета Александровна!
Увы, в израильской школьной программе такого нет.
[Ответить]
30 Январь 2020, 12:01