# Proof Checking and input: Generators of $\mathbb{Z}_{pq}$

I'm self-studying abstract algebra (slowly but surely), and I have a question about my answer to the following prompt:

Problem statement:

Show that there are $(q-1)(p-1)$ generators of the group $\mathbb{Z}_{pq}$, where $p$ and $q$ are distinct primes. (Where $\mathbb{Z}_{n}$ is the additive group of integers modulo $n$)

I can use a theorem from my textbook that says:

The integer $r$ generates the group $\mathbb{Z}_n$ iff $$1\le r\lt n \quad\text{and}\quad \gcd(r, n) = 1$$

My attempt at a proof:

Let $p$ and $q$ be distinct primes and $\mathbb{Z}_{pq}$ be the additive group of integers modulo $pq$.
An element $a \in \mathbb{Z}_{pq}$ is a generator of $\mathbb{Z}_{pq}$ iff: $$1\le a\lt pq \quad\text{and}\quad \gcd(a, pq) = 1$$ There are $p-1$ positive multiples of $q$ less than $pq$. Also, there are $q-1$ positive multiples of $p$ less than $pq$. These are the only elements of $\mathbb{Z}_{pq}$ that are not coprime to $pq$. Finally, $0$ is not a generator of $\mathbb{Z}_{pq}$.

There are $pq$ elements in $\mathbb{Z}_{pq}$, so the number of generators is: \begin{align} pq - (p-1) - (q-1) - 1 &= pq -p -q + 1 \\ &= p(q-1) - (q - 1) \\ &= (q-1)(p-1) \end{align}

My questions:

• Obviously, if there's a flaw in the proof, I'd like to know. :) Aside from that...

• When I assert "these are the only elements of $\mathbb{Z}_{pq}$ that are not coprime to $pq$," do I need to further show that this is true? It is patently obvious to me, but I know that just claiming "this is obvious" is not a valid method of proof.

• I'd like to have some input on the style/format of my proof. Is there a better (read: more formal/traditional) way to phrase something in this proof, or is there a format that I'm not following? As I'm self-teaching, I don't want to learn bad habits...

-
On your second point, the general rule that I like to follow is: If you need to ask whether something has to be justified then it doesn't hurt to actually justify it. People find different things to be obvious and what's obvious to you may not be obvious to me. – EuYu Sep 20 '13 at 1:22

I don't see anything wrong with your proof.

For your second question, you could expand a bit on that statement, perhaps saying something like "since $1$,$p$, $q$ and $pq$ are the only divisors $pq$, any integer $n$not divisible by $p$ or $a$ must have $\gcd(n,pq)=1$, and be coprime to $pq$", but in situations like this, where a moment's though and writing down a few definitions will give a proof, omitting it is usually safe.

In writing proofs, I have found the following idea helpful: a proof is really intended to convince someone (a reader, a teacher, yourself) that a theorem is true. If, after reading your proof and spending a little time thinking about each step, this person could still doubt that your theorem is true, then you should add more. Otherwise, your safe. This reasoning, however, is very audience-dependant. For some audiences, the following would be an acceptable proof of your theorem:

The generators of $\Bbb{Z}_{pq}$ correspond with integers less than and coprime to $pq$. Since these are counted by Euler's $\phi(n)$, $\phi(n)$ is multiplicative, and, for any prime $p$, $\phi(p) = p-1$, the number of generators of $\Bbb{Z}_{pq}$ is $\phi(pq)=\phi(p)\phi(q) = (p-1)(q-1)$.

For lots of other audiences, it would not be.

Remember, a proof doesn't always have to be written down, finalized, and perfect. It can be more of a conversation.

-