<s>[INST] 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?
 [/INST] 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$.
</s>