5

For a Fermat prime or an "upper" Sophie Germain prime a primitive root is explicitly known. Are there further results when the factorization of p-1 is known? Is it unlikely that we ever get explicit formulas for larger classes of primes, not only for such quite special cases?

Landei
  • 397
  • 3
    There are a few others. Here is one in the Sophie Germain family. If $q$ and $p=4q+1$ are prime, then $2$ is a primitive root of $p$, as is $3$ if $q\gt 3$. – André Nicolas Jun 11 '13 at 06:57

1 Answers1

2

Yes, there is an explicit formula, given by Horst Bergmann in "Über eine Formel für primitive Kongruenzwurzeln" (Elemente der Mathematik, 1983).

For every odd prime p:

$w = \sum_{r = 2}^{p-1} r P(r) \prod_{s = 1}^{r-1}(1 - P(s))$, with $P(t) = \prod_{m = 1}^{p-2}(t^m - 1)$

It works, and although it isn't very useful for computation, I find it still very strange that this amazing result seems to be nearly forgotten (e.g. isn't mentioned in Wikipedia or Mathworld)

Stefan Perko
  • 12,467
Landei
  • 397