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_iequiv xa_kpmod{m}qquad(a_ine a_k).]

Так как НОД(x,m)=1, то a_iequiv a_kpmod{m}, что противоречит условию.

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

Лемма. Если aequiv bpmod{m}, то НОД(a,m)=НОД(b,m).

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

aequiv bpmod{m}Longrightarrow a-bvdots mLongrightarrow 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_lquad 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)=aleft(1-{1over p_1}right)left(1-{1over p_2}right)ldots left(1-{1over 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)}equiv1pmod{m}.]

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

    [xa_1cdot xa_2cdotldotscdot xa_kequiv a_1a_2cdotldotscdot a_kpmod{m}.]

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

    [begin{array}{l} x^kequiv1pmod{m}\ x^{varphi(m)}equiv1pmod{m}. end{array}]

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

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

    [a^n=a^{p+kvarphi(m)}=a^pcdotleft(a^{varphi(m)}right)^kequiv a^ppmod{m}.]

a^pequiv b^ppmod{m}.

Значит, a^nequiv b^ppmod{m}.

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

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

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

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

Задачи.

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

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

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

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

5. Докажите, что если a_1,a_2,ldots, a_s> — приведенная система вычетов по модулю mge3, то a_1a_2ldots a_sequivpm1pmod{m}.

6. Докажите, что если a_1,a_2,ldots, a_s — приведенная система вычетов по модулю mge3 и существует xnotequivpm1pmod{m}, такое что x^2equiv1pmod{m}, то a_1a_2ldots a_sequiv1pmod{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)^pequiv a^p+b^ppmod{p}.

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

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

Ссылка на основную публикацию