Fermat's Theorem and primitive $n$th roots of unity Fermat's little theorem states that if $p$ is a prime number, then for any integer $a$ such that $p \not \mid a$ we have that $a^{p − 1} \equiv 1 \operatorname{mod} p$. 
Suppose $p =17$, then we know for any integer, $\alpha$ such that $\alpha <17$, we have $\alpha^{16} \equiv 1 \operatorname{mod} 17$. 
However, let's say I am trying to find the the $16$-th primitive roots $\operatorname{mod} 17$. That is all such $\alpha$ such that $16$ is the smallest integer to have this effect. How would I go about this? 
 A: It is known that $n$ admits a primitive root if and only if the group $(\mathbb Z/n\mathbb Z)^*$ is cyclic which is the case for all prime so for $17$. One can apply here the following known result:
Let $p_1, p_2,…p_r$ be the distinct prime divisors of $\phi(n)$ where $\phi$ is the Euler's totient function and $x$ coprime with $n$; then
$x$ is a primitive root modulo $n$ $\iff$ $x^{(\frac {\phi(n)}{p_i})} \not\equiv 1$  for all i=1,2,...,r
When $n=17$ one has $\phi(17)=16=2^4$ therefore $x$ is a primitive root modulo 17 if 
$x^8\not\equiv 1 mod(17)$. 
Calculation gives as possible values $x=3,5,6,7,10,11,12,14$
(for $x=1,2,4,8,9,13,15,16$ we have $x^8\equiv 1 mod(17)$)
ADDITIONAL NOTE.- It is in general difficult enough calculation of a p.r. modulo $n$ (when it exists!). We quote here three open problems about this topic the third one being a surprising result which precedes an unknown question:
1) It is not known of any integer that is a p. r. for infinitely many primes.
2) At least one of $2,3,5$ is a p.r. for infinitely many primes.  But it is not known which of these.
3)(Gupta-Murty and Heath-Brown) All prime with at most two exceptions is a p. r. for infinitely many primes. But it is not known these exceptions.
