Miller-Rabin: Showing non trivial divisors of $n$ 
Let's assume $n$ doesn't pass the Miller-Rabin test and $b$ is a witness. Meaning, $b^{\frac{n-1}{2^r}} \equiv 1 \pmod{n}$ where $\frac{n-1}{2^r}$ is even, but $c = b^{\frac{n-1}{2^{r+1}}} \not\equiv \pm1 \pmod{n}$. Show that $\gcd(c+1,n),\gcd(c-1, n)$ are non-trivial divisors of $n$.

So first of all, for my convenience:


*

*Denote $n-1 = 2^ls$, $s$ is odd.

*Denote $k=l-r$.


*

*$c = b^{2^{k-1}s}$

*$c^2 = b^{2^{k}s}$

*$2^ks$ is even



It is given that $c^2 \equiv 1 \pmod{n} \implies (c-1)(c+1) \equiv 0 \pmod {n} \implies n\mid (c-1)(c+1)$
Now, I think we can assume that $n$ passed Fermat's theorem test (that's part of the initial tests of the Miller-Rabin algorithm).
Hence,
$$c^{r+1} = b^{2^l s} = b^{n-1} \equiv 1 \pmod {n}$$
but that isn't revealing anything new other than $r$ is odd  (since $2$ must divide $r+1$).
What am I missing?

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.
