Изменения

Перейти к: навигация, поиск

Функция Эйлера

3791 байт убрано, 16:42, 24 декабря 2020
Отмена правки 75525, сделанной MetaMockery (обсуждение)
{{Определение
|definition=
Функция Эйлера <tex>f : \mathbb{N} \to \mathbb{Z} varphi (a) </tex> называется определяется для всех целых положительных ''мультипликативной'a', если '' и представляет собою число чисел ряда <tex>f(mn) = f(m)f(n)0, 1, \ldots, a-1 </tex> для любых , взаимно-простых <tex>m, n</tex>с '''a'''.
}}
 
{{Определение
|definition=
''Функция Эйлера'' <tex>\varphi (n) </tex> - определяется как количество натуральных чисел, не превосходящих <tex>n</tex> и взаимно-простых с <tex>n</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>. Тогда, если <math>GCD(d, m) = 1</math>, то остатки всех этих <math>m</math> чисел по модулю <math>m</math> разные, а значит образуют все множество остатков <math>\{0, \dots , m - 1\}</math>, причем каждый остаток получается ровно из одного из членов прогрессии.
 
Подставив в данные рассуждения <math>d = 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>\sigma(n)</tex> ====
 
Каноническое разложение числа <tex>\displaystyle n = \prod_{i=1}^{r}p_i^{s_i} </tex>
 
Функция <tex>\sigma : \mathbb{N} \to \mathbb{N} </tex> определяется как сумма делителей натурального числа <tex>n</tex>:
: <tex>\displaystyle\sigma(n) = \sum_{d | n}d </tex>
 
Для простого числа <math>p</math> легко посчитать <tex>\displaystyle\sigma(n) = \sum_{k=0}^{}d </tex>
 
Функция <tex>\sigma(n)</tex> мультипликативна. Значит <tex>\displaystyle\sigma(n) = \sum_{d | n}d </tex>
 
 
== sigma и tau функции, их мультипликативность и значение ==
 
==== Примеры: ====
MetaMockery
69
правок
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Служебная:Сравнение_версий/75536»

Навигация