# Euler's Totient function for semiprime numbers

I have noticed, during the period I spent studying RSA, that Euler's Totient function can be calculated in another way than $ϕ(N) =(p-1).(q-1)$

Let me explain myself by pointing to a brief example:

$p = 131$

$q = 11953$

$N= p*q = 1565843$

The totient defines the quantity of positive integers less or equal than $N$ coprime with $N$. So we calculate it:

$ϕ(N) = (p-1)(q-1) = 1553760$

But I have realized that this way can also be obtained:

How many multiples of p are under N? q multiples of p

How many multiples of q are under N? p multiples of q

These previous statements show the quantity of integers NOT coprime with $N$ that are less or equal to $N$. It's just the opposite of the Euler's Totient.

So the equation is the following:

$ϕ(N) = N - p - q + 1$

In the example:

$ϕ(N) = 1565843 - 131 - 11953 + 1$

$ϕ(N) = 1553760$

I suppose that this method is well documented over there. I just want to know if this is a good praxis for using in an implementation (for example).

• Yes, that trivially follows from the definition. Are you asking whether it's "better" to compute the totient as $N - p - q + 1$ instead of $(p - 1)(q - 1)$? They are always equal, of course, since $(p - 1)(q - 1) = pq - p - q + (-1)(-1) = N - p - q + 1$. Jun 2 '15 at 0:24

You can get the 2nd equation from the first with some simple algebra.

$$(p-1)(q-1)$$ $$pq-p-q+1$$ $$n-p-q+1$$

I'm not really sure what you are asking though. Are you asking if computing the second is faster than the first?

I suppose you could argue that you have to do the $pq$ multiplication anyways, so why not reuse it. If that is your argument, then doing the calculation with the 2nd equation you gave for $\varphi$, then you get the multiplication for free and only have to do 2 subtractions and an addition. Using the first equation, you have to do two subtractions (although only a minus 1) and one multiplication. Multiplication is much more expensive, so the 2nd equation would be more efficient.

• So it comes from the 1st equation. Well I just thought it and put on paper, didn't notice. Jun 2 '15 at 0:31
• Yes, I'm asking if this way the computation cost is lower with this way. Could you give me an explanation? Jun 2 '15 at 0:32
• @kub0x see the updates. Jun 2 '15 at 1:22
• So the 2nd way is more efficient. Thank you cleared my doubt. Jun 2 '15 at 1:31
• @kub0x, yes, I think you could make that argument. Jun 2 '15 at 1:35