In Miller Rabin test, let n – 1 = 2xs, then,
if as mod n = 1 or as mod n = -1 then we say n is probably prime or if a2xs mod n = 1 then also we say n is probably prime but,
How can we say surely that n is composite if a2xs mod n = 1.
I read the proof here and understood the case where we say n is probably prime but I'm a little confused about the case where a2xs mod n = 1.
If anyone could explain that would be quite helpful.
Miller Rabin Proof
number theoryprime numbers
Related Solutions
The strong liars form a subgroup of $(\mathbb{Z}/n\mathbb{Z})^{\times}$ iff $n$ isn't of the form $n=\prod_{j=1}^{k}{p_{j}}^{\alpha_{j}}$, where $k\geq2$, $p_{1},\ldots,p_{j}$ are pairwise different primes such that $p_{j}\equiv 1\pmod4$ and $\alpha_{j}\in\mathbb{N}$, $j\in\{1,\ldots,k\}$. Here's the proof:
For $n=1$ everything's trivial so let's assume $n>1$ and set $n-1=2^{x}y$, where $x,y\in\mathbb{Z}$ and $2\nmid y$. Also let $L(n)$ denote the set of strong liars $\bmod n$, ie $$L(n)=\big\{a\in(\mathbb{Z}/n\mathbb{Z})^{\times}\colon(\exists t\in\mathbb{Z},0\leq t<x:a^{2^{t}y}=-1)\vee a^y=1\big\}.$$
If $2\mid n$, then $$L(n)=\big\{a\in(\mathbb{Z}/n\mathbb{Z})^{\times}\colon a^{n-1}=1\big\},$$ which is obviously a subgroup of $(\mathbb{Z}/n\mathbb{Z})^{\times}$.
If $q\mid n$ for some prime $q$ such that $q\equiv3\pmod4$, then $-1$ is quadratic nonresidue $\bmod{q}$, hence also $\bmod{n}$, so it can't be $a^{2^{t}y}=-1$ for $t>0$ and $$L(n)=\big\{a\in(\mathbb{Z}/n\mathbb{Z})^{\times}\colon a^y=\pm1\big\},$$ which is again a subgroup of $(\mathbb{Z}/n\mathbb{Z})^{\times}$.
If $n=p^\alpha$, where $p$ is a prime such that $p\equiv1\bmod4$ and $\alpha\in\mathbb{N}$ then we have $a^{n-1}-1=(a^{y}-1)\prod_{j=0}^{x-1}(a^{2^{j}y}+1)$, and since at most one of the factors on the RHS of this equation can be $0\bmod p$, we have $$L(n)=\big\{a\in(\mathbb{Z}/n\mathbb{Z})^{\times}\colon a^{n-1}=1\big\},$$ which is once again a subgroup of $(\mathbb{Z}/n\mathbb{Z})^{\times}$.
Now let $n=\prod_{j=1}^{k}{p_{j}}^{\alpha_{j}}$, where $k\geq2$, $p_{1},\ldots,p_{j}$ are pairwise different primes such that $p_{j}\equiv 1\pmod4$ and $\alpha_{j}\in\mathbb{N}$, $j\in\{1,\ldots,k\}$. Let $G_{j}=(\mathbb{Z}/{p_{j}}^{\alpha_{j}}\mathbb{Z})^{\times}$, $H_{j}={G_{j}}^y$ be the subgroup of $y$-th powers in $G_{j}$ and $K_{j}=\{a\in G_{j}\colon a^{y}=1\}$ be the $y$-torsion subgroup of $G_{j}$. Then $|G_{j}|=\varphi({p_{j}}^{\alpha_{j}})=(p_{j}-1){p_{j}}^{\alpha_{j}-1}$, $|K_{j}|=\gcd(\varphi({p_{j}}^{\alpha_{j}}),y)$ (because $G_{j}$ is cyclic) and $H_{j}\cong G_{j}/K_{j}$, from which it follows that $4\mid|H_{j}|$. $H_{j}$ is cyclic (it's a subgroup of $G_{j})$, so it contains an unique cyclic subgroup of order $4$. For every $j\in\{1,\ldots,k\}$ let's fix $r_{j}\in G_{j}$ such that ${r_{j}}^{y}$ has order $4$ (such elements exist by the above reasoning). By CRT we have $(\mathbb{Z}/n\mathbb{Z})^{\times}\cong\prod_{j=1}^{k}G_{j}$, let $f_{j}\colon(\mathbb{Z}/n\mathbb{Z})^{\times}\to G_{j}$ be the natural projection. Then there exist $a,b\in(\mathbb{Z}/n\mathbb{Z})^{\times}$ such that $f_{1}(a)=r_1$, $f_{1}(b)=-r_1$ and $f_{j}(a)=f_{j}(b)=r_j$ for $j\geq2$. Then for every $j$ it's $f_{j}(a^{2y})=f_{j}(b^{2y})=-1$, hence $a^{2y}=b^{2y}=-1$ and $a,b\in L(n)$ (because $x\geq2$). But $(ab)^{2y}=1$ so it can't be $(ab)^{2^{t}y}=-1$ for $t\geq1$, and also $f_{1}((ab)^{y})=-{r_{1}}^{2y}=1$, $f_{2}((ab)^{y})={r_{2}}^{2y}=-1$, so it's $(ab)^{y}\neq\pm1$, hence $ab\notin L(n)$, which means that $L(n)$ isn't a subgroup of $(\mathbb{Z}/n\mathbb{Z})^{\times}$ in this case.
Concerning the previous post: If $q\mid n$ for some prime $q$ such that $q\equiv 2\text{ or }3\pmod4$ then it's easy to see that there are no primitive Pythagorean triangles with hypotenuse $n$, and if $n=\prod_{j=1}^{k}{p_{j}}^{\alpha_{j}}$, where $p_{1},\ldots,p_{j}$ are pairwise different primes such that $p_{j}\equiv 1\pmod4$ and $\alpha_{j}\in\mathbb{N}$, then it's not difficult to show that there are $2^{k-1}$ different (up to isomorphism) primitive Pythagorean triangles with hypotenuse $n$, so the "bad" $n$'s are really exactly the ones for which there's more than one such triangle. :)
So you have $n-1$ in the form $2^{\alpha}\cdot d$ where $d$ is odd, then $n$ is composite if there exists any $a \leq n-2$ such that for all $\beta \in [0,\alpha-1]$ we have
$$a^{2^{\beta}\cdot d} \not\equiv 1, -1 (\text{mod } n)$$
The modular exponentiation comes in when we calculate the first test, $a^{2^{0}\cdot d}$. In your example you have to calculate $32^{85}$ modulo $341$.
What is nice is that after that for any $\rho$ we can get $a^{2^{\rho}\cdot d}$ by squaring the previous test value $a^{2^{\rho-1}\cdot d}$. In your case this doesn't really come into play as your $\alpha$ is only $2$, so we only need to test for $\beta = 0,1$. If you had a different $n$, then $\alpha$ might be a lot larger, and you'd end up doing a lot of modular arithmetic.
In your case though, you've found an $a$ which suggests that $n$ might be prime. However if $n$ is composite, then at most $\frac{1}{4}$ of the possible values for $a$ would give a result suggesting primality (a false positive). So based on this one test, you could declare $341$ is prime with only a $25\%$ chance you are wrong.
What you would do in practice is pick $k$ different values for $a$, then declare $n$ to be prime only if all of them pass the test (if any fails, then $n$ is definitely composite). Then you have only a $4^{-k}$ chance of being wrong.
Best Answer
If you start with $a^{s 2^N} \equiv 1 \bmod n, a^s \not \equiv 1 \bmod n$ then by repeated squaring, at some point you'll obtain $x = a^{2^ms}, x \not \equiv 1 \bmod n, x^2 \equiv 1 \bmod n$, if $n$ is prime this implies $x \equiv -1 \bmod n$
(because for $n=p$ prime the polynomial $x^2-1$ has only two roots in the field $\Bbb{Z/p Z}$)