I came across this question in an Olympiad math book:
Let $\gcd(m,n) = 1$, $A = \{x\mid0\le x \le m-1, \gcd(x,m) = 1\}$ and $B = \{x\mid0\le x \le n-1, \gcd(x,n) = 1\}$. If $C= \{na+mb \mid a \in A, b\in B\}$ then prove that $C$ assumes all values $ \equiv 0 \le x \le mn-1$ modulo $mn$.
I have successfully proved that $\gcd (mn, na+mb) = 1$ for all $a, b.$ This would imply that $\forall c \in C, $ $0 \le c \le mn-1$ taken modulo $mn$.
However I am having difficulty proceeding. My hunch says that it has something to do with Euler's phi-function since the number of elements in $A$ and $B$ are respectively $\phi(m)$ and $\phi(n)$ and $C$ must assume $\phi(mn) \Rightarrow \phi(m) \phi(n)$ elements.
How do I prove that this is valid for all such values?
Your hunch is along the right lines.
Suppose two elements of $C$ were equivalent modulo $mn$; $$ a_1 n + b_1 m \equiv a_2 n + b_2 m \pmod{mn}. $$ Then $mn \mid (a_2 - a_1) n + (b_2 - b_1)m$. Thus the right-hand side is a multiple of $m$, so $m \mid (a_2 - a_1) n$. Since $\gcd(m,n) = 1$, this mean $m \mid (a_2 - a_1)$, i.e. $a_2 \equiv a_1 \pmod{m}$. Since $a_1$ and $a_2$, being from $A$, are between 0 and $m-1$, if they are equivalent modulo $m$ they are in fact equal.
Similarly, $b_2 = b_1$.
We have shown that any distinct choices of $a$ or $b$ yield elements of $C$ which are not equivalent modulo $mn$. Since there are $\phi(m)$ choices for $a$, and $\phi(n)$ choices for $b$, there are $\phi(m)\phi(n)$ elements of $C$, all of which are distinct modulo $mn$, and all of which are relatively prime to $mn$.
But, since $m$ and $n$ are relatively prime, $\phi(mn) = \phi(m)\phi(n)$, so there are only that many natural numbers less than $mn$ and relatively prime to $mn$. So $C$ contains an element equivalent to each.