Reduced Residue System Question Suppose $\gcd(m,n) = 1$. Prove that if $x$ assumes all values in a reduced residue system modulo $m$, and $y$ assumes all values in a reduced residue system modulo $n$, then $nx+my$ assumes all values in a reduced residue system modulo $mn$.
$\{r_1, r_2, \ldots , r_s\}$ forms a reduced residue system modulo $m$ if


*

*$\gcd(r_i, m) = 1$ for each $i$

*$r_i \neq r_j$ whenever $i \neq j$

*for each integer $n$ relatively prime to $m$ there corresponds an $r_i$ such that $n \equiv r_i \pmod m$
I appreciate your help.
 A: A reduced residue system modulo $mn$ is any set of $\varphi(mn) = \varphi(m) \varphi(n)$ integers which are incongruent modulo $mn$ and each of which is coprime with $mn$. 
($\varphi(mn)$ is Euler's totient function, which is multiplicative).
There are  $\varphi(m) \varphi(n)$ distinct ways of forming the sum $nx + my$ by choosing $x$ to be one of the $\varphi(m)$ integers in a reduced residue system modulo $m$ and choosing $y$ to be one of the $\varphi(n)$ integers in a reduced residue system modulo $n$. We have to prove that these $\varphi(m) \varphi(n)$ distinct ways of forming the sum produce $\varphi(m) \varphi(n)$ incongruent integers modulo $mn$ each of which is coprime with $mn$.
First, suppose that gcd$(nx + my, mn) = d > 1$. Since $d|(nx+my)$, it must be the case that if $d|m$ then $d|nx$, but this is impossible since gcd$(m, n) = 1$ and gcd$(m, x) = 1$. Similarly, since $d|(nx+my)$, it must be the case that if $d|n$ then $d|my$, but this is impossible since gcd$(m, n) = 1$ and gcd$(n, y) = 1$. Therefore we cannot have either $d|m$ or $d|n$, but this is a contradiction since $d|mn$. Therefore $d > 1$ is impossible, so each sum $nx + my$ is coprime with $mn$. 
Next, suppose that $nx_i + my_i$ and $nx_j + my_j$ are any two distinct ways of forming the sum, i.e., either $x_i \neq x_j$ in a reduced residue system modulo $m$ and/or $y_i \neq y_j$ in a reduced residue system modulo $n$. We have to prove that $nx_i + my_i$ and $nx_j + my_j$ must then be incongruent modulo $mn$. Prove this by contradiction. Suppose they are congruent modulo $mn$. Then their difference is divisible by $mn$ so for some integer $k$ we must have 
$n(x_i - x_j) + m(y_i - y_j) = kmn$
Since $m$ divides both $m(y_i - y_j)$ and $kmn$, it must also divide $n(x_i - x_j)$ but this is impossible since $m$ cannot divide either $n$ or $x_i - x_j$. This contradiction shows that the two sums cannot be congruent modulo $mn$.      
We have therefore proved that the $\varphi(m) \varphi(n)$ distinct ways of forming the sum $nx + my$ produce $\varphi(m) \varphi(n)$ incongruent integers modulo $mn$ each of which is coprime with $mn$, i.e., $nx + my$ must assume all the values in a reduced residue system modulo $mn$. 
A: Hint: From the definition of Reduced Residue System, since both $x$ and $y$ form a reduced residue system modulo $m$ and $n$ , they have $\phi(m)$ and $\phi(m)$ elements respectively and also both $\gcd(x,m)=1$ and $\gcd(y,n)=1$
Now look at $nx + my \pmod {mn}$, if $nx +my$ is always coprime to $mn$ and no two values for  $nx + my$ are congruent modulo $mn$ then it forms a reduced residue system modulo $mn$. Remember $\gcd(m,n)=1$, $\gcd(x,m)=1$ and $\gcd(y,n)=1$ ...
Can you continue?
