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. 1 Вася Пупкин:

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

    [Ответить]

    29 Май 2012, 0:25

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

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

    [Ответить]

    29 Май 2012, 8:39

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

    Google Chrome

    [Ответить]

    29 Май 2012, 10:34

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

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

    [Ответить]

    Елизавета Александровна Калинина Reply:
    Ноябрь 18th, 2015 at 22:18

    Это должен знать каждый? :-)

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

    [Ответить]

    18 Ноябрь 2015, 21:38

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

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

    [Ответить]

    30 Январь 2020, 12:01

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

Добавить изображение