For a positive integer n, let ϕ‎(n) be the number of positive integers less than n that are coprime to n. For example, ϕ‎(12) = 4, since four numbers, 1, 5, 7, and 11, are coprime to 12. This function ϕ‎, defined on the set of positive integers, is the totient function. It can be shown that, if the prime decomposition of n is $n=p_1^{{\alpha }_1}{p}_2^{{\alpha }_2}\dots p_r^{{\alpha }_r}$, then

Euler 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). The totient function is an arithmetic function.