1
$\begingroup$

This question already has an answer here:

I'm really stuck on the following question. I understand logically why this makes sense, and I've read a few proofs on this site of the multiplicative property of Euler's Totient, but those all seem beyond the scope of my class. Is there a simple proof to address the following question?

Suppose a number m is the product of two distinct primes, p and q. prove that the Euler totient of m is equal to (p-1)(q-1). For instance, the Euler totient of 35 (which is 5 * 7) is equal to 4*6, or 24. But remember that when you prove a theory you need to write it in terms of variables rather than numbers. (hint: you might want to check additive or multiplicative properties of totient function)

$\endgroup$

marked as duplicate by Dietrich Burde, Semiclassical, user147263, Daniel W. Farlow, John B Mar 7 '16 at 0:16

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

2
$\begingroup$

In the case when $m=pq$ with $p,q$ distinct primes, it might be easiest to use the inclusion-exclusion principle. There are $pq$ integers from 1 to $pq$, with $q$ of them being multiples of $p$, $p$ of them multiples of $q$, and one being a multiple of both $p$ and $q$. Therefore $$ \phi(pq)=pq-q-p+1=(p-1)(q-1)$$

$\endgroup$
1
$\begingroup$

Consider the meaning of $\phi$

$\phi(n)$ means the number of set $\{x\ |\ (x,n)=1, 1 \le x \lt n\}$.

Then consider $\phi(pq)$, only $\{p,2*p,3*p,...,(q-1)*p,q,2*q,...,(p-1)*q\}$ is factor of $pq$, total p-1+q-1.

So $\phi(pq)=pq-1-(p-1+q-1)=(p-1)(q-1)$

$\endgroup$

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