Функция Эйлера
Материал из Википедии — свободной энциклопедии
Функция Эйлера φ(n), где n — натуральное число, равна количеству натуральных чисел, не больших n и взаимно простых с ним.
[править] Свойства
- φ(pn)=(p - 1)pn - 1, если p — простое число
- Функция Эйлера мультипликативна, т. е. φ(ab)=φ(a)φ(b), если a и b взаимно просты.
- (Теорема Эйлера) aφ(m)≡1 (mod m), если a и m взаимно просты.