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

Возьмем некоторое целое число $n$. Если посмотреть на числа $1..n-1$, то какая-то часть из этих чисел будет взаимно проста с самим $n$.

Функция Эйлера как раз и представляет собой количество чисел взаимно простых с n и обозначается как φ(n). Иными словами:

φ(n) = count(gcd(i, n) == 1), при 1 ≤ i ≤ (n - 1)

Например, для φ(24) взаимно простыми будут числа 1, 5, 7, 11, 13, 17, 19, 23. Т.е. φ(24) = 8.

Кажется, что эта функция абсолютно бессмысленна. Но она имеет и практическое применение. Через нее выводится теорема Эйлера, а следом и малая теорема Ферма, благодаря которой работает шифрование RSA.