Изменения

''Функция Эйлера'' <tex>f : \mathbb{N} \to \mathbb{Z} varphi (n) </tex> называется ''мультипликативной''определяется как количество натуральных чисел, если не превосходящих <tex>f(mn) = f(m)f(n)</tex> для любых и взаимно-простых с <tex>m, n</tex>.

''Функция Эйлера'' <tex>f : \mathbb{N} \to \varphi (n) mathbb{Z} </tex> - определяется как количество натуральных чиселназывается ''мультипликативной'', не превосходящих если <tex>f(mn) = f(m)f(n)</tex> и для любых взаимно-простых с <tex>m, n</tex>.

|statement = Для любых взаимно-простых чисел <tex>m, n</tex> : <math>\varphi(mn)=\varphi(m)\varphi(n).</math>

Запишем <math>nmn \cdot m</math> натуральных чисел, не превосходящих <math>nmn \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>nmn \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>kn</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>n\{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>, что и требовалось доказать.

Каноническое разложение числа <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 : \mathbb{N} \to \mathbb{N} </tex> определяется как сумма делителей натурального числа <tex>n</tex>:

<center><tex> \displaystyle \sigma (n) = \prod_{i = 1}^{r}{\frac{p_{i}^{s_i+1}-1} {p_{i}-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>

<center><tex> \displaystyle \tau(n) = \prod_{i = 1}^{r}(s_i + 1). </tex></center> 

Обосновывается следующим образом: Все не взаимно-простые с <math>p^s</math> числа в диапазоне от 1 до <math>p^s</math>, очевидно, кратны <math>p</math>. Всего таких чисел <math>p^{s - 1}</math>.

|statement = Если <math>n</math> и <math>a</math> {{- --}} взаимно-простые целые числа, то <math>a^{\varphi(n)} \equiv 1 \ (mod \ 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>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>, что и требовалось доказать.

|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>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>, что и требовалось доказать. }}

|proof = Данную теорему можно доказать "напролом", пользуясь формулой для разложив по формуле <math>\varphi(d)</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>, что и требовалось доказать.