== Функции <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 : \mathbb{N} \to \mathbb{N} </tex> определяется как сумма делителей натурального числа <tex>n</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 = Для любого Функция <tex>\sigma : \mathbb{N} \to \mathbb{N} </tex> определяется как сумма делителей натурального числа <mathtex>n</mathtex> выполнено равенство :: <mathtex>\displaystyle \sigma(n ) = \sum_{d | n} \varphi(d)</mathtex>
|proof = Данную теорему можно доказать "напролом", пользуясь формулой для Для простого числа <math>p</math> легко посчитать <tex>\displaystyle\varphisigma(n) = \sum_{k=0}^{}d)</mathtex>, а можно более элегантно:
Рассмотрим Функция <mathtex>\sigma(n)</mathtex> дробей мультипликативна. Значит <mathtex>\frac{1}{n}, displaystyle\frac{2}{sigma(n}, \dots , ) = \frac{n}sum_{d | n}d </mathtex>.
}}== sigma и tau функции, их мультипликативность и значение ==
== Старые записи ==
==== Примеры: ====
