For $p,q\in\mathbb N^*$, if $\phi(p\,q)=(p-1)(q-1)$, then $p$ and $q$ are distinct primes

124 Views Asked by At

If $p$ and $q$ are distinct primes, then the Euler totient of their product $\phi(p\,q)$ is $(p-1)(q-1)$. What's a simple proof of the converse (restricted to strictly positive integers $p$ an $q$) ?

Full proposition: $$\forall(p,q)\in(\mathbb N^\star)^2,\ \phi(p\,q)=(p-1)(q-1)\implies p\in\mathbb P∧q\in\mathbb P∧p\ne q$$


My original proposition was: $p_i\in\mathbb N^*, \phi(\prod p_i)=\prod(p_i-1)$ implies the $p_i$ are distinct primes. It was disproved by the counterexample $\phi(4\times3\times3)=3\times2\times2$. The original motivation is this answer in a crypto context. The proof I could make by contraposition considering the explicit factorization of $p$ and $q$ is rather laborious.

1

There are 1 best solutions below

2
On BEST ANSWER

If $p$, $q$ have a prime factor $k$ in common, then $k^2$ is a factor of $pq$, so $k$ is a factor of $\phi(pq)$. But $k$ cannot be a factor of $p-1$ or $q-1$. So, if $\phi(pq)=(p-1)(q-1)$, this is not possible and so $p$, $q$ are relatively prime and hence $\phi(pq) = \phi(p)\phi(q)$, but then $\phi(p)$ is at most $p-1$ and $\phi(q)$ at most $q-1$, so they must have these values, and $p$, $q$ are prime.