logo
Th_Numb+Combi (2)

§ 9. Функция Эйлера

Для натурального n обозначим через (n) количество взаимно простых с n натуральных чисел на отрезке [0, n – 1]. Таким образом, получается функция : N N, называемая функцией Эйлера.

Примеры: 1. Найдём (1). Отрезок [0; 1–1] = [0; 0] содержит единственное целое число 0, которое взаимно просто с n = 1

Таким образом, (1) = 1.

2. Найдём (2). Для этого рассмотрим отрезок [0; 2–1] = [0; 1], содержащий два целых числа 0, 1, и посчитаем количество взаимно простых с n = 2 чисел в нём:

а

0

1

НОД(a, 2)

2

1

Таким образом, (2) = 1.

3. Найдём (3). Для этого рассмотрим отрезок [0; 3–1] = [0; 2], содержащий три целых числа 0, 1, 2, и вычислим количество взаимно простых с n = 3 чисел в нём:

а

0

1

2

НОД(a, 3)

3

1

1

Таким образом, (3) = 2.

4. Найдём (6). Для этого рассмотрим отрезок [0; 6–1] = [0; 5], содержащий шесть целых чисел 0, 1, 2, 3, 4, 5, и вычислим количество взаимно простых с n = 6 чисел в нём:

а

0

1

2

3

4

5

НОД(a, 6)

6

1

2

3

2

1

Таким образом, (6) = 2.

Теорема (о функции Эйлера). Для любого натурального числа n справедливы следующие утверждения:

(1) (1) = 1,

(2) для простого числа p верно (p) = p – 1,

(3) для любого простого числа p и натурального показателя справедлива формула (р) = р – р–1 = p–1(p – 1) = p(1 – ),

(4) функция Эйлера мультипликативна, т.е. для любыхвзаимно простых чисел m и n верно (mn) = (m)(n),

(5) если , то

.

Доказательство. Докажем лишь некоторые утверждения.

(1) уже доказано.

(2) Пусть p – простое число. Тогда на отрезке [0; p–1] содержатся p целых чисел: 0, 1, 2, … , p – 2, p – 1, из которых ровно одно – 0 делится на p, т.е. НОД(0, p) = p. Остальные не делятся на p, а значит НОД(a, p) = 1 (1 a p–1). Таким образом, (p) = p – 1.

(3) Аналогично предыдущему: расположим p целых чисел из отрезка [0; p –1] в виде таблицы:

0

1

…

p–2

p–1

p

p+1

…

2p–2

2p–1

2p

2p+1

…

3p–2

3p–1

…

…

…

…

…

p–p

p–p+1

…

p–2

p–1

В каждом столбце все числа имеют одинаковые остатки при делении на p: числа 1-го столбца дают остаток 0, числа 2-го столбца – остаток 1, и.т.д., числа последнего столбца – остаток p – 1.

Среди этих чисел p чисел делятся на p только числа первого столбца, т.е. 0p, 1p, … , (p–1 – 1)p, НОД(sp, p) = p (0 s p–1 –1), таких чисел p–1 . Остальные p – p–1 чисел на p не делятся и взаимно просты с p. Таким образом, (p) = p – p–1.

(5) следует из (3) и (4):

(n) = () =()…() =

= .

Теорема доказана.

Примеры: 1. Вычислить (15).

Находим каноническое разложение числа: 15 = 35. Значит,

(15) = (3)(5) = (3 – 1)(5 – 1) = 8.

2. Вычислить (775).

Находим каноническое разложение числа:

ni

775

155

31

1

pi

5

5

31

28,…

12,…

5,…

stop

Таким образом, 775 = 5231. Значит,

(775) = (52)(31) = 5(5 – 1)(31 – 1) = 600.

3. Вычислить (2400).

Находим каноническое разложение числа:

ni

2400

1200

600

300

150

75

25

5

1

pi

2

2

2

2

2

3

5

5

48,…

8,…

stop

Таким образом, 2400 = 25352. Значит,

(155) = (25)(3)(52) = 24254 = 275 = 640.

4. Решить уравнение (x) = 12.

Пусть x = 2p…q , где p, … , q – нечётные простые числа. Тогда при , , … , > 0 получаем (x) = 2–1(p–1)…(q–1)p–1…q–1 = 12 = 223. Поскольку p – 1, q – 1 чётны и > 0, то x = 2p (иначе показатель двойки в левой части больше 2). Ясно, что p = 3, = 2 и = 2, т.е. x = 2232.

Если = 0, то (p–1)…(q–1)p–1…q–1 = 223. Если среди p, … , q нет тройки, то = … = = 1 и (p–1)…(q–1) = 223. В левой части не более двух сомножителей. Если сомножитель один, то x = p = 13. Если сомножителей два, то (p–1)(q–1) = 223, т.е. p – 1 = 2r, q – 1 = 2s и rs = 3. Ясно, что либо r = 1, s = 3, p = 3, q = 7, x = 21, либо r = 3, s = 1, p = 7, q = 3, x = 21.

Таким образом, x = 36, x = 21, x = 13 – все решения уравнения.