Изменения

[[Категория:Математический анализ 1 курс]]== Функция Эйлера Начальные определения==Множество - первичное математическое понятие, которому не может быть дано строгое математическое определение. Часто множество определяют как «совокупность объектов, объединенных общим свойством».

{{ОпределениеВ [[Математический анализ 1 курс|definition=''Функция Эйлера'' <tex>\varphi (n) </tex> определяется как количество натуральных чисел, не превосходящих <tex>n</tex> и взаимно простых с <tex>n</tex>.}} {{Определение|definition=Функция <tex>f : \mathbb{N} \to \mathbb{Z} </tex> называется ''мультипликативной'', если <tex>f(mn) = f(m)f(n)</tex> для любых взаимно простых <tex>m, n</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Кантором(n1870)</math>.

В данном доказательстве мы используем тот факт, что число <mathtex>sa \in A</mathtex> взаимно просто с натуральным <math>k</math> тогда и только тогда, когда остаток деления <math>s</math> на <math>k</math> тоже взаимно прост с <math>k</math>. Данный факт довольно очевиден и используется в [https://e-maxx.ru/algo/euclid_algorithm Алгоритме Евклида].(объект а принадлежит множеству А)

Теперь приступим непосредственно к доказательству. Число находящееся в <mathtex>i</math>-ой строке и <math>ja \notin A</math>-ом столбце нашей таблицы можно представить в виде <mathtex>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>, причем каждый остаток получается ровно из одного из членов прогрессии.=Задание множеств==

Воспользуемся данным утверждением, подставив разность арифметической прогресии 1) Перечислением элементов: <mathtex>d A = n</math>. Тогда в каждом из <math>\varphi(n)</math> столбцов есть ровно <math>\varphi(m)</math> чисел{a_1, взаимно простых с <math>m</math>a_2 ... Следовательно всего чисел, взаимно простых и с <math>n</math> и с <math>m</math> равно <math>a_n, ...\varphi(m)\varphi(n)} </mathtex>, что и требовалось доказать.

== Функции # <tex>A \sigma(n)subset B </tex>(A является подмножеством B, каждый элемент из А также принадлежит В (<tex>\tau(n)</tex> и <tex>forall x: x \varphi(n)</tex>, их мультипликативность и значения == Каноническое разложение числа <tex>in A \displaystyle n = Rightarrow x \prod_{i=1}^{r}p_i^{s_i} in B </tex>, где <tex>r</tex> {{---}} количество простых делителей числа <tex>n</tex>, <tex>p_i</tex> {{---}} <tex>i</tex>-ый простой делитель, <tex>s_i</tex> {{---}} максимальная степень вхождения этого простого делителя. ==== Функция <tex>\sigma(n)</tex> ====); Функция # <tex>A \sigma : \mathbb{N} \to \mathbb{N} </tex> определяется как сумма делителей натурального числа <tex>ncap B </tex>(Пересечение множеств А и В:<center><tex>(x \displaystylein A) \sigmawedge (nx \in B) = \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>A \sigma(n)cup B </tex> мультипликативна(Объединение множеств А и В: Для простого числа <math>p</math> легко посчитать <tex>(x \displaystylein A) \sigmavee (px \in B) = p + 1</tex>. При этом легко обобщается для некоторой степени <math>p</math>: );<center># <tex>B \displaystyle\sigma(p^s) = \sum_{k=0}^{s}p^k = \frac{p^{s + 1} - 1}{p - 1} backslash A </tex></center> В силу мультипликативности функции(Разность множеств:<center><tex> (x \displaystyle in B) \sigma wedge (nx \notin A) = \prod_{i = 1}^{r}{\frac{p_{i}^{s_i+1}-1} {p_{i}-1}} </tex></center>; ==== Функция # <tex> \tau(n)varnothing </tex> ==== Функция <tex>\tau: \mathbb{N{---} \to \mathbb{N} </tex> определяется как число положительных делителей натурального числа <tex>n</tex>пустое множество: <center>#* <tex>A \displaystylecup \tau(n) varnothing = \sum_{d | n}1 A </tex></center> Если <math>m</math> и <math>n</math> взаимно просты, то каждый делитель произведения <math>mn</math> может быть единственным образом представлен в виде произведения делителей <math>m</math> и делителей <math>n</math>, и обратно, каждое такое произведение является делителем <math>mn</math>. Отсюда следует, что функция #* <tex>A \tau(n)</tex> cap мультипликативна:<center><math>\tau(mn)varnothing =\tau(m)\tau(n)varnothing </math></centertex> Для простого числа <math>p</math> легко посчитать #* <tex>\displaystyle\tau(p) = 2</tex>. При этом легко обобщается для некоторой степени <math>p</math>forall A: <center><tex>\displaystylevarnothing \tau(p^s) = s + 1 subseteq A </tex></center> В силу мультипликативности функции:<center># <tex> \displaystyle bigcup\limits_{\tau(n) = alpha\prod_{i = 1}^{rin W}(s_i + 1) </tex></center> ==== Функция <tex>A_\varphi(n)alpha</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 bigcup\varphi(n) = \prod_{i = 1}^{r}(p_i^{s_i} - p_i^limits_{s_i - 1}) = j \prod_{i = 1}^{r}p_i^{s_i}(1 - \frac{1in N}{p_i}) A_j = nA_1 \prod_{i = 1}^{r}(1 - cup A_2 \frac{1}{p_i}) cup </tex></center>... == Малая теорема Ферма и теорема Эйлера == {{Теорема|about= Теорема Эйлера |statement = Если #* <math>n</math> и <math>a</math> {{---}} взаимно простые целые числа, то <mathtex>a^{\varphi(n)} bigcup\equiv 1 \ (mod \ n)limits_{0 </math> |proof =Число x <math>\overline{x1}A_x </mathtex> называется вычетом по модулю #* <mathtex>n</math>, если <math>\overline{x} \equiv x \ (mod \ n)</math>. Вычет <math>bigcup\overlinelimits_{x}</math> называется обратимым вычетом, если существует вычет <math>\overline{y}</math>, такой что <math>alpha \overline{xin W}\overlineA_{y} \equiv 1 \ (mod \ n)</math>. Заметим, что вычет <math>\overline{xalpha}</mathtex> обратим тогда и только тогда, когда <math>\overline{x}</math> и <math>n</math> взаимно простытак далее. Это обосновывается тем, что данное выражение можно представить в виде [https://e-maxx.ru/algo/diofant_2_equation линейного диофантово уравнения второго порядка] # <mathtex>A \overline{x}\cdotcup B \overline{y} + m \cdot n = 1</math>cup C . Как видно из статьи, решение существует только при <math>(\overline{x}, n) = 1</math>. В таком случае, у числа <math>n</math> существует всего <math>\varphi(n)</math> обратимых вычетов. Пусть <math>\mathbb{Z}_{n}^{*}subseteq U </mathtex> {{---}} &laquo;множество всех обратимых вычетов по модулю <math>n</math>. Достаточно доказать данную теорему только для вычетоввсего&raquo;, так как мы знаем, что если остаток числа <math>a</math> по модулю <math>n</math> взаимно прост с <math>n</math>, то и само число взаимно просто с <math>n</math>. Напомним, что данный факт был ранее доказан в доказательстве мультипликативности функции Эйлера.&laquo;универсальное множество&raquo;; Рассмотрим вычеты по модулю # <math>n</math>. Так как <math>n</math> и <math>a</math> взаимно просты, то вычет <mathtex>\overline{aA}= U </mathtex> обратим. Пусть \ <mathtex>\overline{b_1}, \overline{b_2}, \dots , \overline{b_{\varphi(n)}}A </mathtex> {{---}} все обратимые вычеты по модулю <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>, что и требовалось доказать. }} Следствием теоремы Эйлера является малая теорема Ферма. У нее также есть доказательство без использования более общей теоремы Эйлера, однако его мы приводить не будемА до U.

|about = Малая теорема Фермаде Моргана|statement = Если целое число <mathtex>a\overline{\bigcup\limits_\alpha A_\alpha} = \bigcap\limits_\alpha \overline{A_\alpha} \\\overline{\bigcap\limits_\alpha A_\alpha} = \bigcup\limits_\alpha \overline{A_\alpha} </mathtex> |proof=Докажем первое утверждение, второе доказывается аналогично.Для того, чтобы доказать равенство множеств, докажем, что первое множество включает второе и простое число наоборот (частый приём при доказательстве равенства двух множеств).# <mathtex>p\overline{\bigcup\limits_\alpha A_\alpha} \subseteq \bigcap\limits_\alpha \overline{A_\alpha}</mathtex>#* Пусть <tex> x \in \left ( \overline{\bigcup\limits_\alpha A_\alpha} \right )</tex>. Значит, не существует <tex>\alpha_1</tex> такого, что <tex>x \in A_{---\alpha_1}} взаимно просты</tex>. Следовательно, то <mathtex>a^x \in \overline{p - 1A_\alpha} </tex> для любого <tex>\equiv 1 alpha</tex> и <tex>x \ in \left (mod \ pbigcap\limits_\alpha \overline{A_\alpha} \right )</mathtex>. |proof = Так как #* В силу выбора <mathtex>px</mathtex> (любой элемент множества <tex> \overline{\bigcup\limits_\alpha A_\alpha}</tex>) следует искомое включение.# <tex>\bigcap\limits_\alpha \overline{---A_\alpha}\subseteq \overline{\bigcup\limits_\alpha A_\alpha} простое, то <math/tex>#* Пусть <tex>x \varphiin \left (p\bigcap\limits_\alpha \overline{A_\alpha} \right ) = p - 1</mathtex>. Воспользуемся теоремой Эйлера, тогда Тогда для любого <tex>\alpha</tex> <mathtex>a^x \in \overline{A_\varphi(p)alpha} = a^</tex>, то есть, <tex>x \notin A_\alpha</tex>. Поскольку <tex>x</tex> не входит ни в одно объединяемое множество, то <tex>x \notin \bigcup\limits_\alpha A_\alpha</tex>, то есть, <tex>x \in \overline{p - 1} \equiv 1 bigcup\limits_{\ (mod alpha} A_\ p)alpha}</mathtex>#* Аналогично, что и требовалось доказатьв силу выбора <tex>x</tex> выполняется искомое включение. 

== Различные свойства функции Эйлера == {{Теорема|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>A \displaystyle = \frac{\displaystyle\prod_{i = 1}^{r_b}p_i^{\beta_i - 1}(p_i - 1cup B)}{\displaystyle\prod_{i cap C = 1}^{r_a}p_i^{\alpha_i - 1}(p_i - 1)} = A \displaystyle(\prod_{i = 1}^{r_a}p_i^{\beta_i - \alpha_i}cap C) \cdot \displaystylecup (B \prod_{i = r_a + 1}^{r_b}p_i^{\beta_i - 1}(p_i - 1)cap C)</tex>, а значит, <math>\varphi(a)\,|\, \varphi(b)</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> ровно <mathtex>\varphi(q)</math>. Так как, все <math>n</math> дробей мы представили в несократимом виде, где знаменатель является делителем <math>n</math>, то <math>\displaystyle \sum_{d | n} A \varphi(dcap B) = n</math>, так как всего дробей <math>n</math>, что и требовалось доказать. }} : {{Теорема|about = Обобщённая мультипликативность |statement = Пусть <math>n</math> и <math>m</math> {{---}} любые два натуральных числа, а <math>d = (n,\ m)</math>, тогда:: <math>\varphi(m \cdot n) cup C = \varphi(m) A \cdot \varphi(n)\cdot\frac{d}{\varphi(dcup C)}</math> |proof =  Пусть <math>(m,\,n)=d,</math> тогда <math>m = m'd, \; n = n'd,</math> причем в общем случае <math>cap (m',B \,dcup C) \neq 1</math> и <mathtex>(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> }} == Применение теоремы Эйлера в других задачах == ==== Задача об ожерельях ==== {{Задача|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>. == Алгоритм ==Основной идеей алгоритма является формула <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>]