# Consider $m$ and $n$ integers $\geq2$ and the set $A$ of all positive numbers smaller than $m$ and relatively prime with $m$

Problem: Consider $m$ and $n$ integers $\geq2$ and the set $A$ of all positive numbers smaller than $m$ and relatively prime with $m$ and $B$ the set of all positive numbers smaller than $n$ and relatively prime with $n$. Also $(m,n)=1$. Define $C=\{na+mb | a \in A, b \in B\}$. Show that any number in $C$ is relatively prime with $mn$.

I was told to use Euler multiplication to work the problem. Any ideas on how to do so or how to begin such proof?

Let's take a prime $p$ such that $p\mid mn$ and $p\mid na+mb$. Since $\gcd(m,n)=1$, we know that $p$ can't divide both $m$ and $n$.
Suppose $p\mid n$. This means two things. First: $p\mid na$ and second: $p\nmid m$. Hence $p$ has to divide $b$, but since $\gcd(n,b)=1$, we have a contradiction. Because of 'symmetry' (we can flip $m$ and $n$ and have the exact same problem), we are done.