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

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

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

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

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

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

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

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

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

$\triangleright$

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

$\triangleleft$

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

Каноническое разложение числа $\displaystyle n = \prod_{i=1}^{r}p_i^{s_i}$

Функция $\sigma(n)$

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

$\displaystyle\sigma(n) = \sum_{d | n}d$

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

$\displaystyle\sigma(p^s) = \sum_{k=0}^{s}p^k = \frac{p^{s + 1} - 1}{p - 1}$

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

$\displaystyle \sigma (n) = \prod_{i = 1}^{r}{\frac{p_{i}^{s_i+1}-1} {p_{i}-1}}$

Функция $\tau(n)$

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

$\displaystyle\tau(n) = \sum_{d | n}1$

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

$\tau(mn)=\tau(m)\tau(n)$</math>

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

$\displaystyle\tau(p^s) = s + 1$

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

$\displaystyle \tau(n) = \prod_{i = 1}^{r}(s_i + 1)$

Функция $\varphi(n)$

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

$\displaystyle\varphi(p^s) = p^s - p^{s - 1}$

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

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

$\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})$

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

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

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

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

$\triangleright$

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

$\triangleleft$

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

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

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

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

$\triangleright$

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

$\triangleleft$

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

Теорема:

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

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

$\triangleright$

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

$\triangleleft$

Теорема:

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

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

$\triangleright$

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

$\triangleleft$

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

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

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

$\triangleright$

Пусть $(m,\,n)=d,$ тогда $m = m'd, \; n = n'd,$ причем в общем случае $(m',\,d) \neq 1$ и $(n',\,d) \neq 1.$ Поэтому можно записать: $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}},$ $m' = d_1^{\alpha_1} \cdot\ldots\cdot d_k^{\alpha_k} \cdot p_1^{\beta_1} \cdot\ldots\cdot p_r^{\beta_r},$ $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}.$ Здесь первые $k$ делителей $d$ являются также делителями $m',$ а последние $K-k$ делителей $d$ являются делителями $n'.$ Распишем: $\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}).$ В силу мультипликативности функции Эйлера, а также с учётом формулы $\varphi(p^n) = p^n(1-\frac{1}{p}),$ где $p$ — простое, получаем: $\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}$ В первой строке записано $\varphi(m),$ во второй — $\varphi(n),$ а третью можно представить, как $\frac{d}{\varphi(d)}.$ Поэтому: $\varphi(m \cdot n) = \varphi(m) \cdot \varphi(n) \cdot \frac{d}{\varphi(d)}.$

$\triangleleft$

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

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

Задача:

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

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

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

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

Алгоритм

Используя доказанные выше свойства функции, получим алгоритм нахождения $\varphi(n)$ через факторизацию числа, работающий за $O(\sqrt{n})$.

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 — Функция Эйлера
• Алгоритм нахождения функции Эйлера
• Функция $\sigma$