Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

I was trying to understand RSA when I encountered the Euler Function. I do understand this: $\phi(P)$, where $P$ is a prime is $P-1$.

However it seems that for a number $N$ such at $N=P\cdot Q$ where $P$ and $Q$ are non-equal primes:

\begin{equation} \phi(P\cdot Q) = (P-1)\cdot(Q-1) \end{equation}

I'm having trouble understanding why that is so. Could someone point me toward the proof of the same?

share|improve this question

2 Answers 2

up vote 5 down vote accepted

This is actually a special case of a more general property of the Euler totient function: it is a multiplicative function, meaning that, for any two coprime numbers $p$ and $q$, $\phi(pq) = \phi(p)\phi(q)$.

The special case where $p$ and $q$ are (distinct) primes is easy to prove. By definition, $\phi(n)$ gives the number of positive integers coprime to and smaller than $n$, i.e. the number of integers $k$ satisfying $0 < k < n$ and $\gcd(k,n) = 1$.

Since $p$ and $q$ are the prime factors of $pq$, an integer $k$ is coprime to $pq$ if and only if it isn't a multiple of either $p$ or $q$. In the range $0 < k < pq$ there are $p-1$ distinct multiples of $q$, and $q-1$ distinct multiples of $p$, and a bit of thought shows that these two sets cannot overlap, as any positive number that was a multiple of both $p$ and $q$ would have to be at least as large as $pq$.

Thus, out of the total $pq-1$ integers $k$ in the range $0 < k < pq$, all but $(p-1) + (q-1)$ are coprime to $pq$, and so $$\begin{aligned}\phi(pq) &= (pq-1) - (p-1) - (q-1) \\ &= pq - p - q + 1 \\ &= (p-1)(q-1).\end{aligned}$$

share|improve this answer

A very simple explanation is that a prime number is co-prime with every number below it:

$$ϕ(P) = (P−1)$$

Because Euler Totient Function is multiplicative function, this means that:

$$ϕ(pq)=ϕ(p)ϕ(q)$$

Which can be written as:

$$ϕ(n) = (p-1)(q-1)$$

I hope this helps. Otherwise, just look at Ilmari Karonens answer.

share|improve this answer
2  
Simple equations like yours are pretty easy to format; I just added $$ around what you'd written to trigger display math mode. For more advanced tricks, see this page. –  Ilmari Karonen Dec 16 '12 at 11:46

Your Answer

 
discard

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.