Обсуждение участника:MetaMockery

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

Определение:

Функция Эйлера [math]\varphi (n) [/math] определяется как количество натуральных чисел, не превосходящих [math]n[/math] и взаимно простых с [math]n[/math].

Определение:

Функция [math]f : \mathbb{N} \to \mathbb{Z} [/math] называется мультипликативной, если [math]f(mn) = f(m)f(n)[/math] для любых взаимно простых [math]m, n[/math].

Теорема (Мультипликативность функции Эйлера):

Для любых взаимно простых чисел [math]m, n[/math] [math]\varphi(mn)=\varphi(m)\varphi(n)[/math]

Доказательство:

[math]\triangleright[/math]

Запишем [math]n \cdot m[/math] натуральных чисел, не превосходящих [math]n \cdot m[/math], в виде прямоугольной таблицы с [math]n[/math] столбцами и [math]m[/math] строками, располагая первые [math]n[/math] чисел в первой строке, вторые [math]n[/math] чисел во второй и т.д. Поскольку [math]n[/math] и [math]m[/math] взаимно просты, то целое [math]s[/math] взаимно просто с [math]n \cdot m[/math] тогда и только тогда, когда оно взаимно просто как с [math]n[/math], так и с [math]m[/math]. Итак, нужно доказать, что количество чисел в таблице, взаимно простых с [math]n[/math] и с [math]m[/math] равно [math]\varphi(m)\varphi(n)[/math]. В данном доказательстве мы используем тот факт, что число [math]s[/math] взаимно просто с натуральным [math]k[/math] тогда и только тогда, когда остаток деления [math]s[/math] на [math]k[/math] тоже взаимно прост с [math]k[/math]. Данный факт довольно очевиден и используется в Алгоритме Евклида. Теперь приступим непосредственно к доказательству. Число находящееся в [math]i[/math]-ой строке и [math]j[/math]-ом столбце нашей таблицы можно представить в виде [math]n(i - 1) + j[/math]. Если это число взаимно просто с [math]n[/math], то и остаток этого числа по модулю [math]n[/math] тоже взаимно прост с [math]n[/math]. Но тогда и все числа в данном столбце тоже взаимно просты с [math]n[/math], так как весь столбец можно представить в виде арифметической прогрессии с разностью [math]n[/math], а при добавлении [math]n[/math] остаток деления по модулю [math]n[/math] не меняется. Поэтому, числа взаимно простые с [math]n[/math] в таблице занимают ровно [math]\varphi(n)[/math] столбцов. Перед тем как продолжить доказательство, давайте рассмотрим небольшое утверждение. Пусть нам даны [math]m[/math] последовательных членов арифметической прогрессии [math]a, a + d, \dots , a + (m - 1)d[/math]. Тогда, если [math](d, m) = 1[/math], то остатки всех этих [math]m[/math] чисел по модулю [math]m[/math] разные, а значит образуют все множество остатков [math]\{0, \dots , m - 1\}[/math], причем каждый остаток получается ровно из одного из членов прогрессии. Воспользуемся данным утверждением, подставив разность арифметической прогресии [math]d = n[/math]. Тогда в каждом из [math]\varphi(n)[/math] столбцов есть ровно [math]\varphi(m)[/math] чисел, взаимно простых с [math]m[/math]. Следовательно всего чисел, взаимно простых и с [math]n[/math] и с [math]m[/math] равно [math]\varphi(m)\varphi(n)[/math], что и требовалось доказать.

[math]\triangleleft[/math]

Функции [math]\sigma(n)[/math], [math]\tau(n)[/math] и [math]\varphi(n)[/math], их мультипликативность и значения

Каноническое разложение числа [math]\displaystyle n = \prod_{i=1}^{r}p_i^{s_i} [/math], где [math]r[/math] — количество простых делителей числа [math]n[/math], [math]p_i[/math] — [math]i[/math]-ый простой делитель, [math]s_i[/math] — максимальная степень вхождения этого простого делителя.

Функция [math]\sigma(n)[/math]

Функция [math]\sigma : \mathbb{N} \to \mathbb{N} [/math] определяется как сумма делителей натурального числа [math]n[/math]:

[math]\displaystyle\sigma(n) = \sum_{d | n}d [/math]

Если [math]m[/math] и [math]n[/math] взаимно просты, то каждый делитель произведения [math]mn[/math] может быть единственным образом представлен в виде произведения делителей [math]m[/math] и делителей [math]n[/math], и обратно, каждое такое произведение является делителем [math]mn[/math]. Отсюда следует, что функция [math]\sigma(n)[/math] мультипликативна:

Для простого числа [math]p[/math] легко посчитать [math]\displaystyle\sigma(p) = p + 1[/math]. При этом легко обобщается для некоторой степени [math]p[/math]:

[math]\displaystyle\sigma(p^s) = \sum_{k=0}^{s}p^k = \frac{p^{s + 1} - 1}{p - 1} [/math]

В силу мультипликативности функции:

[math] \displaystyle \sigma (n) = \prod_{i = 1}^{r}{\frac{p_{i}^{s_i+1}-1} {p_{i}-1}} [/math]

Функция [math]\tau(n)[/math]

Функция [math]\tau: \mathbb{N} \to \mathbb{N} [/math] определяется как число положительных делителей натурального числа [math]n[/math]:

[math]\displaystyle\tau(n) = \sum_{d | n}1 [/math]

Если [math]m[/math] и [math]n[/math] взаимно просты, то каждый делитель произведения [math]mn[/math] может быть единственным образом представлен в виде произведения делителей [math]m[/math] и делителей [math]n[/math], и обратно, каждое такое произведение является делителем [math]mn[/math]. Отсюда следует, что функция [math]\tau(n)[/math] мультипликативна:

[math]\tau(mn)=\tau(m)\tau(n)[/math]

Для простого числа [math]p[/math] легко посчитать [math]\displaystyle\tau(p) = 2[/math]. При этом легко обобщается для некоторой степени [math]p[/math]:

[math]\displaystyle\tau(p^s) = s + 1 [/math]

В силу мультипликативности функции:

[math] \displaystyle \tau(n) = \prod_{i = 1}^{r}(s_i + 1) [/math]

Функция [math]\varphi(n)[/math]

Для простого числа [math]p[/math] легко посчитать [math]\displaystyle\varphi(p) = p - 1[/math]. На некоторую степень [math]p[/math] формулу можно обобщить:

[math]\displaystyle\varphi(p^s) = p^s - p^{s - 1} [/math]

Обосновывается следующим образом: Все не взаимно простые с [math]p^s[/math] числа в диапазоне от 1 до [math]p^s[/math], очевидно, кратны [math]p[/math]. Всего таких чисел [math]p^{s - 1}[/math].

В силу мультипликативности функции:

[math] \displaystyle \varphi(n) = \prod_{i = 1}^{r}(p_i^{s_i} - p_i^{s_i - 1}) = \prod_{i = 1}^{r}p_i^{s_i}(1 - \frac{1}{p_i}) = n\prod_{i = 1}^{r}(1 - \frac{1}{p_i}) [/math]

Малая теорема Ферма и теорема Эйлера

Теорема (Теорема Эйлера):

Если [math]n[/math] и [math]a[/math] — взаимно простые целые числа, то [math]a^{\varphi(n)} \equiv 1 \ (mod \ n)[/math]

Доказательство:

[math]\triangleright[/math]

Число [math]\overline{x}[/math] называется вычетом по модулю [math]n[/math], если [math]\overline{x} \equiv x \ (mod \ n)[/math]. Вычет [math]\overline{x}[/math] называется обратимым вычетом, если существует вычет [math]\overline{y}[/math], такой что [math]\overline{x}\overline{y} \equiv 1 \ (mod \ n)[/math]. Заметим, что вычет [math]\overline{x}[/math] обратим тогда и только тогда, когда [math]\overline{x}[/math] и [math]n[/math] взаимно просты. Это обосновывается тем, что данное выражение можно представить в виде линейного диофантово уравнения второго порядка [math]\overline{x}\cdot\overline{y} + m \cdot n = 1[/math]. Как видно из статьи, решение существует только при [math](\overline{x}, n) = 1[/math]. В таком случае, у числа [math]n[/math] существует всего [math]\varphi(n)[/math] обратимых вычетов. Пусть [math]\mathbb{Z}_{n}^{*}[/math] — множество всех обратимых вычетов по модулю [math]n[/math]. Достаточно доказать данную теорему только для вычетов, так как мы знаем, что если остаток числа [math]a[/math] по модулю [math]n[/math] взаимно прост с [math]n[/math], то и само число взаимно просто с [math]n[/math]. Напомним, что данный факт был ранее доказан в доказательстве мультипликативности функции Эйлера. Рассмотрим вычеты по модулю [math]n[/math]. Так как [math]n[/math] и [math]a[/math] взаимно просты, то вычет [math]\overline{a}[/math] обратим. Пусть [math]\overline{b_1}, \overline{b_2}, \dots , \overline{b_{\varphi(n)}}[/math] — все обратимые вычеты по модулю [math]n[/math]. Тогда вычет [math]\overline{b} = \overline{b_1}\overline{b_2}\dots\overline{b_{\varphi(n)}}[/math], равный произведению всех обратимых вычетов, тоже обратим. Заметим, что отображение [math]\mathbb{Z}_{n}^{*} \to \mathbb{Z}_{n}^{*}[/math], заданное формулой [math]\overline{x} \mapsto \overline{a}\cdot\overline{x}[/math] является биекцией. Действительно, мы просто умножаем каждый остаток на какую-то константу, от этого множество вычетов не изменится. В таком случае в выражении [math] \overline{a}^{\varphi(n)}\overline{b} = (\overline{a} \overline{b_1}) \dots (\overline{a} \overline{b_{\varphi(n)}}) [/math], в правой части стоит произведение всех обратимых вычетов, но взятое в другом порядке. Тогда [math]\overline{a}^{\varphi(n)}\overline{b} = \overline{b}[/math]. Умножая обе части на вычет, обратный к [math]\overline{b}[/math], получим, что [math]\overline{a}^{\varphi(n)} \equiv 1 \ (mod \ n) [/math], что и требовалось доказать.

[math]\triangleleft[/math]

Следствием теоремы Эйлера является малая теорема Ферма. У нее также есть доказательство без использования более общей теоремы Эйлера, однако его мы приводить не будем.

Теорема (Малая теорема Ферма):

Если целое число [math]a[/math] и простое число [math]p[/math] — взаимно просты, то [math]a^{p - 1} \equiv 1 \ (mod \ p)[/math]

Доказательство:

[math]\triangleright[/math]

Так как [math]p[/math] — простое, то [math]\varphi(p) = p - 1[/math]. Воспользуемся теоремой Эйлера, тогда [math]a^{\varphi(p)} = a^{p - 1} \equiv 1 \ (mod \ p)[/math], что и требовалось доказать.

[math]\triangleleft[/math]

Различные свойства функции Эйлера

Теорема:

Если для каких-то натуральных чисел [math]a[/math] и [math]b[/math] верно, что [math]a\,|\,b[/math], тогда верно и [math]\varphi(a)\,|\, \varphi(b)[/math]

Доказательство:

[math]\triangleright[/math]

Воспользуемся формулой для [math] \displaystyle \varphi(n) = \prod_{i = 1}^{r}(p_i^{s_i} - p_i^{s_i - 1}) = \prod_{i = 1}^{r}p_i^{s_i - 1}(p_i - 1) [/math]. [math]a = p_1^{\alpha_1} \cdot\ldots\cdot p_{r_a}^{\alpha_{r_a}},[/math] [math]b = p_1^{\beta_1} \cdot\ldots\cdot p_{r_b}^{\beta_{r_b}}[/math] При этом, так как [math]a\,|\,b[/math], то [math]r_a \leq r_b[/math], а также [math]\forall i \in [1\, ;\, r_a] \ \alpha_i \leq \beta_i[/math] [math][/math] Значит [math]\displaystyle\frac{\varphi(b)}{\varphi(a)}[/math][math]\displaystyle = \frac{\displaystyle\prod_{i = 1}^{r_b}p_i^{\beta_i - 1}(p_i - 1)}{\displaystyle\prod_{i = 1}^{r_a}p_i^{\alpha_i - 1}(p_i - 1)} = \displaystyle(\prod_{i = 1}^{r_a}p_i^{\beta_i - \alpha_i}) \cdot \displaystyle(\prod_{i = r_a + 1}^{r_b}p_i^{\beta_i - 1}(p_i - 1))[/math], а значит [math]\varphi(a)\,|\, \varphi(b)[/math], что и требовалось доказать.

[math]\triangleleft[/math]

Теорема:

Для любого натурального числа [math]n[/math] выполнено равенство [math]\displaystyle n = \sum_{d | n} \varphi(d)[/math]

Доказательство:

[math]\triangleright[/math]

Данную теорему можно доказать разложив по формуле [math]\varphi(d)[/math], а можно более элегантно: Рассмотрим [math]n[/math] дробей [math]\frac{1}{n}, \frac{2}{n}, \dots , \frac{n}{n}[/math]. Каждую дробь представим в виде несократимой дроби [math]\frac{p}{q}[/math]. Заметим, что множество значений [math]q[/math] — это множество делителей числа [math]n[/math]. Так как дробь [math]\frac{p}{q}[/math] несократима, то [math]p[/math] и [math]q[/math] взаимно просты. Зная, что [math]p \leq q[/math], легко понять, что всего дробей со знаменателем [math]q[/math] ровно [math]\varphi(q)[/math]. Так как, все [math]n[/math] дробей мы представили в несократимом виде, где знаменатель является делителем [math]n[/math], то [math]\displaystyle \sum_{d | n} \varphi(d) = n[/math], так как всего дробей [math]n[/math], что и требовалось доказать.

[math]\triangleleft[/math]

Теорема (Обобщённая мультипликативность):

Пусть [math]n[/math] и [math]m[/math] — любые два натуральных числа, а [math]d = (n,\ m)[/math], тогда: [math]\varphi(m \cdot n) = \varphi(m) \cdot \varphi(n)\cdot\frac{d}{\varphi(d)}[/math]

Доказательство:

[math]\triangleright[/math]

Пусть [math](m,\,n)=d,[/math] тогда [math]m = m'd, \; n = n'd,[/math] причем в общем случае [math](m',\,d) \neq 1[/math] и [math](n',\,d) \neq 1.[/math] Поэтому можно записать: [math]d = d_1^{\delta_1} \cdot\ldots\cdot d_k^{\delta_k} \cdot d_{k+1}^{\delta_{k+1}} \cdot\ldots\cdot d_{K}^{\delta_{K}},[/math] [math]m' = d_1^{\alpha_1} \cdot\ldots\cdot d_k^{\alpha_k} \cdot p_1^{\beta_1} \cdot\ldots\cdot p_r^{\beta_r},[/math] [math]n' = d_{k+1}^{\gamma_{k+1}} \cdot\ldots\cdot d_{K}^{\gamma_{K}} \cdot q_1^{\varepsilon_1} \cdot\ldots\cdot q_s^{\varepsilon_s}.[/math] Здесь первые [math]k[/math] делителей [math]d[/math] являются также делителями [math]m',[/math] а последние [math]K-k[/math] делителей [math]d[/math] являются делителями [math]n'.[/math] Распишем: [math]\varphi(mn)= \varphi(d^2 \cdot m'n') = \varphi((d_1^{\delta_1} \cdot\ldots\cdot d_k^{\delta_k} \cdot d_{k+1}^{\delta_{k+1}} \cdot\ldots\cdot d_{K}^{\delta_{K}})^2 \cdot d_1^{\alpha_1} \cdot\ldots\cdot d_k^{\alpha_k} \cdot p_1^{\beta_1} \cdot\ldots\cdot p_r^{\beta_r} \cdot d_{k+1}^{\gamma_{k+1}} \cdot\ldots\cdot d_{K}^{\gamma_{K}} \cdot q_1^{\varepsilon_1} \cdot\ldots\cdot q_s^{\varepsilon_s}).[/math] В силу мультипликативности функции Эйлера, а также с учётом формулы [math]\varphi(p^n) = p^n(1-\frac{1}{p}),[/math] где [math]p[/math] — простое, получаем: [math] \begin{align} \varphi(mn) &= d_1^{\alpha_1+\delta_1}\left(1-\frac{1}{d_1}\right) \cdot\ldots\cdot d_k^{\alpha_k+\delta_k}\left(1-\frac{1}{d_k}\right) \cdot p_1^{\beta_1}\left(1-\frac{1}{p_1}\right) \cdot\ldots\cdot p_r^{\beta_r}\left(1-\frac{1}{p_r}\right) \cdot d_{k+1}^{\delta_{k+1}}\left(1-\frac{1}{d_{k+1}}\right) \cdot\ldots\cdot d_{K}^{\delta_{K}}\left(1-\frac{1}{d_{K}}\right)\times \\ &\; \times \; d_{k+1}^{\gamma_{k+1}+\delta_{k+1}}\left(1-\frac{1}{d_{k+1}}\right) \cdot\ldots\cdot d_{K}^{\gamma_{K}+\delta_{K}}\left(1-\frac{1}{d_{K}}\right) \cdot q_1^{\varepsilon_1}\left(1-\frac{1}{q_1}\right) \cdot\ldots\cdot q_s^{\varepsilon_s}\left(1-\frac{1}{q_s}\right) \cdot d_1^{\delta_1}\left(1-\frac{1}{d_1}\right) \cdot\ldots\cdot d_{k+1}^{\delta_{k+1}}\left(1-\frac{1}{d_{k+1}}\right)\times \\ &\; \times \; \frac{1}{\left(1-\frac{1}{d_1}\right) \cdot\ldots\cdot \left(1-\frac{1}{d_K}\right)} \end{align} [/math] В первой строке записано [math]\varphi(m),[/math] во второй — [math]\varphi(n),[/math] а третью можно представить, как [math]\frac{d}{\varphi(d)}.[/math] Поэтому: [math]\varphi(m \cdot n) = \varphi(m) \cdot \varphi(n) \cdot \frac{d}{\varphi(d)}[/math]

[math]\triangleleft[/math]

Применение теоремы Эйлера в других задачах

Задача об ожерельях

Задача:

Требуется посчитать количество ожерелий из [math]n[/math] бусинок, каждая из которых может быть покрашена в один из [math] k [/math] цветов. При сравнении двух ожерелий их можно поворачивать, но не переворачивать (т.е. разрешается сделать циклический сдвиг).

В ходе решения задачи мы приходим к формуле [math]|C| =[/math] [math] \dfrac{1} {n}[/math][math]\sum\limits_{i = 1}^{n} k^{\mathrm{gcd}(i,n)}[/math]

Мы можем улучшить эту формулу, если рассмотрим выражение [math]\mathrm{gcd}(i,n)[/math]. Пусть [math]\mathrm{gcd}(i,n) = q[/math], тогда числа [math]i[/math] и [math]n[/math] оба делятся на [math]q[/math] и больше не имеют общих делителей. Тогда [math]\mathrm{gcd}(\frac{i}{q},\frac{n}{q}) = 1[/math]. Таких натуральных [math]i \in [1 ; n][/math] и имеющих [math]\mathrm{gcd}(i,n) = q[/math] ровно [math]\varphi\left(\dfrac{n}{q}\right)[/math].

Пользуясь функцией Эйлера, мы можем привести формулу к более лаконичному виду [math]|C| =[/math] [math] \dfrac{1} {n}[/math][math]\sum\limits_{q|n}\varphi\left(\dfrac{n}{q}\right)k^q[/math].

Алгоритм

Основной идеей алгоритма является формула [math] \displaystyle \varphi(n) = n\prod_{i = 1}^{r}(1 - \frac{1}{p_i}) [/math]. Для решения задачи нам нужны только простые делители числа [math]n[/math]. Их можно найти с помощью алгоритма факторизации. Написанный ниже алгоритм использует факторизацию числа, работающую за [math]O(\sqrt{n})[/math], однако есть более эффективные алгоритмы.

Асимптотика вычисления [math] \displaystyle \varphi(n) = O(\sqrt{n})[/math].

function phi (n):
    result = n 
    i = 2
    
    while (i*i <= n):
        if n % i == 0:
            while n % i == 0:
                n /= i
            result -= result / i
        i++
    if (n > 1):
        result -= result/n
    return result

См. также

• Задача об ожерельях

Ссылки

• Wikipedia — Функция Эйлера
• Алгоритм нахождения функции Эйлера
• Функция [math]\sigma[/math]