# On a reduced residue system mod mn

In this post I provide a proof of the assertion 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$ (provided that $\gcd(m,n) = 1$).

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$. Then $d|m^2n$ and $d|m^2y$ (the latter is true because $m^2y$ is a linear combination of $nx + my$ and $mn$, namely $m(nx + my) - x(mn)$), so $d|m^2$ since $\gcd(n, y) = 1$. In a similar way we can show that $d|n^2$. But since $d|(nx+my)$, it must be the case that if $d|m$ then $d|nx$, and this is impossible if $\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|m^2$ and $d|n^2$. 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 $\gcd(m, n) = 1$ and $m$ cannot divide $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$.