Miller-Rabin: Showing non trivial divisors of $n$

The general statement is that whenever we have a nontrivial square root of $1$ modulo $n$, a value $c$ such that $$ c^2 \equiv 1 \pmod{n}, \qquad c \not\equiv \pm1 \pmod{n}, $$ then we obtain a factorization of $n$.

If $c^2 \equiv 1 \pmod n$, then $(c+1)(c-1) \equiv 0 \pmod n$.

If $c+1$ were relatively prime to $n$, then it would have an inverse modulo $n$, and we could multiply by $(c+1)^{-1}$ to conclude that $c-1 \equiv 0 \pmod n$. But this is ruled out by our assumption that $c \not\equiv 1 \pmod n$.

If $c+1$ were divisible by $n$, then we would have $c+1 \equiv 0 \pmod n$. But this is ruled out by our assumption that $c \not\equiv -1 \pmod n$.

So the only remaining possibility is that $c+1$ shares some, but not all, prime factors with $n$: that $\gcd(c+1,n)$ is a nontrivial factor of $n$.

The same goes for the other factor $c-1$.

---

More generally, whenever we find $a$ and $b$ such that $a^2 \equiv b^2 \pmod n$ but $a \not\equiv \pm b \pmod n$, the same argument shows that $\gcd(a+b,n)$ and $\gcd(a-b,n)$ are nontrivial factors of $n$. This is the basis for many integer factorization algorithms starting from Fermat's factorization method and ending with the quadratic sieve.

From $b^{\frac{n-1}{2^r}}\equiv 1\pmod n$, we see that there exists an integer $m$ such that $$b^{\frac{n-1}{2^r}}=mn+1\tag1$$ From $b^{\frac{n-1}{2^{r+1}}}\not\equiv \pm 1\pmod n$, we see that there exist integers $k,r$ such that $$b^{\frac{n-1}{2^{r+1}}}=kn+r+1\tag2$$ where $$\text{$1\le r\le n-1\quad$ with $\quad r\not=n-2$}\tag3$$

Since $\frac{n-1}{2^r}$ is even, we get, from $(1)(2)$, $$mn+1=b^{\frac{n-1}{2^r}}=b^{\frac{n-1}{2^{r+1}}\times 2}=\left(b^{\frac{n-1}{2^{r+1}}}\right)^2=(kn+r+1)^2=(k^2n+2kr+2k)n+(r+1)^2$$ implying $$1\equiv (r+1)^2\equiv r^2+2r+1\pmod n$$ which implies $$r(r+2)\equiv 0\pmod n\tag4$$

Here, supposing that $r+2=n+1$ implies $r\equiv 0\pmod n$ which is impossible.

So, from $(3)$, we have $1\lt r\lt n$ and $1\lt r+2\lt n$.

It follows from these and $(4)$ that both $r$ and $r+2$ are non-trivial divisors of $n$.

We have $b^{\frac{n-1}{2^{r+1}}}+1=kn+r+2$. Since $r+2$ is a non-trivial divisor of $n$, we see that $\gcd\left(b^{\frac{n-1}{2^{r+1}}} +1,n\right)$ is a non-trivial divisor of $n$.

We have $b^{\frac{n-1}{2^{r+1}}}-1=kn+r$. Since $r$ is a non-trivial divisor of $n$, we see that $\gcd\left(b^{\frac{n-1}{2^{r+1}}} -1,n\right)$ is a non-trivial divisor of $n$.