69
правок
Изменения
→Функции \sigma(n), \tau(n) и \varphi(n), их мультипликативность и значения
<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></math></center>
Для простого числа <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>.
В силу мультипликативности функции:
