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

Определение. Функция Эйлера φ(n) определяется как количество натуральных чисел, не превосходящих n и взаимно простых с n.
Свойство 1 (очевидное) Свойство 2 (мультипликативность). Определение Функция f:N→Z называется мультипликативной, если f(mn)=f(m)f(n) для любых взаимно простых m,n.
 

Функция φ(p^s) для простых p

Для простого числа p легко посчитать φ(p)=p−1.
На некоторую степень p формулу можно обобщить: φ(p^s)=p^s−p^s−1

Обосновывается следующим образом:
Все не взаимно простые с p^s числа в диапазоне от 1 до p^s, очевидно, кратны p.
Всего таких чисел p^s−1.

Функции σ(n), τ(n) и φ(n), их мультипликативность и значения
Пусть \(n = p_1^{s_1}\cdot ...\cdot p_r^{s_r}\), где r - количество простых делителей числа n,
 p_i — i-ый простой делитель, s_i — максимальная степень вхождения этого простого делителя
 

Функция σ:N→N определяется как сумма делителей натурального числа n: \(σ(n)=\displaystyle\sum_{d/n}d\)
можно доказать, что \(σ(n)=\displaystyle\prod_{i=1}^{r} \frac{p_i^{s_i+1}-1}{p_i - 1}\)
 

Функция τ(n)

Функция τ:N→N определяется как число положительных делителей натурального числа n: \(τ(n)=\displaystyle\sum_{d/n} 1\)
несложно показать, что \(τ(n)=\displaystyle\prod_{i=1}^{r} (s_i +1)\)
 

Функция φ(n)

В силу мультипликативности функции:
 \(φ(n)=\displaystyle\prod_{i=1}^{r} (p_i^{s_i} -p_i^{s_i-1} ) =\displaystyle\prod_{i=1}^{r} p_i^{s_i}\cdot( 1 -\frac{1}{p_i} ) =n\cdot \displaystyle\prod_{i=1}^{r}( 1 -\frac{1}{p_i} ) \)

 

Вычисление функции Эйлера может быть основано на последней формуле или на следующем (аналогичном) способе:
def min_del(n):
    if n % 2 == 0 : return 2
    if n < 9 : return n
    d = 3
    while d * d <= n :
        if n % d ==0 : return d
        d += 2
    return n    
n = int(input())
ans1, ans2 = n, min(1, n -1)
while n > 1 :
  d = min_del(n)
  ans1 //= d
  ans2 *= (d-1)
  while n % d == 0 :
    n //= d
print(ans1 * ans2)  
    

 

Малая теорема Ферма и теорема Эйлера

Теорема (Теорема Эйлера):

Если n и a — взаимно простые целые числа, то aφ(n)≡1 (mod n)

Теорема (Малая теорема Ферма):

Если целое число a и простое число p — взаимно просты, то ap−1≡1 (mod p)

(Малую теорему Ферма можно считать следствием из теоремы Эйлера)

Различные свойства функции Эйлера

Теорема:

Если для каких-то натуральных чисел a и b верно, что a|b, тогда верно и φ(a)|φ(b)

 

Теорема:

Для любого натурального числа n выполнено равенство \(n=\displaystyle\sum_{d/n}φ(d)\)

 

Теорема (Обобщённая мультипликативность):

Пусть n и m — любые два натуральных числа, а d=(n, m), тогда: \(φ(m⋅n)=φ(m)⋅φ(n)⋅\frac{d}{φ(d)}\)