In the Miller–Rabin primality condition why do we know the odd power case is congruent to 1?

Question

A prime number n satisfies

$a^{d} \equiv 1\pmod{n}$

or

$a^{2^r\cdot d} \equiv -1\pmod{n}$

where $n - 1 = 2^s·d$, d is odd and $r = 0, 1, ..., s-1$

Why does the second condition being false imply the first is congruent to 1 but not -1?

Answer 1

The precise formulation is this: for any number $a$ not divisible by a prime number $n=2^sd+1$,

• either $a^d\equiv 1\mod n$
• or there exists $r\in \{0,\dots,s-1\}$ such that $a^{2^rd}\equiv -1\mod n$.

This is because of Little Fermat: $a^{2^sd}\equiv 1\mod n$. Then $a^{2^{s-1}d}\equiv \pm1\mod n$ since $\mathbf Z/n\mathbf Z$ is a field. If it is not congruent to $-1$, then $a^{2^{s-2}d}\equiv \pm1\mod n$, &c. If none of $a^{2^{s-k}d}$ is congruent to $-1\mod n$ for $k=1,\dots,s$, it means $a^d\equiv 1$.