5
$\begingroup$

I'm trying to find a small primitive root modulo $p^k$, where $p$ is prime. My strategy is to test small numbers $g=2,3,\ldots$ until I find a primitive root modulo $p$. That is, until $ord_pg=\phi(p)=p-1$. There are results that suggest such a search won't take long.

To go from modulo $p$ to modulo $p^k$, there is the following well-known theorem:

Thm: If $g$ is a primitive root modulo $p$, then $$\begin{cases} g+p & g^{p-1}\equiv 1\pmod{p^2}\\g & g^{p-1}\not\equiv 1\pmod{p^2}\end{cases}$$ is a primitive root modulo $p^k$, for all $k\in\mathbb{N}.$

However, I was unable to find an example that falls into the first case (except $p=2$, trivially). Hence, I have two related questions:

  1. Are there any odd primes $p$, and primitive roots $g$, such that $g^{p-1}\equiv 1\pmod{p^2}$?
  2. Are there any odd primes $p$, and minimal primitive roots $g$, such that $g^{p-1}\equiv 1\pmod{p^2}$?
$\endgroup$
  • $\begingroup$ I have heard finding primitive roots is not easy. $\endgroup$ – Pedro Tamaroff Mar 19 '14 at 18:33
4
+200
$\begingroup$

With computer search I found that $g=5$ for $p = 40487$ is an example of (2) . http://www.wolframalpha.com/input/?i=5%5E40486+mod+1639197169

I would guess that this should happen with probability $1/p$. $\sum_{2 < p \le 40487} \frac 1p = 2.1235$ only. In retrospect it makes sense that the examples are rare.

$\endgroup$
  • $\begingroup$ Nice, thanks. Will pay bounty once permitted. $\endgroup$ – vadim123 Mar 23 '14 at 18:16
  • $\begingroup$ Whoops, awarded bounty incorrectly. Will fix. $\endgroup$ – vadim123 Mar 24 '14 at 14:41
4
+100
$\begingroup$

For your first question, consider $p=71$ and $g=11$. Here, $11$ is a primitive root modulo $71$, but $11^{70}\equiv 1 \bmod 71^2$. Unfortunately, this is not an example of your second question, because $7\bmod 71$ is also a primitive root.

I found this example looking at lists of Wieferich primes with respect to a certain base. There is probably an example for your second question farther down the list; I see no reason why there couldn't be one.

I just checked the first $103$ odd primes $p$ and none of them satisfy $(2)$, with $g$ the smallest positive primitive root modulo $p$.

$\endgroup$
1
$\begingroup$

Surprisingly, only two odd primes are known such that the smallest primitive root mod $p$ is not a primitive root mod $p^2$: $40487$ and $6692367337$. See OEIS:A055578.

$\endgroup$

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.