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.