Вычислите по определению функция Эйлера

Предмет: Математика
Раздел: Теория чисел, функция Эйлера

Упражнение 50

Задание: Вычислите по определению \varphi(13), \varphi(14), \varphi(15).

Функция Эйлера \varphi(n) — это количество натуральных чисел, меньших n и взаимно простых с n.

Решение:

1. \varphi(13)
13 — простое число, значит: \varphi(13) = 13 - 1 = 12

2. \varphi(14)
Разложим 14 на простые множители: 14 = 2 \cdot 7
Тогда по формуле Эйлера: \varphi(14) = 14 \cdot \left(1 - \frac{1}{2}\right) \cdot \left(1 - \frac{1}{7}\right) = 14 \cdot \frac{1}{2} \cdot \frac{6}{7} = 7 \cdot \frac{6}{7} = 6

3. \varphi(15)
Разложим 15: 15 = 3 \cdot 5
\varphi(15) = 15 \cdot \left(1 - \frac{1}{3}\right) \cdot \left(1 - \frac{1}{5}\right) = 15 \cdot \frac{2}{3} \cdot \frac{4}{5} = 10 \cdot \frac{4}{5} = 8

Упражнение 51

Теоретическая часть:

Формула Эйлера для произвольного числа n с разложением на простые множители: n = p_1^{k_1} \cdot p_2^{k_2} \cdot \ldots \cdot p_m^{k_m}

Тогда: \varphi(n) = n \cdot \left(1 - \frac{1}{p_1}\right) \cdot \left(1 - \frac{1}{p_2}\right) \cdot \ldots \cdot \left(1 - \frac{1}{p_m}\right)

а) \varphi(27)

27 = 3^3
\varphi(27) = 27 \cdot \left(1 - \frac{1}{3}\right) = 27 \cdot \frac{2}{3} = 18

б) \varphi(1000)

1000 = 2^3 \cdot 5^3
\varphi(1000) = 1000 \cdot \left(1 - \frac{1}{2}\right) \cdot \left(1 - \frac{1}{5}\right) = 1000 \cdot \frac{1}{2} \cdot \frac{4}{5} = 500 \cdot \frac{4}{5} = 400

в) \varphi(2^2 \cdot 3 \cdot 5)

2^2 \cdot 3 \cdot 5 = 4 \cdot 3 \cdot 5 = 60
\varphi(60) = 60 \cdot \left(1 - \frac{1}{2}\right) \cdot \left(1 - \frac{1}{3}\right) \cdot \left(1 - \frac{1}{5}\right) = 60 \cdot \frac{1}{2} \cdot \frac{2}{3} \cdot \frac{4}{5} = 30 \cdot \frac{2}{3} \cdot \frac{4}{5} = 20 \cdot \frac{4}{5} = 16

г) \varphi(3^2 \cdot 4^2 \cdot 5 \cdot 6)

Сначала упростим выражение:

• 3^2 = 9
• 4^2 = 16 = 2^4
• 6 = 2 \cdot 3

Тогда: 3^2 \cdot 4^2 \cdot 5 \cdot 6 = 9 \cdot 16 \cdot 5 \cdot 6 = (3^2) \cdot (2^4) \cdot 5 \cdot (2 \cdot 3) = 2^5 \cdot 3^3 \cdot 5

Теперь применим формулу Эйлера: \varphi(n) = n \cdot \left(1 - \frac{1}{2}\right) \cdot \left(1 - \frac{1}{3}\right) \cdot \left(1 - \frac{1}{5}\right)

Вычислим: n = 2^5 \cdot 3^3 \cdot 5 = 32 \cdot 27 \cdot 5 = 4320
\varphi(4320) = 4320 \cdot \frac{1}{2} \cdot \frac{2}{3} \cdot \frac{4}{5} = 2160 \cdot \frac{2}{3} \cdot \frac{4}{5} = 1440 \cdot \frac{4}{5} = 1152

Ответы:

Упражнение 50:

• \varphi(13) = 12
• \varphi(14) = 6
• \varphi(15) = 8

Упражнение 51:

• а) \varphi(27) = 18
• б) \varphi(1000) = 400
• в) \varphi(60) = 16
• г) \varphi(4320) = 1152