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?

  • 4
    $\begingroup$ 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$. $\endgroup$ – Daniel Fischer Jul 3 '15 at 19:32
  • $\begingroup$ Just as a matter of experience, I’ve found it rare that the brute-force method usually finds a generator in $\{2,3,5\}$. $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.