Как найти функцию Эйлера: разбор на числе 7560

Дано: число $n = 7560$. Найти: значение функции Эйлера $\varphi(7560)$, то есть количество чисел от 1 до 7560, взаимно простых с 7560.

Функция Эйлера считается не перебором, а по разложению числа на простые множители: каждое различное простое в разложении вносит в ответ свою скобку. Здесь $7560 = 2^3 \cdot 3^3 \cdot 5 \cdot 7$, и после четырёх скобок получается ответ $\varphi(7560) = 1728$. Калькулятор сверху проделывает этот каскад для любого числа и показывает, сколько отрезает каждый простой делитель; ниже - то же решение по шагам.

Решение по шагам

Дано. $n = 7560$.

Найти. $\varphi(7560)$ - количество натуральных $k$ из промежутка от 1 до 7560, для которых $\gcd(k, 7560) = 1$.

Шаг 1. Раскладываем число на простые множители. Без канонического разложения формула не работает вовсе, поэтому это всегда первый шаг. Делим на простые по возрастанию, пока делится:

$$7560 = 2 \cdot 3780 = 2^2 \cdot 1890 = 2^3 \cdot 945 = 2^3 \cdot 3^3 \cdot 35 = 2^3 \cdot 3^3 \cdot 5 \cdot 7.$$

Техника перебора делителей до квадратного корня подробно разобрана в задаче про разложение на простые множители, здесь она нужна только как заготовка. Важен результат: различных простых делителей ровно четыре - это 2, 3, 5 и 7, а их показатели 3, 3, 1 и 1 на формулу влияют только через само число $n$.

Шаг 2. Выписываем формулу. Значение функции Эйлера равно исходному числу, умноженному на скобки вида «единица минус единица на простое», по одной скобке на каждый различный простой делитель:

$$\varphi(n) = n \prod_{p \mid n} \left(1 - \frac{1}{p}\right).$$

Подставляем наши четыре простых:

$$\varphi(7560) = 7560 \left(1 - \frac{1}{2}\right)\left(1 - \frac{1}{3}\right)\left(1 - \frac{1}{5}\right)\left(1 - \frac{1}{7}\right).$$

Шаг 3. Считаем каскадом, а не дробями. Перемножать четыре дроби подряд неудобно и легко ошибиться. Гораздо надёжнее на каждом простом сначала разделить на $p$, а потом умножить на $p - 1$: деление всегда идёт нацело, промежуточные значения остаются целыми.

$$\begin{aligned} 7560 : 2 \cdot 1 &= 3780, \\ 3780 : 3 \cdot 2 &= 2520, \\ 2520 : 5 \cdot 4 &= 2016, \\ 2016 : 7 \cdot 6 &= 1728. \end{aligned}$$

Именно этот каскад рисует график калькулятора в режиме «каскад формулы»: видно, что двойка отрезает половину, тройка ещё треть остатка, а семёрка забирает совсем немного.

Шаг 4. Проверяем мультипликативностью. Есть независимый способ получить тот же ответ. Числа $8$, $27$, $5$ и $7$ попарно взаимно просты, поэтому функция Эйлера их произведения равна произведению значений:

$$\varphi(8) = 8 - 4 = 4, \quad \varphi(27) = 27 - 9 = 18, \quad \varphi(5) = 4, \quad \varphi(7) = 6,$$ $$\varphi(7560) = 4 \cdot 18 \cdot 4 \cdot 6 = 1728.$$

Ответы сошлись, значит в разложении и в арифметике ошибок нет.

Ответ. $\varphi(7560) = 1728$. Из 7560 вычетов взаимно просты с модулем 1728 штук, то есть около 22,86 процента.

Формула и откуда она берётся

По определению $\varphi(n)$ - это количество чисел от 1 до $n$, не имеющих с $n$ общих делителей, кроме единицы. Проверка взаимной простоты каждой пары делается алгоритмом Евклида, но перебирать все 7560 значений никто не заставляет: формула сокращает работу до разложения на множители.

Начнём с простого числа. Если $n = p$ простое, то общий делитель с ним может быть только 1 или $p$, а само $p$ в промежуток до $p$ входит и взаимно простым с собой не является. Значит, подходят все остальные, и $\varphi(p) = p - 1$: например, $\varphi(7) = 6$, а $\varphi(97) = 96$. Проверить простоту кандидата помогает разбор про проверку числа на простоту.

Дальше степень простого. Среди чисел от 1 до $p^k$ не взаимно просты с $p^k$ ровно те, что делятся на $p$, а их ровно $p^{k-1}$ штук. Вычитаем их и получаем

$$\varphi(p^k) = p^k - p^{k-1} = p^{k-1}(p - 1) = p^k\left(1 - \frac{1}{p}\right).$$

Отсюда $\varphi(8) = 8 - 4 = 4$, $\varphi(27) = 27 - 9 = 18$, $\varphi(81) = 81 - 27 = 54$. Обрати внимание: вычитается не единица, а целая доля кратных.

Последний кирпич - мультипликативность. Если $m$ и $k$ взаимно просты, то $\varphi(mk) = \varphi(m)\varphi(k)$. Смысл в том, что остаток по модулю $mk$ однозначно восстанавливается по паре остатков по модулям $m$ и $k$, и взаимная простота с произведением равносильна взаимной простоте с каждым сомножителем отдельно. Соединив три факта, получаем общую формулу: раскладываем число на степени простых, для каждой берём свою скобку и перемножаем.

Опорные случаи в одной таблице

Почти все учебные задания сводятся к нескольким типовым ситуациям, и различать их стоит сразу, ещё на этапе разложения.

Последняя строка показательна: $1000 = 2^3 \cdot 5^3$, различных простых всего два, поэтому ответ $1000 \cdot \tfrac12 \cdot \tfrac45 = 400$. Число большое, а значение функции Эйлера довольно скромное - величина $n$ сама по себе ничего не решает, решает состав делителей. Переключи график калькулятора в режим «разброс значений»: у соседних чисел значения прыгают вдвое, простые сидят на верхней границе, а числа вроде 7560 с четырьмя разными простыми проваливаются глубоко вниз.

Теорема Эйлера и зачем всё это считают

Функцию Эйлера редко ищут ради самого числа: она нужна как показатель степени. Теорема Эйлера утверждает, что при $\gcd(a, n) = 1$ выполнено

$$a^{\varphi(n)} \equiv 1 \pmod n.$$

Для нашего числа это значит, что $11^{1728}$ даёт остаток 1 при делении на 7560 - возводить в степень не нужно, ответ известен заранее. На маленьких числах то же самое видно глазами: $\varphi(10) = 4$ и $3^4 = 81 = 8 \cdot 10 + 1$. Когда $n = p$ простое, $\varphi(p) = p - 1$, и теорема превращается в малую теорему Ферма.

Условие взаимной простоты снимать нельзя. Для $a = 6$ и $n = 10$ любая степень шестёрки чётна, остаток по чётному модулю тоже чётен, единицей он не станет никогда. Именно поэтому теорема говорит не про все основания, а ровно про те $\varphi(n)$ вычетов, которые обратимы по модулю $n$.

Практический выход - асимметричная криптография. В RSA модуль равен произведению двух простых, значение функции Эйлера считается как $(p-1)(q-1)$, и закрытый ключ получается из открытого по модулю этого числа; пошаговый разбор с конкретными $p$ и $q$ есть в задаче про генерацию ключей RSA. Стойкость держится на асимметрии: зная разложение, $\varphi(n)$ считают за секунду, а не зная - задача упирается в факторизацию большого числа.

Как проверить полученный ответ

Первый способ годится для маленьких чисел: просто перебрать. Для $n = 12$ взаимно просты с числом только 1, 5, 7 и 11, то есть $\varphi(12) = 4$, и формула даёт то же самое: $12 \cdot \tfrac12 \cdot \tfrac23 = 4$. Если на маленьком примере формула и перебор разошлись, ошибка почти всегда в разложении.

Второй способ работает и для больших чисел. Сумма значений функции Эйлера по всем делителям числа равна самому числу:

$$\sum_{d \mid n} \varphi(d) = n.$$

Для $n = 12$ делители это 1, 2, 3, 4, 6, 12, а их значения 1, 1, 2, 2, 2, 4, и в сумме ровно 12. Тождество удобно тем, что проверяет не одно значение, а всю цепочку сразу.

Третий способ - грубая оценка. Значение $\varphi(n)$ всегда меньше $n$ и для любого $n > 2$ чётно, потому что каждый нечётный простой делитель вносит чётный множитель $p - 1$. Если в ответе получилось нечётное число вроде 1727, можно не перепроверять выкладки: ответ точно неверный.

Частые ошибки

• Пишут $\varphi(n) = n - 1$ для составного числа. Формула $p - 1$ верна только для простого $p$. Для 7560 она дала бы 7559 вместо 1728 - разница в четыре с лишним раза.
• Берут скобку на каждое вхождение простого. В разложении $2^3 \cdot 3^3 \cdot 5 \cdot 7$ шесть множителей, но различных простых всего четыре, и скобок тоже четыре. Лишние скобки по двойке и тройке занизили бы ответ до 576.
• Для степени простого вычитают единицу. Правильно $\varphi(27) = 27 - 9 = 18$, а не $27 - 1 = 26$: выбывают все кратные тройке, а их девять.
• Применяют мультипликативность к не взаимно простым множителям. $\varphi(24) = 8$, но $\varphi(4)\varphi(6) = 2 \cdot 2 = 4$, потому что у 4 и 6 есть общий делитель 2. Разбивать число надо на степени разных простых, а не на любые сомножители.
• Перемножают дроби и теряют точность. Считать $0{,}5 \cdot 0{,}667 \cdot 0{,}8 \cdot 0{,}857$ в столбик - верный способ получить 1727,9. Каскад «разделить на $p$, умножить на $p - 1$» всегда даёт целое.
• Забывают, что при неполном разложении ответ неверен. Если число 7560 разложить до $2^3 \cdot 945$ и остановиться, формула даст 3780: пропущенные простые 3, 5 и 7 свои скобки не внесут.

FAQ

Чему равно $\varphi(1)$? По соглашению $\varphi(1) = 1$: в промежутке от 1 до 1 есть единственное число, и $\gcd(1, 1) = 1$. Это не частный случай формулы, а именно договорённость, зато с ней тождество суммы по делителям работает без оговорок.

Всегда ли значение функции Эйлера чётно? Для всех $n > 2$ да. Если у числа есть нечётный простой делитель $p$, ответ содержит чётный множитель $p - 1$; если же $n = 2^k$ при $k \geqslant 2$, то $\varphi(n) = 2^{k-1}$ и тоже чётно. Нечётные значения бывают только у $n = 1$ и $n = 2$, там $\varphi = 1$.

Можно ли найти $\varphi(n)$, не раскладывая число на множители? Для учебных чисел проще всего разложить, для больших - практически нет. Знание $\varphi(n)$ для $n = pq$ равносильно знанию самих $p$ и $q$: из системы «сумма и произведение» они восстанавливаются квадратным уравнением. Поэтому быстрый способ вычислить $\varphi$ означал бы быструю факторизацию, а на её отсутствии и держится RSA.

Чем функция Эйлера отличается от числа делителей? Число делителей считает, сколько чисел делят $n$, а функция Эйлера - сколько чисел с $n$ общих делителей не имеют. У 7560 делителей 64, а взаимно простых с ним вычетов 1728. Обе величины читаются из одного разложения, но по разным правилам: для делителей перемножают показатели, увеличенные на единицу, а для функции Эйлера - скобки по простым.

Коротко

1. Раскладываем число на простые: $7560 = 2^3 \cdot 3^3 \cdot 5 \cdot 7$, различных простых делителей четыре.
2. Применяем формулу $\varphi(n) = n \prod (1 - 1/p)$, по одной скобке на каждое различное простое, а не на каждый множитель разложения.
3. Считаем каскадом с целыми числами: $7560 \to 3780 \to 2520 \to 2016 \to 1728$, деля на $p$ и умножая на $p - 1$.
4. Проверяем мультипликативностью: $\varphi(8)\varphi(27)\varphi(5)\varphi(7) = 4 \cdot 18 \cdot 4 \cdot 6 = 1728$, ответы совпали.
5. Ответ: $\varphi(7560) = 1728$, то есть 22,86 процента вычетов обратимы по модулю 7560, и для любого взаимно простого $a$ выполнено $a^{1728} \equiv 1 \pmod{7560}$.