Функция Эйлера — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Добавил ожерелья)
м (rollbackEdits.php mass rollback)
 
(не показано 7 промежуточных версий 3 участников)
Строка 3: Строка 3:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
Функция <tex>f : \mathbb{N} \to \mathbb{Z} </tex> называется ''мультипликативной'', если <tex>f(mn) = f(m)f(n)</tex> для любых взаимно-простых <tex>m, n</tex>.
+
''Функция Эйлера'' <tex>\varphi (n) </tex> определяется как количество натуральных чисел, не превосходящих <tex>n</tex> и взаимно простых с <tex>n</tex>.
 
}}
 
}}
  
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
''Функция Эйлера'' <tex>\varphi (n) </tex> - определяется как количество натуральных чисел, не превосходящих <tex>n</tex> и взаимно-простых с <tex>n</tex>.
+
Функция <tex>f : \mathbb{N} \to \mathbb{Z} </tex> называется ''мультипликативной'', если <tex>f(mn) = f(m)f(n)</tex> для любых взаимно простых <tex>m, n</tex>.
 
}}
 
}}
  
 
{{Теорема
 
{{Теорема
 
|about = Мультипликативность функции Эйлера
 
|about = Мультипликативность функции Эйлера
|statement = Для любых взаимно-простых чисел <tex>m, n</tex>  
+
|statement = Для любых взаимно простых чисел <tex>m, n</tex>  
: <math>\varphi(mn)=\varphi(m)\varphi(n).</math>
+
: <math>\varphi(mn)=\varphi(m)\varphi(n)</math>
 
|proof =
 
|proof =
Запишем <math>nm</math> натуральных чисел, не превосходящих <math>nm</math>, в виде прямоугольной таблицы с <math>n</math> столбцами и <math>m</math> строками, располагая первые <math>n</math> чисел в первой строке, вторые <math>n</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>nm</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>k</math> взаимно-просто с <math>k</math>. Поэтому, числа в таблице, взаимно-простые с <math>n</math>, заполняют ровно <math>\varphi(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>. Данный факт довольно очевиден и используется в [https://e-maxx.ru/algo/euclid_algorithm Алгоритме Евклида].
 +
 
 +
Теперь приступим непосредственно к доказательству. Число находящееся в <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>m</math> последовательных членов арифметической прогрессии <math>a, a + d, \dots , a + (m - 1)d</math>. Тогда, если <math>GCD(d, m) = 1</math>, то остатки всех этих <math>m</math> чисел по модулю <math>m</math> разные, а значит образуют все множество остатков <math>\{0, \dots , m - 1\}</math>, причем каждый остаток получается ровно из одного из членов прогрессии.
 
  
Подставив в данные рассуждения <math>d = n</math>, получим, что в каждом столбце таблицы имеется ровно <math>\varphi(m)</math> чисел, взаимно-простых с <math>m</math>. Следовательно всего чисел, взаимно-простых и с <math>n</math> и с <math>m</math> равно <math>\varphi(m)\varphi(n)</math>, что и требовалось доказать.
 
 
}}
 
}}
 
  
 
== Функции <tex>\sigma(n)</tex>, <tex>\tau(n)</tex> и <tex>\varphi(n)</tex>, их мультипликативность и значения ==
 
== Функции <tex>\sigma(n)</tex>, <tex>\tau(n)</tex> и <tex>\varphi(n)</tex>, их мультипликативность и значения ==
  
Каноническое разложение числа <tex>\displaystyle n = \prod_{i=1}^{r}p_i^{s_i} </tex>
+
Каноническое разложение числа <tex>\displaystyle n = \prod_{i=1}^{r}p_i^{s_i} </tex>, где <tex>r</tex> {{---}} количество простых делителей числа <tex>n</tex>, <tex>p_i</tex> {{---}} <tex>i</tex>-ый простой делитель, <tex>s_i</tex> {{---}} максимальная степень вхождения этого простого делителя.
  
 
==== Функция <tex>\sigma(n)</tex> ====
 
==== Функция <tex>\sigma(n)</tex> ====
  
Функция <tex>\sigma : \mathbb{N} \to \mathbb{N} </tex> определяется как сумма делителей натурального числа <tex>n</tex>
+
Функция <tex>\sigma : \mathbb{N} \to \mathbb{N} </tex> определяется как сумма делителей натурального числа <tex>n</tex>:
 
<center><tex>\displaystyle\sigma(n) = \sum_{d | n}d </tex></center>
 
<center><tex>\displaystyle\sigma(n) = \sum_{d | n}d </tex></center>
 +
 +
Если <math>m</math> и <math>n</math> взаимно просты, то каждый делитель произведения <math>mn</math> может быть единственным образом представлен в виде произведения делителей <math>m</math> и делителей <math>n</math>, и обратно, каждое такое произведение является делителем <math>mn</math>. Отсюда следует, что функция <tex>\sigma(n)</tex>  мультипликативна:
  
 
Для простого числа <math>p</math> легко посчитать <tex>\displaystyle\sigma(p) = p + 1</tex>. При этом легко обобщается для некоторой степени <math>p</math>:  
 
Для простого числа <math>p</math> легко посчитать <tex>\displaystyle\sigma(p) = p + 1</tex>. При этом легко обобщается для некоторой степени <math>p</math>:  
Строка 39: Строка 46:
  
 
В силу мультипликативности функции:
 
В силу мультипликативности функции:
<center><tex> \displaystyle \sigma (n) = \prod_{i = 1}^{r}{\frac{p_{i}^{s_i+1}-1} {p_{i}-1}}. </tex></center>
+
<center><tex> \displaystyle \sigma (n) = \prod_{i = 1}^{r}{\frac{p_{i}^{s_i+1}-1} {p_{i}-1}} </tex></center>
 
 
  
 
==== Функция <tex>\tau(n)</tex> ====
 
==== Функция <tex>\tau(n)</tex> ====
Строка 47: Строка 53:
 
<center><tex>\displaystyle\tau(n) = \sum_{d | n}1 </tex></center>
 
<center><tex>\displaystyle\tau(n) = \sum_{d | n}1 </tex></center>
  
Если <math>m</math> и <math>n</math> взаимно-просты, то каждый делитель произведения <math>mn</math> может быть единственным образом представлен в виде произведения делителей <math>m</math> и делителей <math>n</math>, и обратно, каждое такое произведение является делителем <math>mn</math>. Отсюда следует, что функция <tex>\tau(n)</tex>  мультипликативна:
+
Если <math>m</math> и <math>n</math> взаимно просты, то каждый делитель произведения <math>mn</math> может быть единственным образом представлен в виде произведения делителей <math>m</math> и делителей <math>n</math>, и обратно, каждое такое произведение является делителем <math>mn</math>. Отсюда следует, что функция <tex>\tau(n)</tex>  мультипликативна:
<center><math>\tau(mn)=\tau(m)\tau(n).</math></center>
+
<center><math>\tau(mn)=\tau(m)\tau(n)</math></center>
  
 
Для простого числа <math>p</math> легко посчитать <tex>\displaystyle\tau(p) = 2</tex>. При этом легко обобщается для некоторой степени <math>p</math>:  
 
Для простого числа <math>p</math> легко посчитать <tex>\displaystyle\tau(p) = 2</tex>. При этом легко обобщается для некоторой степени <math>p</math>:  
Строка 54: Строка 60:
  
 
В силу мультипликативности функции:
 
В силу мультипликативности функции:
<center><tex> \displaystyle \tau(n) = \prod_{i = 1}^{r}(s_i + 1). </tex></center>
+
<center><tex> \displaystyle \tau(n) = \prod_{i = 1}^{r}(s_i + 1) </tex></center>
 
 
  
 
==== Функция <tex>\varphi(n)</tex> ====
 
==== Функция <tex>\varphi(n)</tex> ====
Строка 61: Строка 66:
 
Для простого числа <math>p</math> легко посчитать <tex>\displaystyle\varphi(p) = p - 1</tex>. На некоторую степень <math>p</math> формулу можно обобщить:
 
Для простого числа <math>p</math> легко посчитать <tex>\displaystyle\varphi(p) = p - 1</tex>. На некоторую степень <math>p</math> формулу можно обобщить:
 
<center><tex>\displaystyle\varphi(p^s) = p^s - p^{s - 1} </tex></center>
 
<center><tex>\displaystyle\varphi(p^s) = p^s - p^{s - 1} </tex></center>
Обосновывается следующим образом: Все не взаимно-простые с <math>p^s</math> числа в диапазоне от 1 до <math>p^s</math>, очевидно, кратны <math>p</math>. Всего таких чисел <math>p^{s - 1}</math>.
+
Обосновывается следующим образом: Все не взаимно простые с <math>p^s</math> числа в диапазоне от 1 до <math>p^s</math>, очевидно, кратны <math>p</math>. Всего таких чисел <math>p^{s - 1}</math>.
  
 
В силу мультипликативности функции:
 
В силу мультипликативности функции:
 
<center><tex> \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}) </tex></center>
 
<center><tex> \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}) </tex></center>
 
 
  
 
== Малая теорема Ферма и теорема Эйлера ==
 
== Малая теорема Ферма и теорема Эйлера ==
Строка 73: Строка 76:
 
|about= Теорема Эйлера
 
|about= Теорема Эйлера
  
|statement = Если <math>n</math> и <math>a</math> - взаимно-простые целые числа, то <math>a^{\varphi(n)} \equiv 1 \ (mod \ n)</math>
+
|statement = Если <math>n</math> и <math>a</math> {{---}} взаимно простые целые числа, то <math>a^{\varphi(n)} \equiv 1 \ (mod \ n)</math>
  
 
|proof =
 
|proof =
Число <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>n</math> существует всего <math>\varphi(n)</math> обратимых вычетов. Пусть <math>\mathbb{Z}_{n}^{*}</math> - множество всех обратимых вычетов по модулю <math>n</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> взаимно просты. Это обосновывается тем, что данное выражение можно представить в виде [https://e-maxx.ru/algo/diofant_2_equation линейного диофантово уравнения второго порядка] <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>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>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>, что и требовалось доказать.
  
 
}}
 
}}
Строка 88: Строка 93:
 
|about = Малая теорема Ферма
 
|about = Малая теорема Ферма
  
|statement = Если целое число <math>a</math> и простое число <math>p</math> - взаимно-просты, то <math>a^{p - 1} \equiv 1 \ (mod \ p)</math>
+
|statement = Если целое число <math>a</math> и простое число <math>p</math> {{---}} взаимно просты, то <math>a^{p - 1} \equiv 1 \ (mod \ p)</math>
  
|proof = Так как <math>p</math> - простое, то <math>\varphi(p) = p - 1</math>. Воспользуемся теоремой Эйлера, тогда <math>a^{\varphi(p)} = a^{p - 1} \equiv 1 \ (mod \ p)</math>, что и требовалось доказать.
+
|proof = Так как <math>p</math> {{---}} простое, то <math>\varphi(p) = p - 1</math>. Воспользуемся теоремой Эйлера, тогда <math>a^{\varphi(p)} = a^{p - 1} \equiv 1 \ (mod \ p)</math>, что и требовалось доказать.
  
 
}}
 
}}
  
 
== Различные свойства функции Эйлера ==
 
== Различные свойства функции Эйлера ==
 +
 +
{{Теорема
 +
|about =
 +
 +
|statement = Если для каких-то натуральных чисел <math>a</math> и <math>b</math> верно, что <math>a\,|\,b</math>, тогда верно и <math>\varphi(a)\,|\, \varphi(b)</math>
 +
 +
|proof =
 +
Воспользуемся формулой для <tex> \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) </tex>.
 +
 +
:<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>
 +
 +
Значит, <tex>\displaystyle\frac{\varphi(b)}{\varphi(a)}</tex><tex>\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))</tex>, а значит, <math>\varphi(a)\,|\, \varphi(b)</math>, что и требовалось доказать.
 +
 +
}}
  
 
{{Теорема
 
{{Теорема
Строка 101: Строка 125:
 
|statement = Для любого натурального числа <math>n</math> выполнено равенство <math>\displaystyle n = \sum_{d | n} \varphi(d)</math>
 
|statement = Для любого натурального числа <math>n</math> выполнено равенство <math>\displaystyle n = \sum_{d | n} \varphi(d)</math>
  
|proof = Данную теорему можно доказать "напролом", пользуясь формулой для <math>\varphi(d)</math>, а можно более элегантно:
+
|proof = Данную теорему можно доказать разложив по формуле <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>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>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>, что и требовалось доказать.
  
 
}}
 
}}
  
 +
:
 +
 +
{{Теорема
 +
|about = Обобщённая мультипликативность
 +
 +
|statement = Пусть <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>
 +
 +
|proof =
 +
 +
Пусть <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>
 +
 +
}}
  
 
== Применение теоремы Эйлера в других задачах ==
 
== Применение теоремы Эйлера в других задачах ==
Строка 121: Строка 180:
 
Мы можем улучшить эту формулу, если рассмотрим выражение <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> ровно <tex>\varphi\left(\dfrac{n}{q}\right)</tex>.
 
Мы можем улучшить эту формулу, если рассмотрим выражение <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> ровно <tex>\varphi\left(\dfrac{n}{q}\right)</tex>.
  
Пользуясь функцией Эйлера, мы можем привести формулу к финальному виду <tex>|C| =</tex> <tex> \dfrac{1} {n}</tex><tex>\sum\limits_{q|n}\varphi\left(\dfrac{n}{q}\right)k^q</tex>.
+
Пользуясь функцией Эйлера, мы можем привести формулу к более лаконичному виду <tex>|C| =</tex> <tex> \dfrac{1} {n}</tex><tex>\sum\limits_{q|n}\varphi\left(\dfrac{n}{q}\right)k^q</tex>.
 +
 
 +
== Алгоритм ==
 +
Основной идеей алгоритма является формула <tex> \displaystyle \varphi(n) = n\prod_{i = 1}^{r}(1 - \frac{1}{p_i}) </tex>. Для решения задачи нам нужны только простые делители числа <math>n</math>. Их можно найти с помощью алгоритма факторизации. Написанный ниже алгоритм использует факторизацию числа, работающую за <math>O(\sqrt{n})</math>, однако есть более [https://e-maxx.ru/algo/factorization эффективные алгоритмы].
 +
 
 +
Асимптотика вычисления <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
 +
 
 +
== См. также ==
 +
* [[Задача об ожерельях]]
 +
 
 +
== Ссылки ==
 +
* [https://ru.wikipedia.org/wiki/Функция_Эйлера Wikipedia {{---}} Функция Эйлера]
 +
* [https://e-maxx.ru/algo/euler_function Алгоритм нахождения функции Эйлера]
 +
* [https://wikichi.ru/wiki/Divisor_function Функция <math>\sigma</math>]

Текущая версия на 19:35, 4 сентября 2022

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

Определение:
Функция Эйлера [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

См. также

Ссылки