I'm working on a series of number theory proofs and I'm stumped on this one. The idea is to extend each result for the subsequent proof. I just succeeded in proving the following:
Suppose $n > 1$. The number $n$ is prime if and only if there exists a number $b$ such that gcd$(b, n) = 1$ and $b^{n−1} ≡ 1$ (mod $n$) and $b^{(n−1)/d} \not ≡ 1$ (mod $n$) for all positive divisors $d$ of $n − 1$ with $d > 1$.
My proof for this theorem is straightforward: we know that if $n$ is not prime, then for any $b$ we have $exp_n(b) < n-1$ since $exp_n(b)$ must divide $\phi(n) < n-1$. However, if $n$ is prime, we know $\phi(n) = n-1$ and that $n$ must have a primitive root. Therefore if we call $b$ that primitive root, we know that $exp_n(b) = \phi(n) = n-1$.
The proof I'm currently stuck on is as follows:
Suppose $n > 2$. Prove that $n$ is prime iff there exists a number $b$ such that:
- gcd($b, n$) $= 1$
- $b^{(n−1)/2} \equiv −1$ (mod $n$)
- $b^{(n−1)/q} \not \equiv 1 $(mod $n$) for all odd prime divisors $q$ of $n − 1$.
I know that this is related to the Pocklington criterion, and I see that $b^{(n−1)/2} \equiv −1$ (mod $n$) is equivalent to $b^{n−1} \equiv 1$ (mod $n$). So I'm stuck on (3); I'm not sure I see how the previous result applies when only considering odd prime divisors. Can anyone offer some guidance?