In this post I provide a proof of the assertion that if assumes all values in a reduced residue system modulo , and assumes all values in a reduced residue system modulo , then assumes all values in a reduced residue system modulo (provided that ).

A reduced residue system modulo is any set of integers which are incongruent modulo and each of which is coprime with .

( is Euler’s totient function, which is multiplicative).

There are distinct ways of forming the sum by choosing to be one of the integers in a reduced residue system modulo and choosing to be one of the integers in a reduced residue system modulo . We have to prove that these distinct ways of forming the sum produce incongruent integers modulo each of which is coprime with .

First, suppose that . Then and (the latter is true because is a linear combination of and , namely ), so since . In a similar way we can show that . But since , it must be the case that if then , and this is impossible if and . Similarly, since , it must be the case that if then , but this is impossible since and . Therefore we cannot have either or , but this is a contradiction since and . Therefore is impossible, so each sum is coprime with .

Next, suppose that and are any two distinct ways of forming the sum, i.e., either in a reduced residue system modulo and/or in a reduced residue system modulo . We have to prove that and must then be incongruent modulo . Prove this by contradiction. Suppose they are congruent modulo . Then their difference is divisible by so for some integer we must have

Since divides both and , it must also divide but this is impossible since and cannot divide . This contradiction shows that the two sums cannot be congruent modulo .

We have therefore proved that the distinct ways of forming the sum produce incongruent integers modulo each of which is coprime with , i.e., must assume all the values in a reduced residue system modulo .