Past exam of the mathematics course of the University of Cambridge / 2025 / ii / Paper 2 / 15C / c / Solution

Since $r$ is even,The first factor is not divisible by $N$, since that would contradict minimality of $r$, and the second is not divisible by $N$ by hypothesis. Nevertheless their product is divisible by $N$. Thereforeand Euclid's algorithm computes a nontrivial factor. One can also compute $\gcd (a^{r/2}+1,N)$; together the two gcds expose factors lying on opposite sides of the congruence $a^{r/2}\equiv \pm 1$ modulo the prime-power divisors of $N$.