Classical reduction: $N \nmid a^{r/2} - 1$ when the order $r$ is even

Let $1 < a < N$ with $\gcd(a, N) = 1$ and let $r = \operatorname{ord}_N(a)$. If $r$ is even, then

Otherwise $a^{r/2} \equiv 1 \pmod N$, contradicting the minimality of the order $r$. Together with the previous milestone this shows that the only way the reduction can fail for even $r$ is $N \mid a^{r/2}+1$.

Formalization Note Natural-number subtraction is harmless here because $a^{r/2} \ge 1$.