
φ(n) is the number of positive integers not larger than n that are coprime to n. (Coprime is defined this way: two numbers are coprime when they share no factor other than 1.) Note that φ(1)=1, because 1 is coprime to itself.
If p is prime then φ(p)=p1.
If p is prime then φ(p^{n}) = p^{n1}(p1)
Totient is a multiplicative function  that means when a and b are coprime (i.e. GCD(a,b)=1), then φ(ab) = φ(a) φ(b).
Mathworld says that by convention, φ(0) is defined as 1, even though there are no of positive integers that are not larger than 0, so by the definition, φ(0) really should be 0. Moreover, Mathematica defines EulerPhi[0]=0 to be consistent with FactorInteger[0]
Together, these rules give the following formula for the totient of any number, given its prime factorization:
Let x = p_{1}^{e}1 p_{2}^{e}2 ... p_{n}^{e}n
φ(x) = p_{1}^{e}1^{1} (p_{1}1) p_{2}^{e}2^{1} ( p_{2}1)...p_{n}^{e}n^{1} ( p_{n}1)
Note that p^{e1} (p1) = p^{e} (11/p). Using this fact, the formula for φ(x) can be rewritten as follows:
φ(x) = p_{1}^{e}1 (11/p_{1}) p_{2}^{e}2 ( 11/p_{2})...p_{n}^{e}n ( 11/p_{n})
and then by pulling out the factors p_{1}^{e}1 p_{2}^{e}2 ... p_{n}^{e}n , which together equal x, we get the simplest formula:
φ(x) = x (11/p_{1}) ( 11/ p_{2})...( 11/ p_{n})
Example
17640 = 2^{3} 3^{2} 5 7^{2}
φ(17640) = 2^{2} (21) 3^{1} (31) 5^{0} (51) 7^{1} (71) = 4032
φ(17640) = 17640 (1/2)(2/3)(4/5)(6/7) = 4032
Additional facts:
Mathworld says φ(n^{2}) = nφ(n), but this can be generalized further: φ(n^{k}) = n^{k1}φ(n)
In addition, Mathworld provides this factoid, from Euclid:
Σ φ(d) = n
^{dn}
Proof:
We will prove this sumoftotientsofdivisors theorem by partitioning the set {1,2,3,...,n} into subsets according to each element's greatest common divisor with n. Each subset of {1,2,3,...,n} will be called Q(g), the set of all integers between 1 and n inclusive, such that gcd(x,n) = g. The Q(g) sets don't overlap, and their union is {1,2,3,...,n}, so the sum of the cardinality of the Q(g) sets is n. Also, there is a onetoone correspondence between the elements of Q(g) and the "proper coprimes" of n/g, which completes the proof.
For example, if n=12, then the set {1,2,3,4,5,6,7,8,9,10,11,12} is partitioned into these sets:
Q(1) = {1,5,7,11}
Q(2) = {2,10}
Q(3) = {3,9}
Q(4) = {4,8}
Q(6) = {6}
Q(12) = {12}(All other Q(g) are empty sets)
These "Q" sets have the following three properties:
Q(g) is nonempty if and only if g divides n. (If g weren't a divisor of n, then it could never be the greatest common divisor of n and some other number).
If x belongs to Q(g) for a given g, then it can't belong to another Q(h) where h≠g, because it wouldn't be possible for gcd(x,n)=g and gcd(x,n)=h.
For all x between 1 and n inclusive, there exists a g such that gcd(x,n) = g
Put together, these three properties imply that the union of all the Q(g) sets (for each g a divisor of n), which are pairwise mutually exclusive, is the set {1,2,3,...,n}. And therefore, the sum of the cardinalities of each Q(g) equals n.
Now consider the set Q(g)/g, which is the set obtained by dividing each element of Q(g) by g. You know all the elements of Q(g)/g are integers, because g is a divisor of every element of Q(g). Let's look at our example, where n=12, again:
Q(1) = {1,5,7,11}
Q(2) = {2,10}
Q(3) = {3,9}
Q(4) = {4,8}
Q(6) = {6}
Q(12) = {12}Q(1)/1 = {1,5,7,11}
Q(2)/2 = {1,5}
Q(3)/3 = {1,3}
Q(4)/4 = {1,2}
Q(6)/6 = {1}
Q(12)/12 = {1}
Now we will show that Q(g)/g is the set of "proper coprimes" of n/g. By "proper coprimes" I mean positive numbers coprime to n that don't exceed n. Keep in mind that the set of proper coprimes of n/g contains φ(n/g) elements, so by showing that Q(g)/g is the set of proper coprimes of n/g, we will show that Q(g) = φ(n/g). Also, since the set {n/g  g divides n} is equal to the set {d  d divides n}, and the union of the Q(g) sets is {1,2,3,...,n}, the result will follow, and the proof will be complete.
Suppose x is an element of Q(g)/g. That means gx is an element of Q(g), so gcd(gx,n)=g, so gcd(x,n/g)=1, which means x is a coprime of n/g. gx does not exceed n, so x does not exceed n/g, which means x is a proper coprime of n/g.
Now suppose x is a proper coprime of n/g. gcd(x,n/g)=1, so gcd(gx,n)=g, so x is an element of Q(g)/g.
Therefore, Q(g) = φ(n/g). The proof is complete.
Now, let's take one more look at our example, filling in the part about φ(n/g):
Q(1) = {1,5,7,11}
Q(2) = {2,10}
Q(3) = {3,9}
Q(4) = {4,8}
Q(6) = {6}
Q(12) = {12}Q(1)/1 = {1,5,7,11}
Q(2)/2 = {1,5}
Q(3)/3 = {1,3}
Q(4)/4 = {1,2}
Q(6)/6 = {1}
Q(12)/12 = {1}φ(12/1) = φ(12) = 4
φ(12/2) = φ(6) = 2
φ(12/3) = φ(4) = 2
φ(12/4) = φ(3) = 2
φ(12/6) = φ(2) = 1
φ(12/12) = φ(1) = 1Union of Q(g):
{1,2,3,...,12}Sum of φ(d): 12
Proof of: For any integer n, the sum of the totient values of each of its divisors equals n.
Fermat's Theorems  Fermat's Little Theorem, in particular.
Euler's Totient Theorem  a generalization of Fermat's Little Theorem
Number theory theorems, page 4: Totient.
Group  definition of a "group", which has properties closure, associativity, identity, and inverse.
The proof that primes of the form 4k+3 can be expressed as the sum of four squares uses Fermat's Little Theorem.
A bunch of Ring Theory theorems and definitions.
Proof that there is no solution to the Diophantine equation A^{4}+B^{4}=C^{2}, which means Fermat's last theorem is true
Highly Composite Numbers  numbers, n, such that no number smaller than n has as many factors as n.
The webmaster and author of this Math Help site is Graeme McRae.