Why Eulers' totient doesn't seem to work in following situation?

55 Views Asked by At

I have a question about Eulers' totient function related to RSA

(1) $N=PQ$

(2) $\varphi(N)=\varphi(P)\varphi(Q)=(P-1)(Q-1)$

Now, say $P = 3$ and $Q = 3$

From (1) it follows that $N=PQ=3\cdot3=9$

From (2) it follows that $\varphi(9)=\varphi(3)\varphi(3)=(3-1)(3-1)=2\cdot2=4$

But, actually $6$ numbers are coprime with $9$, being $1,2,4,5,7,8$, so actually $\varphi(9)=6$.

What am I missing here?

1

There are 1 best solutions below

0
On BEST ANSWER

The relation $\varphi(pq)=\varphi(p)\varphi(q)$ is only true if $\gcd(p,q)=1$. But here $\gcd(p,q)=\gcd(3,3)=3$.

Hence the two primes that multiply to $N$ in the RSA cryptosystem must be distinct.