[[Категория:Математический анализ 1 курс]] [[Категория:Дискретная математика и алгоритмы]] [[Категория:Отношения]] == Функция Эйлера Определения==
{{Определение
|definition=
Функция <tex>f : \mathbb{N} \to \mathbb{Z} </tex> называется ''мультипликативнойМножество''{{---}} первичное математическое понятие, которому не дано строгое математическое определение. Представляет собой набор, если <tex>f(mn) = f(m)f(n)</tex> для любых взаимносовокупность каких-простых <tex>mлибо объектов, n</tex>объединенных общим свойством.
}}
{{Определение
|definition=
Объекты, из которых состоит множество, называют ''Функция Эйлераэлементами'' этого множества. Если <tex>a</tex> {{---}} элемент множества <tex>A</tex>, то записывают <tex>a \varphi in A</tex> (n«<tex>a</tex> принадлежит <tex>A</tex>») . Если <tex>a</tex> не является элементом множества <tex>A</tex> - определяется как количество натуральных чисел, не превосходящих то записывают <tex>a \notin A</tex> («<tex>na</tex> и взаимно-простых с не принадлежит <tex>nA</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>входящих в множество. Тогда, если <mathtex>GCD(d, m) A = 1</math>, то остатки всех этих <math>m</math> чисел по модулю <math>m</math> разные, а значит образуют все множество остатков <math>\{0a_1, a_2 ..., \dots a_n, m - 1...\}</mathtex>, причем каждый остаток получается ровно из одного из членов прогрессии.
Подставив в данные рассуждения <math>d = n</math>=== Описание ====Второй способ применяется, получим, что в каждом столбце таблицы имеется ровно <math>\varphi(m)</math> чисел, взаимно-простых когда множество нельзя или затруднительно задать с <math>m</math>помощью списка. Следовательно всего чисел, взаимно-простых и с <math>n</math> и с <math>m</math> равно <math>\varphi(m)\varphi(n)</math>, что и требовалось доказатьВ таком случае множества определяются свойствами их элементов.}}
<tex> A = \{a \mid P\} </tex> , где <tex>P</tex> {{---}} определенное свойство элемента <tex>a</tex>.
== Функции <tex>\sigma(n)</tex>, <tex>\tau(n)</tex> и <tex>\varphi(n)</tex>, их мультипликативность и значения Отношения между множествами ==
Каноническое разложение числа Два множества <tex>\displaystyle n = \prod_{i=1}^{r}p_i^{s_i} A</tex>и <tex>B</tex> могут вступать друг с другом в различные отношения.
==== Функция Включение ====* <tex>A</tex> включено в <tex>B</tex>, если каждый элемент множества <tex>A</tex> принадлежит также и множеству <tex>B</tex> : *: <tex>\displaystyle A\subseteq B\Leftrightarrow \forall a\in A \sigma(n)\colon \ a\in B</tex> ====
Функция * <tex>\sigma : \mathbb{N} \to \mathbb{N} A</tex> включает <tex>B</tex> определяется как сумма делителей натурального числа , если <tex>nB</tex>включено в <centertex>A</tex>:*: <tex>{\displaystyleA\supseteq B\sigma(n) = Leftrightarrow B\sum_{d | nsubseteq A}d </tex></center>
Для простого числа * <mathtex>pA</mathtex> строго включено в <tex>B</tex> легко посчитать , если <tex>\displaystyle\sigma(p) = p + 1A</tex>. При этом легко обобщается для некоторой степени включено в <mathtex>pB</mathtex>, но не равно ему: <center>*: <tex>{\displaystyleA\sigmasubset B\Leftrightarrow (p^sA\subseteq B) = \sum_{k=0}^{s}p^k = land (A\frac{p^{s + 1} - 1}{p - 1neq B)} </tex></center>
В силу мультипликативности функции:==== Равенство ====* <tex>A</tex> равно <tex>B</tex>, если <tex>A</tex> и <centertex>B</tex> включены друг в друга:*: <tex>{\displaystyle A=B\sigma Leftrightarrow (nA\subseteq B) = \prod_{i = 1}^{r}{land (B\frac{p_{i}^{s_i+1}-1subseteq A)} {p_{i}-1}}. </tex></center>
==== Общие элементы ====
* <tex>A</tex> и <tex>B</tex> не пересекаются, если у них нет общих элементов:
*: <tex>A</tex> и <tex>B</tex> не пересекаются <tex>{\displaystyle \Leftrightarrow \forall a\in A \ \colon a\notin B}</tex>
==== Функция <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> взаимно{{Определение|definition=''Пустое множество'' {{---просты, то каждый делитель произведения <math>mn</math> может быть единственным образом представлен в виде произведения делителей <math>m</math> и делителей <math>n</math>}} множество, и обратно, каждое такое произведение является делителем <math>mn</math>не содержащее ни одного элемента. Отсюда следует, что функция Обычно пустое множество обозначают как <tex>\tau(n)varnothing</tex> мультипликативна:.<center><math>\tau(mn)=\tau(m)\tau(n).</math></center>}}
Для простого числа <math>p</math> легко посчитать {{Определение|definition=''Универсальное множество'' {{---}} множество, содержащее все объекты и все множества. В тех аксиоматиках, в которых универсальное множество существует, оно единственно. Обычно универсальное множество обозначают как <tex>\ \displaystyle\tau(p) = 2mathbb {U}</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>A</tex> и <tex>B</tex>. *: <tex>{\displaystyle A\cap B =\{x\varphi(n)mid x\in A\land x\in B\}}</tex> ====
Для простого числа * Объединение <mathtex>pA</mathtex> легко посчитать и <tex>\displaystyle\varphi(p) = p - 1B</tex>. На некоторую степень <math>p</math> формулу можно обобщить*:<center><tex>{\displaystyleA\varphi(p^s) cup B = p^s - p^\{s - 1x\mid x\in A\lor x\in B\}} </tex></center>Обосновывается следующим образом: Все не взаимно-простые с <math>p^s</math> числа в диапазоне от 1 до <math>p^s</math>, очевидно, кратны <math>p</math>. Всего таких чисел <math>p^{s - 1}</math>.
В силу мультипликативности функции:* Разность <tex>A</tex> и <centertex>B</tex> . *: <tex>{\displaystyle A\varphi(n) setminus B = A\prod_cap {i = 1}^\overline {rB}(p_i^{s_i} - p_i^{s_i - 1}) = \prod_{i = 1}^{r}p_i^{s_i}(1 - x\mid x\in A\frac{1}{p_i}) = nland x\prod_{i = 1}^{r}(1 - notin B\frac{1}{p_i}) </tex></center>
* Симметрическая разность <tex>A</tex> и <tex>B</tex>.
*: <tex> {\displaystyle A \bigtriangleup B \equiv A - B = (A \cup B) \setminus (A \cap B) }</tex>
==== Унарные операции над множествами ====
== Малая теорема Ферма и теорема Эйлера ==* Дополнение определяется следующим образом: {{Теорема|about= Теорема Эйлера |statement = Если <math>n</math> и <math>a</math> - взаимно-простые целые числа, то *: <mathtex>a^{\varphi(n)} \equiv 1 \ (mod \ n)</math> |proof =Число <math>\overlinedisplaystyle {x}</math> называется вычетом по модулю <math>n</math>, если <math>\overline{x} \equiv x \ (mod \ n)</math>. Вычет <math>\overline{xA}</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}A^{*}</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{bcomplement } = \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{mid 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}^{notin A\varphi(n)}\overline{b} = U\overline{b}</math>. Умножая обе части на вычет, обратный к <math>\overline{bsetminus A}</mathtex>, получим, что <math>\overline{a}^{\varphi(n)} \equiv 1 \ (mod \ n) </math>, что и требовалось доказать. }} Следствием теоремы Эйлера является малая теорема Ферма. У нее также есть доказательство без использования более общей теоремы Эйлера, однако его мы приводить не будем.
== Теорема де Моргана ==
{{Теорема
|about = Малая теорема Фермаде Моргана|statement= <tex>\displaystyle {\overline{\bigcup\limits_\alpha A_\alpha} = \bigcap\limits_\alpha \overline{A_\alpha} \\\overline{\bigcap\limits_\alpha A_\alpha} = \bigcup\limits_\alpha \overline{A_\alpha}} </tex>|proof=Докажем первое утверждение, второе доказывается аналогично.Для того, чтобы доказать равенство множеств, докажем, что первое множество включает второе и наоборот (частый приём при доказательстве равенства двух множеств).
|statement = Если целое число <math>a</math> и простое число <math>p</math> - взаимно-простыСначала докажем, то что <mathtex>a^\ \displaystyle \overline{p - 1\bigcup\limits_\alpha A_\alpha} \equiv 1 displaystyle \ (mod subseteq \ p)bigcap\limits_\alpha \overline{A_\alpha}</mathtex>.
|proof = Так как Пусть <mathtex>px \in \left ( \overline{\bigcup\limits_\alpha A_\alpha} \right )</mathtex> - простое. Значит, то <mathtex>\varphi(p) = p - 1nexists \ \alpha_i</mathtex>. Воспользуемся теоремой Эйлератакого, тогда что <mathtex>a^x \in A_{\varphi(p)alpha_i} = a^</tex>. Следовательно, <tex>\forall \alpha : \ x \in \overline{p - 1A_\alpha} \equiv 1 Rightarrow x \in \ left (mod \ pbigcap\limits_\alpha \overline{A_\alpha} \right )</mathtex>.В силу выбора <tex>x</tex> (любой элемент множества <tex>\overline{\bigcup\limits_\alpha A_\alpha}</tex>, что и требовалось доказать) следует искомое включение.
}}
== Различные свойства функции Эйлера ==
{{Теорема
|about =
|statement = Для любого натурального числа <math>n</math> выполнено равенство <math>\displaystyle n = \sum_{d | n} \varphi(d)</math>
|proof = Данную теорему можно доказать "напролом", пользуясь формулой для <math>\varphi(d)</math>, а можно более элегантно:
Рассмотрим Теперь докажем, что <math>n</math> дробей <mathtex>\frac{1}{n}, \frac{2}{n}, displaystyle \bigcap\limits_\dots , alpha \fracoverline{n}{nA_\alpha}</math>. Каждую дробь представим в виде несократимой дроби <math>\frac{p}{q}</math>.Заметим, что множество значений <math>q</math> - это множество делителей числа <math>n</math>. Так как дробь <math>subseteq \frac{p}overline{q}</math> несократима, то <math>p</math> и <math>q</math> взаимно-просты. Зная, что <math>p \leq q</math>, легко понять, что всего дробей со знаменателем <math>q</math> ровно <math>bigcup\varphi(q)</math>. Так как, все <math>n</math> дробей мы представили в несократимом виде, где знаменатель является делителем <math>n</math>, то <math>limits_\displaystyle alpha A_\sum_{d | nalpha} \varphi(d) = n</math>, так как всего дробей <math>n</mathtex>, что и требовалось доказать.
Пусть <tex>x \in \left ( \bigcap\limits_\alpha \overline{A_\alpha} \right )</tex>. Тогда <tex>\forall \alpha : \ x \in \overline{A_\alpha} \Rightarrow x \notin A_\alpha</tex>. Поскольку <tex>x</tex> не входит ни в одно объединяемое множество, то <tex>x \notin \bigcup\limits_\alpha A_\alpha \Rightarrow x \in \overline{\bigcup\limits_{\alpha} A_\alpha}</tex>
Аналогично, в силу выбора <tex>x</tex> выполняется искомое включение.
}}
== Применение теоремы Эйлера в других задачах == ==== Задача об ожерельях ==== {{Задача|definition=Требуется посчитать количество ожерелий из <tex>n</tex> бусинокТеорема де Моргана устанавливает двойственность понятий объединения и пересечения множеств. То есть, имея некоторое верное равенство, содержащее объединения и пересечения, каждая из которых может быть покрашена в один из <tex> k </tex> цветов. При сравнении двух ожерелий их можно поворачиватьпереписать его, но не переворачивать (тзаменив пересечения на объединения и наоборот.е. разрешается сделать циклический сдвиг).}}Например, из равенства В ходе решения задачи мы приходим к формуле <tex>|C| =</tex> :<tex> (A \dfrac{1} {n}</tex><tex>cup B) \sum\limits_{i cap C = 1}^{n} k^{(A \mathrm{gcd}(i,ncap C)}</tex> Мы можем улучшить эту формулу, если рассмотрим выражение <math>\mathrm{gcd}cup (i,n)</math>. Пусть <math>B \mathrm{gcd}(i,ncap C) = q</math>, тогда числа <math>i</math> и <math>n</math> оба делятся на <math>q</math> и больше не имеют общих делителей. Тогда <math>\mathrm{gcd}Rightarrow (A \frac{i}{q},cap B) \frac{n}{q}) cup C = 1</math>. Таких натуральных <math>i (A \in [1 ; n]</math> и имеющих <math>\mathrm{gcd}(i,ncup C) = q</math> ровно <tex>\varphi\leftcap (B \dfrac{n}{q}\rightcup C)</tex>. Пользуясь функцией ЭйлераДоказывается это следующим образом: равны множества, значит, мы можем привести формулу равны дополнения. После раскрытия дополнений приходим к финальному виду <tex>|C| =</tex> <tex> \dfrac{1} {n}</tex><tex>\sum\limits_{q|n}\varphi\left(\dfrac{n}{q}\right)k^q</tex>написанному равенству. == Ссылки ==* [[Линейный оператор]]
