This post gives a proof that Euler’s phi function is multiplicative. The proof is a simpler and more elegant proof, as compared to the one presented here. The combinatorial argument is greatly simplified using the Chinese remainder theorem (abbreviated CRT).
The letter is used below to denote the modulus in modular arithmetic. The phi function is defined to be the count of all the integers such that and are relatively prime. If is prime, then since all integers from to have no factors in common with (other than 1). If , then since 1, 3, 7, and 9 are the only numbers that are relatively prime to .
To properly work with the phi function, conmsider the following setting. Given a modulus , a set of interest is . This is the set of all least resdues modulo , i.e., every integer is congruent modulo to exactly one element of . Another set of interest is , which is the set of all elements in such that and are relatively prime. In other words, is defined to be the cardinality of the set .
The set is called the ring of integers modulo since it satisfies the definition of a ring with regard to addition and multiplication modulo . The set with the multiplication modulo is a group, i.e. every element of has a multiplicative inverse with respect to the binary operation of multiplication modulo . The set is called the multiplicative group of integers modulo . The fact that is a group is established by the following theorem, which is proved here.
Theorem 1
Let be an integer in . The following conditions are equivalent.
 The numbers and are relatively prime, i.e. .
 There is a such that .
 Some positive power of modulo is , i.e., for some positive integer .
Another interesting fact to point out is that when is a prime number, is a field, i.e. it is a commutative ring in which every nonzero element has a multiplicative inverse. Another terminology that is used by some authors is that the elements in that have multiplicative inverses are called units. Thus is also called the group of units of the ring of integers modulo . Our notation here is not standard. The usual notation for the ring is . The usual notation for is .
The phi function is multiplicative in the following sense.
Theorem 2
Let and be positive integers such that they are relatively prime. Then .
Theorem 2 is established by the following results.
Lemma 3
Let and be positive integers such that they are relatively prime. Then the set and the set have the same cardinality.
Proof
To prove that the two sets have the same cardinality, we define a bijection , i.e. is a onetoone function that maps onto the set . For each , define where with and with .
To see that is onetoone, let . Then we have and . By the Chinese remainder theorem, . Since , .
To show that maps onto the set , let . Consider the equations and . By CRT, these two equations have a simultaneous solution that is unique modulo . This means that .
Lemma 4
Let and be positive integers such that they are relatively prime. Then the set and the set have the same cardinality.
Proof
The same mapping defined in the proof of Lemma 3 is used. We show that when is restricted to the set , it is a bijection from onto the set . First, we show that for any , is indeed in . To see this, note that and are relatively prime. So it must be that and are relatively prime too and that and are relatively prime.
The function is onetoone as shown above. The remaining piece is that for each , there is some such that . As in the proof of Lemma 3, there is some such that . Note that and are relatively prime and and are relatively prime. This means that and are relatively prime (see Lemma 4 here). Thus the function is a onetoone from onto .
Proof of Theorem 2
Lemma 4 shows that the set and the set have the same cardinality. First, is the cardinality of the set . Theorem 2 is established by noting that is the cardinality of .
____________________________________________________________________________
Evaluating the phi function
The combinatorial argument for is greatly simplified by using the Chinese remainder theorem. Compare the above proof with the lengthier proof in an earlier post (see Theorem 3 here). With the multiplicative property of the phi function, we can evaluate the phi function for any positive integer.
For any positive integer , consider its unique prime factorization . Then we have:
In the above evaluation, this fact is used. For any prime , (see see Theorem 2 here). We also use the extended version of Theorem 2: if are pairwise relatively prime, then

.
The extended result is to extend the product to more than two numbers. It is derived by a simple inductive argument.
____________________________________________________________________________
A formula for the phi function
The above evaluation leads us to the following way to express the phi function. For , we have the following:
In the above product, the ranges over all prime divisors of . A quick example: for ,
One comment. For the above formula to work, we only need to know the prime divisors of the number, not necessarily the powers of the primes. For example, for 33075, we only need to know that the prime divisors are 3, 5 and 7.
____________________________________________________________________________
Pingback: Speeding up modular exponentiation using CRT  Exploring Number Theory