Функція Ейлера

Визначення

Функція Ейлера $\phi (n)$ (інколи позначається як $\varphi(n)$ або ${\it phi}(n)$ ) - це кількість чисел від $1$ до $n$ , взаємно простих з $n$ . Іншими словами, це кількість таких чисел у відрізку $[1; n]$ , для яких найбільший спільний дільник з $n$ рівний одиниці.

Декілька перших значення цієї функції (A000010 в енциклопедії OEIS):

\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 \\ \hline \phi(n) & 1 & 1 & 2 & 2 & 4 & 2 & 6 & 4 & 6 & 4 & 10 & 4 & 12 & 6 & 8 \\ \hline \end{array}

Властивості

Трьох наступних властивостей функції Ейлера достатньо, щоб навчитися обчислювати її для будь-яких чисел:

Якщо $p$ - просте число, то $\phi (p)=p-1$ .
Оскільки будь-яке число, крім самого $p$ , взаємно просте з ним.
Якщо $p$ - просте, $a$ - натуральне число, то $\phi (p^a)=p^a-p^{a-1}$ .
Оскільки з числом $p^a$ не взаємно прості тільки числа виду $pk$ $(k \in \mathcal{N})$ , яких $p^a / p = p^{a-1}$ штук.
Якщо $a$ і $b$ взаємно прості, то $\phi(ab) = \phi(a) \phi(b)$ ("мультиплікативність" функції Ейлера).
Цей факт слідує з китайської теореми про остачі. Розглянемо довільне число $z \le ab$ . Позначимо через $x$ і $y$ залишки від ділення $z$ на $a$ і $b$ відповідно. Тоді $z$ взаємно просте з $ab$ тоді і тільки тоді, коли $z$ взаємно просте з $a$ і з $b$ окремо, або, що означає $x$ взаємно просте з $a$ , та $y$ взаємно просте з $b$ . Застосовуючи китайську теорему про остачі, отримаємо, що будь-якій парі чисел $x$ і $y$ $(x \le a, ~ y \le b)$ взаємно однозначно відповідає число $z$ $(z \le ab)$ , що і завершує доведення.

Звідси можна отримати функцію Ейлера для будь-якого $\it n$ через його факторизацію (розкладання $n$ на прості множники):

якщо

n = p_1^{a_1} \cdot p_2^{a_2} \cdot \ldots \cdot p_k^{a_k}

(де всі $p_i$ - прості), то

\phi(n) = \phi(p_1^{a_1}) \cdot \phi(p_2^{a_2}) \cdot \ldots \cdot \phi(p_k^{a_k}) =

= (p_1^{a_1} - p_1^{a_1-1}) \cdot (p_2^{a_2} - p_2^{a_2-1}) \cdot \ldots \cdot (p_k^{a_k} - p_k^{a_k-1}) =

= n \cdot \left( 1-{1\over p_1} \right) \cdot \left( 1-{1\over p_2} \right) \cdot \ldots \cdot \left( 1-{1\over p_k} \right).

Реалізація

Код, що обчислює функцію Ейлера, факторизуючи число за $O(\sqrt n)$ :

int phi(int n) {
    int res = n;
    for (int i = 2; i*i <= n; i++) {
        if (n % i == 0) {
            while (n % i == 0) {
                n /= i;
            }
            res -= res / i;
        }
    }
    if (n > 1) {
        res -= res / n;
    }
    return res;
}

Ключовим моментом при обчисленні функції Ейлера є знаходження факторизації числа $n$ . Її можна знайти за час, значно менший $O(\sqrt{n})$ : див. Ефективні алгоритми факторизації.

Застосування

Найважливіша і найвідоміша властивість функції Ейлера виражається у теоремі Ейлера:

a^{\phi(m)} \equiv 1 \pmod m,

де $\it a$ і $\it m$ взаємно прості.

Зокрема, коли $\it m$ просте, теорема Ейлера перетворюється у так звану малу теорему Ферма:

a^{m-1} \equiv 1 \pmod m

Теорема Ейлера достатньо часто зустрічається на практиці, наприклад, див. Обернений елемент в кільці за модулем.

Визначення​

Властивості​

Реалізація​

Застосування​

Задачі​

Визначення

Властивості

Реалізація

Застосування

Задачі