I'm trying to prove the following statement:
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$.
Here's what I have so far:
If $n$ is composite, by definition it has at least one positive divisor $d$ other than itself and 1. Since $\phi(n)$ counts the number of values $1 \ge x \ge n$ such that gcd$(x,n) = 1$ and we know that gcd$(d,n) \not = 1$ and gcd$(n,n) \not = 1$, $\phi(n)$ can be at most $n-2$. Thus, if $n$ is composite, $\phi(n) < n-1$. By the contrapositive, if $\phi(n) = n - 1$, $n$ is prime.
(We can say $=$ instead of $\ge$ because $\phi(n) \not = n$ for $n>1$.)
This result seems helpful but I can't connect the dots yet. The problem states that $exp_n(b) = n-1$, and I know that if $n$ is prime $\phi(n) = n-1$, making $b$ a primitive root. But this doesn't give me the proof I need yet. Can I get a hint in the right direction?