Certificate of primality based on the order of a primitive root Reading my textbook, it tells me that to prove $n$ is prime, all that is necessary is to find one of its primitive roots and verify that the order of one of these primitive roots is $n-1$.
Now, why exactly does this work? It's not making much sense to me.  Also, will any primitive root work?   

Yes, any primitive root will work.
Effectively what we have established, by raising the primitive root $m$ to the power $(n-1)$  and that being the lowest power for which we encounter $1 \pmod n$, is that there are $(n-1)$ distinct numbers less than $n$ that don't divide $n$.  If there were some $k<n-1$ which had $\gcd(m^k, n) = c \ne 1$, we could never get rid of the factor of $c$ and so we would not reach $m^{n-1} \equiv 1 \bmod n$.
To find a primitive root is perhaps more of a challenge. For a number $n$ that we don't know is prime, we need to check that our candidate root $m$ fulfills $m^{n-1} \equiv 1 \bmod n$ (failure on this count would immediately mean that $n$ is not prime) and then check that it also fulfills $m^{k} \not\equiv 1 \bmod n$ for each $k = \frac{n-1}{p_i}$ where $p_i$ are the distinct prime factors of $(n-1)$.
