Полная и приведенная системы вычетов | Математика, которая мне нравится

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

Определение. Числа $a_1,a_2,\dots,a_k$ образуют полную систему вычетов по модулю $m$ , если любое целое число сравнимо по модулю $m$ с одним и только одним из этих чисел.

Любая полная система вычетов по модулю $m$ состоит из $m$ чисел, которые попарно не сравнимы по модулю $m$ .

Теорема. Пусть $a_1,a_2,\ldots,a_m$ — полная система вычетов по модулю $m$ . Пусть $x$ — целое число, взаимно простое с $m$ . Тогда $xa_1,xa_2,\ldots,xa_m$ — тоже полная система вычетов по модулю $m$ .

Доказательство. Нужно доказать, что эти числа попарно не сравнимы по модулю $m$ . Предположим противное. Пусть

$xa_i\equiv xa_k\pmod{m}\qquad(a_i\ne a_k).$

Так как НОД $(x,m)=1$ , то $a_i\equiv a_k\pmod{m}$ , что противоречит условию.

Теорема. Пусть $a_1,a_2,\dots,a_m$ — полная система вычетов по модулю $m$ . Пусть $x$ — целое число. Тогда $x+a_1,x+a_2,\dots,x+a_m$ — тоже полная система вычетов по модулю $m$ .

Лемма. Если $a\equiv b\pmod{m}$ , то НОД $(a,m)=$ НОД $(b,m)$ .

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

$a\equiv b\pmod{m}\Longrightarrow a-b\vdots m\Longrightarrow a-b=km,\ k$ – целое число.

Отсюда $a=b+km,b=a-km$ . Любой общий делитель $a$ и $m$ является делителем $b$ . Отсюда НОД $(a,m)=$ НОД $(b,m)$ .

Определение. Числа $a_1,a_2,\ldots,a_k$ образуют приведенную систему вычетов по модулю $m$ , если они взаимно просты с $m$ и любое целое число, взаимно простое с $m$ , сравнимо с одним и только одним из этих чисел по модулю $m$ .

Пример. Приведенная система вычетов по модулю $10$ : $1,3,7,9$ .

Лемма. Все приведенные системы вычетов по модулю $m$ состоят из одного и того же количества чисел, которое обозначается $\varphi(m)$ — функция Эйлера.

Доказательство. Действительно, пусть есть две приведенные системы вычетов по модулю $m$ , состоящие из разного количества чисел:

$a_1,a_2,\ldots,a_k,\quad b_1,b_2,\ldots,b_l\quad k>l.$

Тогда так как числа $b_1,b_2,\ldots,b_l$ образуют приведенную систему вычетов по модулю $m$ , то каждое из чисел $a_1,\ldots,a_k$ сравнимо с одним и только одним из этих чисел. Поскольку $k>l$ , то, по принципу Дирихле, по крайней мере два числа из $a_1,\ldots,a_k$ будут сравнимы с каким-то числом $b_j$ , а значит, будут сравнимы между собой по модулю $m$ . А это противоречит тому, что $a_1,\ldots,a_k$ — приведенная система вычетов по модулю $m$ . Значит, $k=l$ .

Докажем теперь, что $k=\varphi(m)$ . В самом деле, числа, меньшие $m$ и взаимно простые с $m$ , образуют приведенную систему вычетов по модулю $m$ . Это следует из леммы.

Определение. Функция Эйлера (или тотиент) обозначает количество чисел, меньших $m$ и взаимно простых с $m$ .

Теорема. Если $a_1,a_2,\ldots,a_k$ — приведенная система вычетов по модулю $m$ и $x$ — число, взаимно простое с $m$ , то $xa_1,xa_2,\ldots,xa_k$ — тоже приведенная система вычетов по модулю $m$ .

Если $p$ — простое, то $\varphi(p)=p-1$ .

Лемма. Если $p$ — простое, то $\varphi(p^k)=p^k-p^{k-1}$ .

Доказательство. Действительно, чисел, меньших простого $p$ и имеющих с ним общий делитель, всего $p^k/p=p^{k-1}$ .

Лемма. Пусть НОД $(a,b)=1$ . Тогда $\varphi(ab)=\varphi(a)\varphi(b)$ . Функция Эйлера мультипликативна.

Доказательство. Запишем все числа от $1$ до $ab$ следующим образом:

$\begin{array}{ccccc} 1&2&3&\ldots&a\\ a+1&a+2&a+3&\ldots&2a\\ 2a+1&2a+2&2a+3&\ldots&3a\\ \ldots&&&&\\ (b-1)a+1&(b-1)a+2&(b-1)a+3&\ldots&ab \end{array}$

Числа в каждой строке образуют полную систему вычетов по модулю $a$ . Значит, взаимно простых с $a$ среди них $\varphi(a)$ . При этом эти числа расположены по столбцам — друг под другом, поскольку в каждом столбце стоят числа, сравнимые по модулю $a$ .

Числа в каждом столбце образуют полную систему вычетов по модулю $b$ . Действительно, $i$ -й столбец получается, если взять числа $0,1,\ldots,b-1$ , образующие полную систему вычетов по модулю $b$ , умножить их на число $a$ , взаимно простое с $b$ , и прибавить к каждому из них $i$ .

Таким образом, в каждом столбце ровно $\varphi(b)$ чисел, взаимно простых с $b$ .

Так как число будет взаимно простым с $ab$ тогда и только тогда, когда оно взаимно просто с $a$ и взаимно просто с $b$ , то количество чисел, взаимно простых с $ab$ , равно $\varphi(a)\varphi(b)$ .

Теорема. Пусть

$a=p_1^{k_1}p_2^{k_2}\dots p_n^{k_n}$

— каноническое разложение числа $a$ . Тогда

$\begin{array}{l} \displaystyle \varphi(a)=a\left(1-{1\over p_1}\right)\left(1-{1\over p_2}\right)\ldots \left(1-{1\over p_n}\right)=\\[3mm] \displaystyle =(p^{k_1}-p^{k_1-1})(p_2^{k_2}-p_2^{k_2-1})\dots(p_n^{k_n}-p_n^{k_n-1}). \end{array}$

Доказательство. По лемме о мультипликативности функции Эйлера

$\varphi(p_1^{k_1}p_2^{k_2}\ldots p_n^{k_n})=\varphi(p_1^{k_1})\varphi(p_2^{k_2})\ldots \varphi(p_n^{k_n}).$

А далее каждое $\varphi(p_j^{k_j})$ вычисляем по лемме о вычислении функции Эйлера для простых чисел.

Пример.

$\varphi(4)=2,\varphi(10)=4,\varphi(100)=40,\varphi(1000)=400.$

Теорема (Эйлера). Если x и m — взаимно простые числа, то

$x^{\varphi(m)}\equiv1\pmod{m}.$

Пусть $a_1,a_2,\ldots,a_k$ — какая-нибудь приведенная система вычетов по модулю $m$ . $k=\varphi(m)$ . Тогда $xa_1,xa_2,\dots,xa_k$ — тоже приведенная система вычетов по модулю $m$ . Следовательно, каждое из чисел первой последовательности сравнимо с одним из чисел второй последовательности по модулю $m$ , а каждое из чисел второй последовательности сравнимо с одним из чисел первой последовательности. Тогда

$xa_1\cdot xa_2\cdot\ldots\cdot xa_k\equiv a_1a_2\cdot\ldots\cdot a_k\pmod{m}.$

Так как каждое из чисел $a_1,a_2,\dots,a_k$ взаимно просто с $m$ , то на них сравнение можно сократить:

$\begin{array}{l} x^k\equiv1\pmod{m}\\ x^{\varphi(m)}\equiv1\pmod{m}. \end{array}$

Следствие. Пусть $a,b$ – целые числа, $m,n,p$ – натуральные. Если $a\equiv b\pmod{m}$ , $n\equiv p\pmod{\varphi(m)}$ , НОД $(a,m)=1$ , то $a^n\equiv b^p\pmod{m}$ .

Доказательство. Пусть $n>p$ . Так как $n\equiv p\pmod{\varphi(m)}$ , то $n=p+k\varphi(m), k$ — натуральное число. Тогда

$a^n=a^{p+k\varphi(m)}=a^p\cdot\left(a^{\varphi(m)}\right)^k\equiv a^p\pmod{m}.$

$a^p\equiv b^p\pmod{m}$ .

Значит, $a^n\equiv b^p\pmod{m}$ .

Именем Леонарда Эйлера (1707–1783) в современной математике названы: критерий, метод, многочлены, подстановки, постоянная, преобразование, произведение, ряд, теоремы, тождества, уравнения, формулы, функции, характеристика, интегралы, углы, числа и т.д. Гений XVIII в. — Леонард Эйлер — обрел в России вторую родину и проработал в Петербургской академии наук более 30 лет. Французский математик П.С. Лаплас советовал: “Читайте, читайте Эйлера — он учитель нас всех”.

Рассказывают, что однажды Эйлер во время бессонницы вычислил шестую степень первых 100 чисел, а результаты повторил на память через много дней. В другой раз Эйлер, испытывая полученный им ряд, вычислил в течение часа первые 20 десятичных знаков числа $\pi$ .

В 1741 году Эйлер, по приглашению Фридриха II, приезжает из Петербурга в Берлинскую академию наук. Ученого приняли с большими почестями. На одном из королевских приемов во дворце мать короля обратила внимание Эйлера, что он отвечает ей односложно “да” и “нет”. “Почему же Вы не хотите со мной говорить?” — спросила она Эйлера. “Сударыня, — ответил ученый, — я приехал из страны, где тех, кто говорит, вешают”. Ответ Эйлера показывает, в каких трудных условиях приходилось работать в Петербургской академии того времени.

Выдающийся французский математик Пьер Ферма (1601–1665) был по профессии юрист. В теории чисел с его именем связаны знаменитые теоремы: великая теорема Ферма и малая теорема Ферма. В геометрии Ферма явился непосредственным предшественником Декарта. Важную роль сыграл Ферма в зарождении теории вероятности. В трудах Ферма получили систематическое развитие операции дифференцирования и интегрирования. С именем Ферма связано установление вариационного принципа геометрической оптики.

Задачи.

1. Докажите, что если $a_1,a_2,\ldots,a_s$ — приведенная система вычетов по модулю $m\ge3$ , то $a_1+a_2+\ldots+a_s\equiv0\pmod{m}$ .

2. Докажите,что если $p$ — простое число, то $(p-1)!\equiv-1\pmod{p}$ (теорема Вильсона).

3. Докажите, что если $p$ — простое число и $p\equiv1\pmod{4}$ , то найдется такое целое число $n$ , что $n^2+1$ делится на $p$ .

4. Докажите, что если $n$ — целое число и $p$ — нечетный простой делитель числа $n^2+1$ , то $p\equiv1\pmod{4}$ .

5. Докажите, что если $a_1,a_2,\ldots, a_s$ > — приведенная система вычетов по модулю $m\ge3$ , то $a_1a_2\ldots a_s\equiv\pm1\pmod{m}$ .

6. Докажите, что если $a_1,a_2,\ldots, a_s$ — приведенная система вычетов по модулю $m\ge3$ и существует $x\not\equiv\pm1\pmod{m}$ , такое что $x^2\equiv1\pmod{m}$ , то $a_1a_2\ldots a_s\equiv1\pmod{m}$ .

7. Найдите остатки от деления $2^{2000}$ на $13,25,50$ .

8. Докажите, что если $a,b,c$ — целые числа и $a+b+c$ делится на $30$ , то $a^5+b^5+c^5$ делится на $30$ .

9. Докажите, что если $a,b$ и $c$ — целые числа и $p$ — простое число, то $(a+b)^p\equiv a^p+b^p\pmod{p}$ .

10. Пусть $p$ и $q$ — различные простые числа. Докажите, что $p^{q-1}+q^{p-1}\equiv1\pmod{pq}$ .

11. Докажите, что при всех $n>1$ число $2^n-1$ не делится на $n$ .

Комментарии (RSS) | Трекбек

Комментариев: 6

1 Вася Пупкин:

Что-то с версткой не в порядке )

[Ответить]
29 Май 2012, 0:25
2 Елизавета Александровна Калинина:

У Вас какой браузер? У меня все хорошо (Opera, Explorer).

[Ответить]
29 Май 2012, 8:39
3 Вася Пупкин:

Google Chrome

[Ответить]
29 Май 2012, 10:34
4 Константин:

Вы об адаптивном дизайне и верстке ничего не слышали?мда…тяжелый случай

[Ответить]
Елизавета Александровна Калинина Reply:
Ноябрь 18th, 2015 at 22:18
Это должен знать каждый?

Проблему поняла, исправила

[Ответить]
18 Ноябрь 2015, 21:38
5 Ян Альбертович Дененберг:

Спасибо Вам за интересный урок, уважаемая Елизавета Александровна!
Увы, в израильской школьной программе такого нет.

[Ответить]
30 Январь 2020, 12:01

Математика, которая мне нравится

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

Комментариев: 6

1 Вася Пупкин:

2 Елизавета Александровна Калинина:

3 Вася Пупкин:

4 Константин:

5 Ян Альбертович Дененберг:

Оставьте свой отзыв

Навигация по сайту

Разделы

Новые комментарии

Подписка на обновления сайта