Изменения
Нет описания правки
{{Определение
|definition=
''Функция Эйлера'' <tex>f : \mathbb{N} \to \mathbb{Z} varphi (n) </tex> называется ''мультипликативной''определяется как количество натуральных чисел, если не превосходящих <tex>f(mn) = f(m)f(n)</tex> для любых и взаимно-простых с <tex>m, n</tex>.
}}
{{Определение
|definition=
}}
{{Теорема
|about = Мультипликативность функции Эйлера
|statement = Для любых взаимно-простых чисел <tex>m, n</tex> : <math>\varphi(mn)=\varphi(m)\varphi(n).</math>
|proof =
Запишем <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>\sigma(n)</tex>, <tex>\tau(n)</tex> и <tex>\varphi(n)</tex>, их мультипликативность и значения ==
Каноническое разложение числа <tex>\displaystyle n =\prod_{i= Функции 1}^{r}p_i^{s_i} </tex>, где <tex>r</tex> {{---}} количество простых делителей числа <tex>\sigma(n)</tex>, <tex>\tau(n)p_i</tex> и {{---}} <tex>\varphi(n)i</tex>-ый простой делитель, их мультипликативность и значения ==<tex>s_i</tex> {{---}} максимальная степень вхождения этого простого делителя.
==== Функция <tex>\sigma(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> \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 эффективные алгоритмы].
== См. также ==*3. Функция Эйлера является [[Мультипликативность функции, свертка Дирихле|мультипликативнойЗадача об ожерельях]] <tex> \varphi(a_1 a_2) = \varphi(a_1)\varphi(a_2) </tex>.** Вытекает из первого свойства.
==== Еще примеры ==Ссылки ==* <tex> \varphi(60) = 60(1 - \frac[https://ru.wikipedia.org/wiki/Функция_Эйлера Wikipedia {1}{2})(1 - \frac{1--}{3})(1 Функция Эйлера]* [https://e- \frac{1}{5}) = 16<maxx.ru/algo/tex>euler_function Алгоритм нахождения функции Эйлера]* [https://wikichi.ru/wiki/Divisor_function Функция <texmath> \varphi(81) = 81 - 27 = 54 sigma</texmath>]