Invertible elements of $\mathbb Z/pq\mathbb Z$ Let $p,q$ two distinct primes. What are the invertible elements of $\mathbb{Z}/pq\mathbb{Z}$? I couldn't figure it out. I've got also a question about the notation, what is the logic behind $\mathbb{Z}/pq\mathbb{Z}$? I would think $\mathbb{Z}/pq$ would be much easier and logical?
 A: In general, for $\mathbb Z/m\mathbb Z$, the invertible elements are the ones that are coprime to $m$. This is a consequence of Bézout's theorem: if $x \perp m$ (I like to use $\perp$ to denote coprimality), then some $k,\ell$ exist such that $kx + \ell m = 1$ and in particular, $kx \equiv 1 \pmod m$.
For $m = pq$ the elements that are not coprime to $pq$ are the ones that are divisible by $p$ or $q$, these are $p, 2p, ..., qp = 0$ and $q,2q, ... , pq = 0$.
By the way, we see that there are $$1 + (q-1) + (p-1) = p+q-1$$ elements that  are not invertible, thus the number of invertible elements is $$pq  -p-q+1 = (p-1)(q-1),$$ consequent with $\phi(pq) = \phi(p)\phi(q) = (p-1)(q-1)$.
The notation comes from ring theory: $\mathbb Z/m\mathbb Z$ is the ring that arises by "dividing" or "modding out" the ideal $m\mathbb Z = \{0,\pm m, \pm 2m, \dots\}$ in the ring $\mathbb Z$. Informally this means we consider the same ring $\mathbb Z$, but set all elements of the ideal we mod out, these are all multiples of $m$ equal to zero. Wikipedia gives a precise definition.
A: As recalled in Myself's answer, one knows that Bezout's Identity implies that the invertible elements in $\Bbb Z/n\Bbb Z$ are the classes $\bar k\bmod n$ such that ${\rm GCD}(k,n)=1$, whatever $n$.
Another possible approach to your question is to work out the following two exercises:
Exercise 1: There is a ring isomorphism $\Bbb Z/pq\Bbb Z\simeq\Bbb Z/p\Bbb Z\times\Bbb Z/q\Bbb Z$.
Exercise 2: If $A$ and $B$ are two rings, then $(A\times B)^\times=A^\times\times B^\times$.
(if $R$ is a ring, the symbol $R^\times$ denotes the multiplicative group of invertible elements in $R$)
