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:
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,
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
or, taking the contrapositive of this statement,
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, .
Pingback: Computing the Euler totient function, part 4: totient of prime powers | The Math Less Traveled