# How does $x^{\frac{r}{2}} \equiv -1 \pmod {p_i^{a_i}}$ follow from “if all these powers of $2$ agree”?

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?

If $$r$$ is the least common multiple of the $$r_i$$, then for each $$r_i$$ there is an integer $$s_i$$ such that $$r=r_is_i$$. If at least one of the $$r_i$$ is even, then so is $$r$$, which we need.
Moreover, if all the $$r_i$$ agree on the powers of 2 dividing the $$r_i$$, then $$r$$ contains the same number of powers of 2, and $$s_i$$ must be odd. Hence, for each $$i$$, $$x^{r/2}\text{ mod }p_i^{a_i}=(x^{r_i/2})^{s_i}\text{ mod }p_i^{a_i}$$ Now, we know that $$x^{r_i}-1=(x^{r_i/2}+1)(x^{r_i/2}-1)\equiv 0\text{ mod }p_i^{a_i}$$ but $$x^{r_i/2}-1$$ is not 0 modulo $$p_i^{a_i}$$ because otherwise the order would be $$r_i/2$$, not $$r_i$$. So, $$x^{r/2}\text{ mod }p_i^{a_i}=(-1)^{s_i}\text{ mod }p_i^{a_i}=(-1)\text{ mod }p_i^{a_i}.$$