# Miller’s test for the base $b$

Definition: Let $$n$$ be an integer with $$n > 2$$ and $$n − 1 = 2^st$$, where $$s$$ is a non-negative integer and $$t$$ is an odd positive integer. We say that $$n$$ passes Miller’s test for the base $$b$$ if either $$b^t ≡ 1 \ ( mod \ n)$$ or $$b^{2^jt} ≡ −1 \ (mod \ n)$$ for some $$j$$ with $$0 ≤ j ≤ s − 1$$.

I'm a bit confused with this. I thought the test was based on the fact if $$x^2 - 1 \equiv 0 \ (mod \ p)$$, then $$x \equiv 1$$ or $$x \equiv -1$$. If at any point we get $$b^{2^jt} \not ≡ −1$$ or $$1$$, shouldn't the test fail there? The test seems to say, you will constantly divide the exponent by 2 until you are left with just the odd integer $$t$$. If you at any point encounter a congruence to $$-1 \ (mod \ n)$$ before the $$b^t$$ case, you pass the test. If left with $$b^t$$ test and you get not congruent to $$1$$, you fail. What is the significance too, of $$b^t$$ being congruent to $$1$$ and not $$-1$$?

I apologize if the information is easily searchable. When I tried looking this up, I mainly found the Miller-Rabin test, which I think is a bit different from this. Thanks!

• The Miller-Rabin test is just Miller's test with $b$ chosen at random. – Misha Lavrov Dec 8 '18 at 6:28
• Oh... I'll take a look at it then, thank you very much. – Stawbewwy Dec 8 '18 at 6:29

The sequence $$b^t \bmod n, b^{2t} \bmod n, b^{4t}\bmod n, \dots, b^{2^s t}\bmod n$$ should fail the test if, at any point in the sequence, we find a number that's not $$-1$$ (or $$n-1$$ if you prefer), followed by $$1$$. This gives us an $$x \not\equiv \pm 1\pmod n$$ whose square is $$x^2 \equiv 1 \pmod n$$, ultimately leading to a nontrivial factor of $$n$$. It should also fail if we don't get $$1$$ at the end; in that case, $$n$$ is not prime by the converse of Fermat's little theorem.
• the sequence is entirely $$1,1,1,\dots,1,1$$, or
• it ends with $$\dots, -1, 1, \dots, 1,1$$.
The first case is the one where $$b^t \equiv 1 \pmod n$$. In the second case, even if the sequence has elements other than $$\pm 1$$, that's fine, as long as they're before the $$-1$$. Seeing such elements doesn't tell us that $$n$$ is composite, because even for prime $$n$$, we don't really know what square roots of $$-1$$ look like.
• I get it now I think. If what I looked up is correct, the only solutions to $x^2 \equiv 1 \ (mod \ p)$ are $1,-1$, so, it's possible to get $-1$ through other squares, but not $1$. Thank you very much for the post, it helped make things very clear for me :) – Stawbewwy Dec 8 '18 at 7:46