5. Функция эйлера

Функцией Эйлера от натурального числа nназывается число(n) натуральных чисел, не превосходящихnи взаимно простых сn.

Функция Эйлера мультипликативна: если (m, n) = 1, то(mn) =(m)(n).

Для вычисления функции Эйлера (n) используем каноническое разложение числаnна простые множители. Имеем

() = .

В частности, (p) = p – 1, (p^k)= p^k-1(p – 1).

Пример 5.1. Вычислить функцию Эйлера от чисел 47; 72.

Решение. Имеем(47) = 46;(72) =(2³3²) = 2²(2 – 1)3¹(3 – 1) = 24.

Упражнение5.1. Вычислите(125),(97),(136),(216).

Упражнение5.2. Сколько натуральных чисел в промежутке от 1 до 120, не взаимно простых с 30?

Упражнение5.3. Решите уравнения(5^x) = 100;(7^x) = 294;

(3^x5^y) = 600.

Упражнение5.4.Докажите, что при m  3 значение (m) – число четное.

Упражнение5.5. Решите уравнения(x) = 2;(x) = 4.

6. Сравнения

Числа aиbназываются сравнимыми по модулюm, это записывается в видеa  b(modm), еслиaиbимеют одинаковые остатки при делении наm. Это равносильно условию(a – b) m.

Свойства сравнений:

1. a  b(mod m), c  d(mod m)  a  c  b  d(mod m);

2. a  b(modm),c  d(modm)ac bd(modm);

3. ac bc(modmc)a b(modm);

4. ac bc(modm), (c, m) = 1a b(modm).

Пример 6.1. Найти последнюю цифру числа 27³⁹.

Решение. Число сравнимо со своей последней цифрой поmod10. Поэтому, пользуясь свойствами сравнений, имеем 27_­³⁹7_­³⁹(mod10). Далее находим 7²9, 7³3, 7⁴1(mod10). Поэтому

7³⁹ = 7^49+3 = (7⁴)⁹7³  1⁹3  3 (mod 10).

Последняя цифра числа есть 3.

Упражнение6.1. Найдите последнюю цифру числа 23⁵³; 42³⁵;.

Отношение сравнения по модулю mесть отношение эквивалентности. Числа, сравнимые по модулюm,образуют класс эквивалентности, называемый классом вычетов по модулюm. Число различных классов вычетов по модулюmравноm.

Полной системой вычетов по модулю mназывается система представителей, взятых по одному из каждого класса вычетов по модулюm.

Упражнение6.2. Образуют ли числа: а)17, 21, 120, 34, 58; б) 27, 12, 53, 28, 44, 77 полную систему вычетов по какому-нибудь модулю?

Согласно теореме 2.2 все числа из одного класса вычетов по модулю mимеют один и тот же НОД с модулемm. Поэтому если одно число из класса вычетов взаимно просто с модулем, то все числа из этого класса будут взаимно просты с модулем. Такой класс вычетов называется взаимно простым с модулем.

Приведенной системой вычетов по модулю mназывается система представителей, взятых по одному из каждого класса вычетов, взаимно простого сm.

Приведенная система вычетов по модулю mсодержит(m) элементов.

Теорема 6.1(Эйлер). Если (a, m) = 1, тоa^(m)1(modm).

Теорема 6.2(Ферма). Еслиp – простое,aне делится наp, тоa^p-1 1(modp).

Пример 6.2. Найти две последних цифры числа 233⁸⁹.

Решение. Чтобы найти две последних цифры числа, следует рассматривать сравнение по модулю 100. Имеем (233, 100) = 1,(100) = 40, и по теореме Эйлера 233⁴⁰1(mod100). Поэтому

233⁸⁹  233^402+9 (233⁴⁰)²233⁹ 233⁹ 33⁹ (mod 100).

Далее вычисляем

33² = 108989 (mod 100);

33⁴ = (33²)² 89²= 792121(mod 100);

33⁸ = (33⁴)² 21²= 44141(mod 100);

33⁹ = 33⁸33  4133 = 1353  53(mod 100).

Значит, наше число оканчивается на 53.

Упражнение6.3. Докажите, что:

а) a¹² – 1  7, если (а, 7) = 1;

б) a¹² – b¹²  65, если (а, 65) = (b, 65) = 1;

в) а⁵⁶¹  а (mod 11).