P=Q

If p=qp = q then N=pq=p2N = pq = p^2 and you can use function such as isqrt in Python to retrieve pp.

Note that in the situation N=p2N=p^2, ϕ(N)(p1)2\phi(N) \neq (p-1)^2 due to the full definition of Euler's totient function:

ϕ(n)=npn(11p)\phi(n) = n \prod_{p|n} (1-\frac{1}{p})

The key here is that pnp \mid n are distinct prime factors, so we would only use pp once in the equation:

ϕ(n)=n(11p)=np\phi(n) = n(1-\frac{1}{p}) = n - p

Last updated

Was this helpful?