# 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?

• You can brute-force it. More or less brute. If you know quadratic reciprocity, it is not hard to see that $\bigl(\frac{3}{17}\bigr) = -1$, so $3$ is a primitive root modulo $17$ (since $17 - 1 = 16$ is a power of $2$). Once you have found one primitive $r$ root modulo $p$, the others are $r^k$ where $\gcd(k,p-1) = 1$. – Daniel Fischer Jul 3 '15 at 19:32
• Just as a matter of experience, I’ve found it rare that the brute-force method usually finds a generator in $\{2,3,5\}$. – Lubin Jul 4 '15 at 0:55

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.