|
|
| Строка 27: |
Строка 27: |
| | | | |
| | == Функции <tex>\sigma(n)</tex>, <tex>\tau(n)</tex> и <tex>\varphi(n)</tex>, их мультипликативность и значения == | | == Функции <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>\sigma(n)</tex> ==== | | ==== Функция <tex>\sigma(n)</tex> ==== |
| | | | |
| − | Функция <tex>\sigma : \mathbb{N} \to \mathbb{N} </tex> определяется как сумма делителей натурального числа <tex>n</tex>
| + | Каноническое разложение числа <tex>\displaystyle n = \prod_{i=1}^{r}p_i^{s_i} </tex> |
| − | <center><tex>\displaystyle\sigma(n) = \sum_{d | n}d </tex></center>
| |
| − | | |
| − | Для простого числа <math>p</math> легко посчитать <tex>\displaystyle\sigma(p) = p + 1</tex>. При этом легко обобщается для некоторой степени <math>p</math>:
| |
| − | <center><tex>\displaystyle\sigma(p^s) = \sum_{k=0}^{s}p^k = \frac{p^{s + 1} - 1}{p - 1} </tex></center>
| |
| − | | |
| − | В силу мультипликативности функции:
| |
| − | <center><tex> \displaystyle \sigma (n) = \prod_{i = 1}^{r}{\frac{p_{i}^{s_i+1}-1} {p_{i}-1}}. </tex></center>
| |
| − | | |
| − | | |
| − | ==== Функция <tex>\tau(n)</tex> ====
| |
| − | | |
| − | Функция <tex>\tau: \mathbb{N} \to \mathbb{N} </tex> определяется как число положительных делителей натурального числа <tex>n</tex>:
| |
| − | <center><tex>\displaystyle\tau(n) = \sum_{d | n}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>
| |
| − | | |
| − | Для простого числа <math>p</math> легко посчитать <tex>\displaystyle\tau(p) = 2</tex>. При этом легко обобщается для некоторой степени <math>p</math>:
| |
| − | <center><tex>\displaystyle\tau(p^s) = s + 1 </tex></center>
| |
| − | | |
| − | В силу мультипликативности функции:
| |
| − | <center><tex> \displaystyle \tau(n) = \prod_{i = 1}^{r}(s_i + 1). </tex></center>
| |
| − | | |
| − | | |
| − | ==== Функция <tex>\varphi(n)</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 \varphi(n) = \prod_{i = 1}^{r}(p_i^{s_i} - p_i^{s_i - 1}) = \prod_{i = 1}^{r}p_i^{s_i}(1 - \frac{1}{p_i}) = n\prod_{i = 1}^{r}(1 - \frac{1}{p_i}) </tex></center>
| |
| − | | |
| − | | |
| − | | |
| − | == Малая теорема Ферма и теорема Эйлера ==
| |
| − | | |
| − | {{Теорема
| |
| − | |about= Теорема Эйлера
| |
| − | | |
| − | |statement = Если <math>n</math> и <math>a</math> - взаимно-простые целые числа, то <math>a^{\varphi(n)} \equiv 1 \ (mod \ n)</math>
| |
| − | | |
| − | |proof =
| |
| − | Число <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> взаимно-просты. В таком случае, у числа <math>n</math> существует всего <math>\varphi(n)</math> обратимых вычетов. Пусть <math>\mathbb{Z}_{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>, что и требовалось доказать.
| |
| − | | |
| − | }}
| |
| − | | |
| − | Следствием теоремы Эйлера является малая теорема Ферма. У нее также есть доказательство без использования более общей теоремы Эйлера, однако его мы приводить не будем.
| |
| − | | |
| − | | |
| − | {{Теорема
| |
| − | |about = Малая теорема Ферма
| |
| − | | |
| − | |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>n</math> выполнено равенство <math>\displaystyle n = \sum_{d | n} \varphi(d)</math>
| + | Функция <tex>\sigma : \mathbb{N} \to \mathbb{N} </tex> определяется как сумма делителей натурального числа <tex>n</tex>: |
| | + | : <tex>\displaystyle\sigma(n) = \sum_{d | n}d </tex> |
| | | | |
| − | |proof = Данную теорему можно доказать "напролом", пользуясь формулой для <math>\varphi(d)</math>, а можно более элегантно:
| + | Для простого числа <math>p</math> легко посчитать <tex>\displaystyle\sigma(n) = \sum_{k=0}^{}d </tex> |
| | | | |
| − | Рассмотрим <math>n</math> дробей <math>\frac{1}{n}, \frac{2}{n}, \dots , \frac{n}{n}</math>.
| + | Функция <tex>\sigma(n)</tex> мультипликативна. Значит <tex>\displaystyle\sigma(n) = \sum_{d | n}d </tex> |
| | | | |
| | | | |
| − | }}
| + | == sigma и tau функции, их мультипликативность и значение == |
| | | | |
| − | == Старые записи ==
| |
| | | | |
| | ==== Примеры: ==== | | ==== Примеры: ==== |
Функция Эйлера
| Определение: |
| Функция [math]f : \mathbb{N} \to \mathbb{Z} [/math] называется мультипликативной, если [math]f(mn) = f(m)f(n)[/math] для любых взаимно-простых [math]m, n[/math]. |
| Определение: |
| Функция Эйлера [math]\varphi (n) [/math] - определяется как количество натуральных чисел, не превосходящих [math]n[/math] и взаимно-простых с [math]n[/math]. |
| Теорема (Мультипликативность функции Эйлера): |
Для любых взаимно-простых чисел [math]m, n[/math]
- [math]\varphi(mn)=\varphi(m)\varphi(n).[/math]
|
| Доказательство: |
| [math]\triangleright[/math] |
|
Запишем [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], что и требовалось доказать. |
| [math]\triangleleft[/math] |
Функции [math]\sigma(n)[/math], [math]\tau(n)[/math] и [math]\varphi(n)[/math], их мультипликативность и значения
Функция [math]\sigma(n)[/math]
Каноническое разложение числа [math]\displaystyle n = \prod_{i=1}^{r}p_i^{s_i} [/math]
Функция [math]\sigma : \mathbb{N} \to \mathbb{N} [/math] определяется как сумма делителей натурального числа [math]n[/math]:
- [math]\displaystyle\sigma(n) = \sum_{d | n}d [/math]
Для простого числа [math]p[/math] легко посчитать [math]\displaystyle\sigma(n) = \sum_{k=0}^{}d [/math]
Функция [math]\sigma(n)[/math] мультипликативна. Значит [math]\displaystyle\sigma(n) = \sum_{d | n}d [/math]
sigma и tau функции, их мультипликативность и значение
Примеры:
[math] \varphi (1) = 1[/math], [math] \varphi (4) = 2[/math],
[math] \varphi (2) = 1[/math], [math] \varphi (5) = 4[/math],
[math] \varphi (3) = 2[/math], [math] \varphi (6) = 2[/math].
Свойства функции Эйлера
- 1. Доказательство: [math] \varphi (p) = p-1 [/math], p — простое, [math] \varphi (p^{\alpha}) = p^{\alpha} - p^{\alpha - 1}[/math].
- Логически понятно, если строго, то выводится из 2 свойства.
- 2. Пусть [math] a = {p_1}^{\alpha_1} {p_2}^{\alpha_2} \ldots {p_k}^{\alpha_k}[/math] — каноническое разложение числа a, тогда
[math] \varphi (a) = a(1 - \frac{1}{p_1}) (1 - \frac{1}{p_2}) \ldots (1 - \frac{1}{p_k})[/math].
- Доказательство: Пусть [math] x [/math] пробегает числа [math] 0,1,2,\ldots,a-1[/math], положим [math] \sigma_x = (a, x)[/math] — НОД. Тогда [math] \varphi(a) [/math] есть число значений [math] \sigma_x [/math], равных единице. Возьмем функцию, которая равна единице, если [math] \sigma_x = 1[/math], и равна нулю в остальных случаях. Вот такая функция : [math]\sum_{d | n} \mu(d) = \begin{cases} 1,&n=1,\\ 0,&n\gt 1.\end{cases}[/math], где [math] \mu(a) [/math] — функция Мебиуса. Отсюда [math] \varphi(a) = \sum_{0 \le x \le a-1}(\sum_{d | a} \mu(d))[/math]. Поскольку справа сумма в скобках берется по всем делителям d числа [math] \sigma_x = ( x , a )[/math], то d делит x и a . Значит в первой сумме справа в суммировании участвуют только те x , которые кратны d . Таких x среди чисел [math] 0,1,2,\ldots,a-1[/math] ровно [math] \frac{a}{d} [/math] штук. Получается, что [math] \varphi(a) = \sum_{d | a} \frac{a}{d}\mu(d) = a\sum_{d | a} \frac{\mu(d)}{d} = a(1 - \frac{1}{p_1}) (1 - \frac{1}{p_2}) \ldots (1 - \frac{1}{p_k})[/math].
- 3. Функция Эйлера является мультипликативной [math] \varphi(a_1 a_2) = \varphi(a_1)\varphi(a_2) [/math].
- Вытекает из первого свойства.
Еще примеры
- [math] \varphi(60) = 60(1 - \frac{1}{2})(1 - \frac{1}{3})(1 - \frac{1}{5}) = 16[/math]
- [math] \varphi(81) = 81 - 27 = 54 [/math]
