To find a factor of an odd number $n$, given a method for computing the order $r$ of $x$, choose a random $x \pmod n$, find its order, and compute $\text{gcd}(x^{\frac{r}{2}}-1,n)$. Here $\text{gcd}(a,b)$ is the greatest common divisor of $a$ and $b$, i.e., the largest integer that divides both $a$ and $b$. The Euclidean algorithm [Knuth 1981] can be used to compute $\text{gcd}(a,b)$ in polynomial time. Since $$(x^{\frac{r}{2}}+1)(x^{\frac{r}{2}}-1) \equiv 0 \pmod n,$$ then $\text{gcd}(x^{\frac{r}{2}}-1, n)$ fails to be a non-trivial divisor of $n$ only if $r$ is odd or if $x^{\frac{r}{2}} \equiv -1 \pmod n$. Using this criterion, it can be shown that this procedure, when applied to a random $x \pmod n$, yeilds a factor of $n$ with probability $1-2^{k-1}$, where $k$ is the number of distinct odd prime factors of $n$. A brief sketch of the proof of this result follows. Suppose that $n = \prod_{i=1}^{k} p_i^{a_i}$. Let $r_i$ be the order of $x \pmod {p_i^{a_i}}$. Then $r$ is the least common multiple of all $r_i$. Consider the largest power of $2$ dividing each $r_i$. The algorithm only fails if all these powers of $2$ agree: if they are all $1$, then $r$ is $1$, then $r$ is odd and $\frac{r}{2}$ does not exist; if they are all equal and larger than $1$, then $x^{\frac{r}{2}} \equiv -1 \pmod n$ since $x^{\frac{r}{2}} \equiv -1 \pmod {p_i^{a_i}}$ for every $i$.
I know that in factoring algorithms the general idea is that if we can obtain $b^2\equiv c^2 \pmod n$ and $b\not\equiv \pm c\pmod n$, then $\gcd(b+c,n)$ will be a non-trivial factor of $n$. So far so good.
But then it is not clear to me why $x^{\frac{r}{2}} \equiv -1 \pmod {p_i^{a_i}}$ for every $i$, in this context. It doesn't seem to logically follow from "all these powers of $2$ (i.e. the highest powers of $2$ that divide each $r_i$) agree" and "if they are all equal and larger than $1$".
I'm probably missing something. Could someone clarify?
