|
|
| Строка 3: |
Строка 3: |
| | {{Определение | | {{Определение |
| | |definition= | | |definition= |
| − | Функция <tex>f : \mathbb{N} \to \mathbb{Z} </tex> называется ''мультипликативной'', если <tex>f(mn) = f(m)f(n)</tex> для любых взаимно-простых <tex>m, n</tex>. | + | Функция Эйлера <tex>\varphi (a) </tex> определяется для всех целых положительных '''a''' и представляет собою число чисел ряда <tex>0, 1, \ldots, a-1 </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 функции, их мультипликативность и значение ==
| |
| − |
| |
| | | | |
| | ==== Примеры: ==== | | ==== Примеры: ==== |
