§5, p. 1498 — the reduction fails only if the 2-parts of all the local orders r_i agree

Let $n > 1$ be odd with prime factorization $n = \prod_{i=1}^k p_i^{\alpha_i}$, let $x$ be a unit modulo $n$ and let $r_i$ be the order of $x \bmod p_i^{\alpha_i}$. Write $\nu_2(m)$ for the exponent of the largest power of $2$ dividing $m$. If the procedure does not yield a nontrivial factor of $n$ at $x$ — that is, $r$ is odd or $\gcd(x^{r/2}-1, n) \in \{1, n\}$ — then

Contrapositively, whenever two of the local orders have different 2-adic valuations, $x$ is a good choice. Combined with the estimate that the valuations all agree for at most a $1/2^{k-1}$ fraction of units, this gives the mission's goal.

Formalization Note Only the direction "failure implies agreement" is stated, which is the direction the page's "The algorithm only fails if all of these powers of 2 agree" asserts and the goal needs; the converse (also true for odd $n$) is the page's description of the two agreeing cases and is not part of this statement. Oddness of $n$ is needed: modulo a power of $2$, $-1$ and $1$ can coincide.