I need an explanation of the following theorem from Leveque's Elementary Theory of Numbers (page 44):
Theorem 3-7 If $(m,n)=1$ then $\varphi(mn)=\varphi(m)\varphi(n)$
Proof: Take integers m,n with $(m,n)=1$, and consider the numbers of the form $mx+ny$. If we can so restrict the values which x and y assume that these numbers form a reduced residue system (mod mn), there must be $\varphi(mn)$ of them. But their number is also the product of the number of values which x assumes and the number of values which y assumes. Clearly, in order for $mx+ny$ to be prime to m, it is necessary that $(m,y)=1$, and likewise we must have $(n,x)=1$. Conversely, if these last two conditions are satisfied, then $(mx+ny,mn)=1$, since in this case any prime divisor of m, or of n, divides exactly one of the two terms in$ mx+ny$. Hence let x range over a reduced residue system (mod n), say $x_1,...,x_{\varphi(n)}$, and let y run over a reduced residue system (mod m), say $y_1,...,y_{\varphi(m)}$. If for some indices $i,j,k,l$ we have
$$mx_i+ny_j \equiv mx_k + ny_l (mod\text{ } mn)$$
then
$$m(x_i-x_k)+n(y_j-y_l)\equiv 0(mod \text{ } mn)$$
Since divisibility by mn implies divisibility by m, we have
$$m(x_i-x_k)+n(y_j-y_l) \equiv 0(mod\text{ } m)$$ $$n(y_j-y_l) \equiv 0 (mod\text{ } m)$$ $$y_j \equiv y_l(mod\text{ } m)$$
whence $j =l$. Similarly, $i=k$. Thus the numbers $mx+ny$ so formed are incongruent (mod mn). Now let a be any integer prime to mn: in particular, $(a,m)=1$ and $(a,n)=1$. Then theorem 2-6 shows that there are integers X,Y (not necessarily in the chosen reduced residue systems)) such that $mX+nY=a$, whence also $mX+nY \equiv a(mod\text{ } mn)$. Since $(m,Y)=(n,X)=1$, there is an $x_i$ such that $X\equiv x_i(mod n)$ and there is a $y_j$ such that $Y \equiv y_j(mod\text{ } m)$. This means that there are integers $k,l$ such that $X=x_i+kn$, $Y=y_j+lm$. Therefore,
$$mX+nY=m(x_i+kn)+n(y_j+lm)\equiv mx_i+ny_j \equiv a(mod\text{ } mn)$$
Hence, as x and y run over fixed reduced residue systems (mod n) and (mod m), respectively, $mx+ny$ runs over a reduced residue system (mod mn), and the proof is complete.
The book was doing a very good job at explaining theorems in an easy way up to the latter. I couldn't hate that proof more. It obviates a lot of things that are hard to understand. I underlined some of things that I didn't get but there are still more. I would be glad if someone provides a simplified or better explained proof for this theorem. The first thing that I would like to understand is when they refer to x ranging over a residue system. What does that mean?. Does that mean x is congruent to some term in that specific residue system mod n?
First I will try to help you go through the given proof and then I'll show you an easier proof.
The first bold part is just an introduction to what the author will try to prove. For the second part note that if $p \mid m$ then $p \not \mid ny \implies p \not \mid ny + mx$. Similar argument for $x$ shows that $(ny + mx, mn) = 1$. And for the third part note that by Bezout's Lemma we have that there exist integers $x,y$ s.t. $mx + ny = 1 \implies m(ax) + n(ay) = a \implies mX + nY = a$. Obviously this proves the existence of $X$ and $Y$. I assume that the rest of the proof is understandable for you.
Anyway this proof seems rather bad. Actually one can first proof that $\phi(n) = n \prod_{p \mid n} \left(1 - \frac 1p \right)$ by Inclusion-Exclusion Principle and then the multiplicativity is trivial. Also if you are introduced to Ring Theory (Chinese Remainder Theorem) then there is a quite short and easy proof.