We are trying to show that the Euler totient function , which counts how many numbers from to share no common factors with , is *multiplicative*, that is, whenever and share no common factors. In my previous post, we looked at some illustrations, for example:

The dark blue squares are those counted by , and the light blue rows and columns are those counted by and . We noted what these pictures are telling us: because we know from the Chinese Remainder Theorem that the numbers from to correspond exactly to pairs of numbers , showing that is multiplicative really comes down to showing the following fact:

**is relatively prime to**

*if and only if*is relatively prime to and is relatively prime to .In other words, the dark blue cells show up precisely at the intersections of light blue rows and columns. Let’s prove this!

First, if shares no common factors with the product , then it can’t possibly share any common factors with or individually. This is because any divisor of is also a divisor of , and likewise for ; so if did share any common factor with, say, , then it would automatically be a common factor with . The converse is also true: if shares no common factors with and also shares no common factors with , then it can’t share any common factors with . That is,

**(A) is relatively prime to**

*if and only if*is relatively prime to and is relatively prime to .For the second piece of the puzzle, note that by definition, for some integer . That is, is what is left over after we subtract some number of copies of from . If shares a common factor with , then so does , since we could factor out of both and . Likewise, if we add to both sides to get , we can see that if shares a common factor with , then so does —since once again we could factor out of both and . Thus we have shown that

**shares a common factor with if and only if shares a common factor with ,**

or, taking the contrapositive of this statement,

**(B) is relatively prime to if and only if is relatively prime to .**

Now let’s put the puzzle pieces together:

which is exactly what we set out to prove.

The Chinese Remainder Theorem tells us that when and are relatively prime, there is a 1-1 matchup between the numbers and the pairs of numbers such that and . But we now know we can make an even finer distinction: which are relatively prime to are in 1-1 correspondence with pairs where is relatively prime to and is relatively prime to . Hence, .