Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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)$.

share|cite|improve this question
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)$$

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.