= Solution
Since $r$ is even,
$$
(a^{r/2}-1)(a^{r/2}+1)=a^r-1\equiv0\pmod N.
$$
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$. Therefore
$$
1<\gcd(a^{r/2}-1,N)<N,
$$
and 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\pm1$ modulo the prime-power divisors of $N$.
Back to article page
