# Let $p,q$ be distinct primes. Find number of generators of $(\mathbb{Z}/pq\mathbb Z, +)$

May I verify if my proof to the a/m claim is correct? Thank you.

#generators $=\phi(pq)$. Let $A = \{x\in \mathbb{N}： q\mid x \wedge x< pq\}$ and $B = \{y\in \mathbb{N}： p\mid y \wedge y< pq\}$. Then $\left| A \right| = p-1, \left| B \right| =q-1$ and $A \cup B \subseteq G.$ Suppose $A \cap B \neq \emptyset.$ Let $z \in A \cap B.$ Then, $z \geq pq.$ (Contradiction). Hence, $\phi(pq) = pq-1 - (p-1) -(q-1)$.

-
Hm technically you never counted $0$ or $pq$ (they are they same, but whatever) in your technique, so there is probably a problem there. Or maybe that is the $(pq-1)$ term at the end? Does the $-1$ stand for $0$? – Patrick Da Silva Oct 18 '13 at 15:58

It all boils down to showing that $\varphi(pq)=\varphi(p)\varphi(q)=(p-1)(q-1)$. We can do this for arbitrary coprime $a,b$. We do so by contraposition.
Suppose that $(a,b)=1$. We show that $(a,y)=(x,b)=1$ if and only if $(ax+by,ab)=1$. Indeed, suppose that there is a prime $p\mid (ax+by,ab)$. Then $p\mid ab$, so $p\mid a$ or $p\mid b$. We can assume $p\mid a$. Thus $p\not\mid b$, since $(a,b)=1$. It follows that $p\mid ax+by$ and $p\mid a$ so $p \mid by$, so $p\mid y$ since $p\not\mid b$. Thus $p\mid (a,y)$. In the case $p\mid b$ and $p\not\mid a$ we'd get $p\mid (x,b)$. In any case $(ax+by,ab)>1\implies (a,y)$ or $(b,x)>1$.
Now suppose $p\mid (a,y)$. Then $p\mid ax+by$, and $p\mid ab$, so $p\mid(ax+by,ab)$. Similarily, if $p\mid (b,x)$, $p\mid(ax+by,ab)$. Here we do not need the assumption that $(a,b)=1$.
Conclusion As $x,y$ range over the set of generators of $\Bbb Z/(b)$ and $\Bbb Z(a)$, $ax+by$ ranges over the set of generators of $\Bbb Z/(ab)$. Thus, whenever $(a,b)=1$ $$\varphi(ab)=\varphi(a)\varphi(b)$$