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)ā‰ (pāˆ’1)2\phi(N) \neq (p-1)^2 due to the full definition of Euler's totient function:

Ļ•(n)=nāˆpāˆ£n(1āˆ’1p)\phi(n) = n \prod_{p|n} (1-\frac{1}{p})

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

Ļ•(n)=n(1āˆ’1p)=nāˆ’p\phi(n) = n(1-\frac{1}{p}) = n - p

Last updated