[[Категория:Математический анализ 1 курс]] [[Категория:Дискретная математика и алгоритмы]] [[Категория:Отношения]] == Функция Эйлера Определения==
{{Определение
|definition=
''Функция ЭйлераМножество'' <tex>\varphi (n) </tex> {{---}} определяется как количество натуральных чиселпервичное математическое понятие, которому не превосходящих <tex>n</tex> и взаимно простых с <tex>n</tex>дано строгое математическое определение. Представляет собой набор, совокупность каких-либо объектов, объединенных общим свойством.
}}
{{Определение
|definition=
Функция Объекты, из которых состоит множество, называют ''элементами'' этого множества. Если <tex>f : \mathbba</tex> {{N---} \to \mathbb{Z} элемент множества <tex>A</tex> называется ''мультипликативной'', если то записывают <tex>fa \in A</tex> (mn«<tex>a</tex> принадлежит <tex>A</tex>») = f. Если <tex>a</tex> не является элементом множества <tex>A</tex>, то записывают <tex>a \notin A</tex> (m)f(n)«<tex>a</tex> для любых взаимно простых не принадлежит <tex>m, nA</tex>»). В отличие от мультимножества каждый элемент множества уникален, и во множестве не может быть двух идентичных элементов.
}}
{{Теорема|about = Мультипликативность функции Эйлера|statement = Для любых взаимно простых чисел <tex>m, n</tex> : <math>\varphi(mn)Способы задания множеств=\varphi(m)\varphi(n)</math>|proof =Запишем <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> тогда задаётся и только тогдаперечисляется полный список элементов, когда остаток деления входящих в множество. <mathtex>sA = \{a_1, a_2 ..., a_n, ...\} </math> на <mathtex>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> последовательных членов арифметической прогрессии <mathtex>A = \{a, a + d, \dots , a + (m - 1)dmid P\} </mathtex>. Тогда, если где <mathtex>(d, m) = 1P</mathtex>, то остатки всех этих <math>m</math> чисел по модулю <math>m</math> разные, а значит образуют все множество остатков <math>\{0, \dots , m {--- 1\}} определенное свойство элемента <tex>a</mathtex>, причем каждый остаток получается ровно из одного из членов прогрессии.
Воспользуемся данным утверждением, подставив разность арифметиечской прогресии <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>, что и требовалось доказать.= Отношения между множествами ==
Два множества <tex>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 \ \colon \ a\in B</tex>
== Функции * <tex>\sigma(n)A</tex> включает <tex>B</tex>, если <tex>B</tex> включено в <tex>\tau(n)A</tex> и :*: <tex>{\varphi(n)displaystyle A\supseteq B\Leftrightarrow B\subseteq A}</tex>, их мультипликативность и значения ==
Каноническое разложение числа * <tex>A</tex> строго включено в <tex>B</tex>, если <tex>A</tex> включено в <tex>B</tex>, но не равно ему:*: <tex>{\displaystyle n = A\subset B\Leftrightarrow (A\subseteq B)\land (A\prod_{i=1}^{r}p_i^{s_ineq B)} </tex>
==== Функция Равенство ====* <tex>A</tex> равно <tex>B</tex>, если <tex>A</tex> и <tex>B</tex> включены друг в друга:*: <tex>{\sigmadisplaystyle A=B\Leftrightarrow (A\subseteq B)\land (nB\subseteq A)}</tex> ====
Функция ==== Общие элементы ====* <tex>\sigma : \mathbb{N} \to \mathbb{N} A</tex> определяется как сумма делителей натурального числа и <tex>nB</tex>не пересекаются, если у них нет общих элементов:*: <centertex>A</tex>и <tex>B</tex> не пересекаются <tex>{\displaystyle\sigma(n) = Leftrightarrow \forall a\in A \ \colon a\sum_{d | nnotin B}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></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>, что и требовалось доказать.
{{Определение
|definition=
''Пустое множество'' {{---}} множество, не содержащее ни одного элемента. Обычно пустое множество обозначают как <tex>\varnothing</tex>.
}}
Следствием теоремы Эйлера является малая теорема Ферма. У нее также есть доказательство без использования более общей теоремы Эйлера, однако его мы приводить не будем. {{ТеоремаОпределение|about definition= Малая теорема Ферма |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>содержащее все объекты и все множества. Воспользуемся теоремой ЭйлераВ тех аксиоматиках, тогда в которых универсальное множество существует, оно единственно. Обычно универсальное множество обозначают как <mathtex>a^{\varphi(p)} = a^\displaystyle \mathbb {p - 1U} \equiv 1 \ (mod \ p)</mathtex>, что и требовалось доказать.
}}
== Различные свойства функции Эйлера Операции над множествами ==
{{Теорема|about ==== Бинарные операции над множествами ====
|statement = Если для каких-то натуральных чисел * Пересечение <mathtex>aA</mathtex> и <mathtex>bB</mathtex> верно, что . *: <mathtex>a{\,|displaystyle A\,b</math>, тогда верно и <math>cap B =\{x\mid x\varphi(a)in A\,|land x\, in B\varphi(b)}}</mathtex>
|proof = * Объединение <tex>A</tex> и <tex>B</tex>. Воспользуемся формулой для *: <tex> {\displaystyle A\varphi(n) cup B = \prod_{i = 1}^{r}(p_i^{s_i} - p_i^{s_i - 1}) = x\mid x\in A\lor x\in B\prod_{i = 1}^{r}p_i^{s_i - 1}(p_i - 1) </tex>.
* Разность <tex>A</tex> и <tex>B</tex>. *:<mathtex>a = p_1^{\alpha_1} displaystyle A\cdot\ldotssetminus B =A\cdot p_{r_a}^cap {\alpha_overline {r_aB}},</math>:<math>b = p_1^\{x\beta_1} mid x\cdotin A\ldotsland x\cdot p_{r_b}^{notin B\beta_{r_b}}</mathtex>
При этом, так как * Симметрическая разность <mathtex>a\,|\,bA</mathtex>, то и <mathtex>r_a \leq r_bB</mathtex>, а также . *: <mathtex>{\forall i \in [1\, ;displaystyle A \, r_a] bigtriangleup B \ equiv A - B = (A \alpha_i cup B) \leq setminus (A \beta_icap B) }</mathtex>
<math></math>==== Унарные операции над множествами ====
Значит * Дополнение определяется следующим образом:*: <tex>{\displaystyle\frac{\varphi(b)}{\varphi(a)}</tex><tex>\displaystyle = \frac{\displaystyle\prod_overline {i = 1A}^{r_b}p_i^{\beta_i - 1}(p_i - 1)}{\displaystyle\prod_{i = 1}^{r_a}p_iequiv A^{\alpha_i - 1}(p_i - 1)complement } = \displaystyle(\prod_{i = 1}^{r_a}p_i^{\beta_i - \alpha_i}) x\cdot mid x\displaystyle(notin A\prod_{i = r_a + 1}^{r_b}p_i^{=U\beta_i - 1setminus A}(p_i - 1))</tex>, а значит <math>\varphi(a)\,|\, \varphi(b)</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>n</math> выполнено равенство <mathtex>\ \displaystyle n = \sum_overline{d | n\bigcup\limits_\alpha A_\alpha} \varphi(d)displaystyle \subseteq \bigcap\limits_\alpha \overline{A_\alpha}</mathtex>.
|proof = Данную теорему можно доказать "напролом", пользуясь формулой для Пусть <mathtex>x \in \varphileft (d\overline{\bigcup\limits_\alpha A_\alpha} \right )</mathtex>. Значит, <tex>\nexists \ \alpha_i</tex> такого, что <tex>x \in A_{\alpha_i}</tex>. Следовательно, а можно более элегантно<tex>\forall \alpha :\ x \in \overline{A_\alpha} \Rightarrow x \in \left (\bigcap\limits_\alpha \overline{A_\alpha} \right )</tex>.В силу выбора <tex>x</tex> (любой элемент множества <tex>\overline{\bigcup\limits_\alpha A_\alpha}</tex>) следует искомое включение.
Рассмотрим <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>, что и требовалось доказать.
}} : {{Теорема|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>В силу мультипликативности функции ЭйлераТеперь докажем, а также с учётом формулы:что <mathtex>\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^{displaystyle \beta_r}bigcap\left(1-limits_\frac{1}{p_r}\right) alpha \cdot d_{k+1}^overline{A_\delta_{k+1}alpha}\left(1-subseteq \fracoverline{1}{d_{k+1}}\right) \cdotbigcup\ldotslimits_\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}{alpha A_\varphi(d)alpha}.</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},\frac{n}{q}cap B) = 1</math>. Таких натуральных <math>i \in [1 ; n]</math> и имеющих <math>\mathrm{gcd}(i,n) cup C = q</math> ровно <tex>\varphi\left(A \dfrac{n}{q}\rightcup C)</tex>. Пользуясь функцией Эйлера, мы можем привести формулу к финальному виду <tex>|C| =</tex> <tex> \dfrac{1} {n}</tex><tex>\sum\limits_{q|n}\varphi\leftcap (B \dfrac{n}{q}\rightcup C)k^q</tex>. == Алгоритм ==Используя доказанные выше свойства функцииДоказывается это следующим образом: равны множества, получим алгоритм нахождения <math>\varphi(n)</math> через факторизацию числазначит, работающий за <math>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>]
