69
правок
Изменения
Шаблон финальной версии. Потом еще добавлю пару свойств функции Эйлера.
== Функция Эйлера ==
{{Определение
|definition=
Функция <tex>f : \mathbb{N} \to \mathbb{Z} </tex> называется ''мультипликативной'', если <tex>f(mn) = f(m)f(n)</tex> для любых взаимно-простых <tex>m, n</tex>.
}}
{{Определение
|definition=
''Функция Эйлера'' <tex>\varphi (n) </tex> - определяется как количество натуральных чисел, не превосходящих <tex>n</tex> и взаимно-простых с <tex>n</tex>.
}}
{{Теорема
|about = Мультипликативность функции Эйлера
|statement = Для любых взаимно-простых чисел <tex>m, n</tex>
: <math>\varphi(mn)=\varphi(m)\varphi(n).</math>
|proof =
Запишем <math>nm</math> натуральных чисел, не превосходящих <math>nm</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>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>\displaystyle n = \prod_{i=1}^{r}p_i^{s_i} </tex>
==== Функция <tex>\sigma(n)</tex> ====
Функция <tex>\sigma : \mathbb{N} \to \mathbb{N} </tex> определяется как сумма делителей натурального числа <tex>n</tex>
<center><tex>\displaystyle\sigma(n) = \sum_{d | n}d </tex></center>
Для простого числа <math>p</math> легко посчитать <tex>\displaystyle\sigma(p) = p + 1</tex>. При этом легко обобщается для некоторой степени <math>p</math>:
<center><tex>\displaystyle\sigma(p^s) = \sum_{k=0}^{s}p^k = \frac{p^{s + 1} - 1}{p - 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: \mathbb{N} \to \mathbb{N} </tex> определяется как число положительных делителей натурального числа <tex>n</tex>:
<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> мультипликативна:
<center><math>\tau(mn)=\tau(m)\tau(n).</math></center>
Для простого числа <math>p</math> легко посчитать <tex>\displaystyle\tau(p) = 2</tex>. При этом легко обобщается для некоторой степени <math>p</math>:
<center><tex>\displaystyle\tau(p^s) = s + 1 </tex></center>
В силу мультипликативности функции:
<center><tex> \displaystyle \tau(n) = \prod_{i = 1}^{r}(s_i + 1). </tex></center>
==== Функция <tex>\varphi(n)</tex> ====
Для простого числа <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>
Обосновывается следующим образом: Все не взаимно-простые с <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>
== Малая теорема Ферма и теорема Эйлера ==
{{Теорема
|about= Теорема Эйлера
|statement = Если <math>n</math> и <math>a</math> - взаимно-простые целые числа, то <math>a^{\varphi(n)} \equiv 1 \ (mod \ n)</math>
|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>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>, что и требовалось доказать.
}}
Следствием теоремы Эйлера является малая теорема Ферма. У нее также есть доказательство без использования более общей теоремы Эйлера, однако его мы приводить не будем.
{{Теорема
|about = Малая теорема Ферма
|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>, что и требовалось доказать.
}}
== Различные свойства функции Эйлера ==
{{Теорема
|about =
|statement = Для любого натурального числа <math>n</math> выполнено равенство <math>\displaystyle n = \sum_{d | n} \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>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>, что и требовалось доказать.
}}
== Применение теоремы Эйлера в других задачах ==
==== Задача об ожерельях ====
{{Задача
|definition=
Требуется посчитать количество ожерелий из <tex>n</tex> бусинок, каждая из которых может быть покрашена в один из <tex> k </tex> цветов. При сравнении двух ожерелий их можно поворачивать, но не переворачивать (т.е. разрешается сделать циклический сдвиг).}}
В ходе решения задачи мы приходим к формуле <tex>|C| =</tex> <tex> \dfrac{1} {n}</tex><tex>\sum\limits_{i = 1}^{n} k^{\mathrm{gcd}(i,n)}</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>.
{{Определение
|definition=
Функция <tex>f : \mathbb{N} \to \mathbb{Z} </tex> называется ''мультипликативной'', если <tex>f(mn) = f(m)f(n)</tex> для любых взаимно-простых <tex>m, n</tex>.
}}
{{Определение
|definition=
''Функция Эйлера'' <tex>\varphi (n) </tex> - определяется как количество натуральных чисел, не превосходящих <tex>n</tex> и взаимно-простых с <tex>n</tex>.
}}
{{Теорема
|about = Мультипликативность функции Эйлера
|statement = Для любых взаимно-простых чисел <tex>m, n</tex>
: <math>\varphi(mn)=\varphi(m)\varphi(n).</math>
|proof =
Запишем <math>nm</math> натуральных чисел, не превосходящих <math>nm</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>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>\displaystyle n = \prod_{i=1}^{r}p_i^{s_i} </tex>
==== Функция <tex>\sigma(n)</tex> ====
Функция <tex>\sigma : \mathbb{N} \to \mathbb{N} </tex> определяется как сумма делителей натурального числа <tex>n</tex>
<center><tex>\displaystyle\sigma(n) = \sum_{d | n}d </tex></center>
Для простого числа <math>p</math> легко посчитать <tex>\displaystyle\sigma(p) = p + 1</tex>. При этом легко обобщается для некоторой степени <math>p</math>:
<center><tex>\displaystyle\sigma(p^s) = \sum_{k=0}^{s}p^k = \frac{p^{s + 1} - 1}{p - 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: \mathbb{N} \to \mathbb{N} </tex> определяется как число положительных делителей натурального числа <tex>n</tex>:
<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> мультипликативна:
<center><math>\tau(mn)=\tau(m)\tau(n).</math></center>
Для простого числа <math>p</math> легко посчитать <tex>\displaystyle\tau(p) = 2</tex>. При этом легко обобщается для некоторой степени <math>p</math>:
<center><tex>\displaystyle\tau(p^s) = s + 1 </tex></center>
В силу мультипликативности функции:
<center><tex> \displaystyle \tau(n) = \prod_{i = 1}^{r}(s_i + 1). </tex></center>
==== Функция <tex>\varphi(n)</tex> ====
Для простого числа <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>
Обосновывается следующим образом: Все не взаимно-простые с <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>
== Малая теорема Ферма и теорема Эйлера ==
{{Теорема
|about= Теорема Эйлера
|statement = Если <math>n</math> и <math>a</math> - взаимно-простые целые числа, то <math>a^{\varphi(n)} \equiv 1 \ (mod \ n)</math>
|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>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>, что и требовалось доказать.
}}
Следствием теоремы Эйлера является малая теорема Ферма. У нее также есть доказательство без использования более общей теоремы Эйлера, однако его мы приводить не будем.
{{Теорема
|about = Малая теорема Ферма
|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>, что и требовалось доказать.
}}
== Различные свойства функции Эйлера ==
{{Теорема
|about =
|statement = Для любого натурального числа <math>n</math> выполнено равенство <math>\displaystyle n = \sum_{d | n} \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>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>, что и требовалось доказать.
}}
== Применение теоремы Эйлера в других задачах ==
==== Задача об ожерельях ====
{{Задача
|definition=
Требуется посчитать количество ожерелий из <tex>n</tex> бусинок, каждая из которых может быть покрашена в один из <tex> k </tex> цветов. При сравнении двух ожерелий их можно поворачивать, но не переворачивать (т.е. разрешается сделать циклический сдвиг).}}
В ходе решения задачи мы приходим к формуле <tex>|C| =</tex> <tex> \dfrac{1} {n}</tex><tex>\sum\limits_{i = 1}^{n} k^{\mathrm{gcd}(i,n)}</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>.
