Euler's function

Quick Reference

For a positive integer n, let (n) be the number of positive integers less than n that are relatively prime to n. For example, (12)=4, since four numbers, 1, 5, 7 and 11, are relatively prime to 12. This function , defined on the set of positive integers, is Euler's function. It can be shown that, if the prime decomposition of n is n=p1α1p2α2prαr, thenEuler proved the following extension of Fermat's Little Theorem: If n is a positive integer and a is any integer such that (a, n)=1, then aϕ(n) ≡ 1 (mod n).

Subjects: Mathematics.

Reference entries