A number theory problem in RSA Let say we have $N=pq$ (Both $p$ and $q$ are safe primes, meaning $\gcd(p-1,q-1)=2$)

let's assume $e$ is an odd number which can be efficiently factored and assume that we know the $e$'th root of 1 modulo $N$ - call it $r$ - as well es $e$ and its prime-factorization. There is a claim that knowing the $e$'th root of 1 modulo $N$ we can find such $y&gt;1$ and an odd prime $p_0$ such that $y^{p_0} = 1 \bmod N$.

How can we calculate $y$ and $p_0$?
If we know $e$, then it's easy.

If don't have to know the factors, but it does make it easier - as fgrieu pointed out, either $(p-1)/2$ or $(q-1)/2$ will appear as one of the prime factors, that will allow us to immediately recover $p, q$

Once we have that, then we know that we want:

$$y^{p_0} \equiv 1 \pmod p$$
$$y^{p_0} \equiv 1 \pmod q$$

If we have $y \equiv 4 \pmod p$ (or any other quadratic residue) and $p_0 = (p-1)/2$ (which is prime), then we satisfy the first equation.

If we have $y \equiv 1 \pmod q$, then we satisfy the second equation.

It's easy to find a $y$ that meets both modulii (as $p, q$ are relatively prime) using the Chinese Remainder Theorem, and so that's our answer.