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, .

##
About Brent

Assistant Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.

Pingback: Computing the Euler totient function, part 4: totient of prime powers | The Math Less Traveled