One can see that $$\mathbb{Z}/19\mathbb{Z}=\{[0],[1],\ldots,[18]\}=\{[0],[3^1],[3^2],\ldots,[3^{18}]\}.$$ If I have $\mathbb{Z}/p\mathbb{Z}$, $p>2$ prime, when is there a $k\in\{2,3,\ldots,p-1\}$ such that $[k ^n]$ and $[0]$ recover $\mathbb{Z}/p\mathbb{Z}$? Further, when is there a prime $k$?

I'm a little removed from my last algebra course, but this interested me and I couldn't come up with a solution offhand.

Edit: nonessential to answer, but appreciated: Regarding when $k$ is prime, are there any partial results for any special classes of primes $p$?

  • $\begingroup$ For your last question, see Greg Martin's paper linked in this answer. As long as $p$ is large enough and none of the L-functions of Dirichlet characters mod $p$ have zeroes of small height far away from the critical line, then there exists a rather small (less than some power of $\log p$) prime $k$ which works. In particular, GRH would imply this for all sufficiently large primes. $\endgroup$ – Erick Wong Jun 21 '17 at 16:33

The group $(\mathbb{Z}/p\mathbb{Z})^\times$ of non-zero elements of $\mathbb{Z}/p\mathbb{Z}$ is cyclic, which means there always exists an element $k\in\{1,\ldots,p-1\}$ whose powers, along with $[0]$, give every element of $\mathbb{Z}/p\mathbb{Z}$. Such a $k$ is called a primitive root modulo $p$. The number of primitive roots is $\varphi(p-1)$, the number of integers between $1$ and $p-1$ that are coprime to $p-1$.

Regarding trying to find a prime $k$ that does the job, this question gives an argument that the answer is probably yes, but that proving this might be very hard.


What you are really asking is "Can I find a generator for $(\Bbb Z/p\Bbb Z)^{\ast}$?"

The answer is "always", but there is no "general formula" for "how", and such a generator need not be some prime less than $p$.

The question of "if" there is always such a prime, is to the best of my knowledge, still open, but there "probably is".

As strange as it seems, trial-and-error is still the best method for investigating this question for any given $p$.

  • $\begingroup$ Sure, but this prime is not necessarily less than $n$. $\endgroup$ – David Wheeler Sep 24 '15 at 1:15
  • $\begingroup$ That there is such a prime (between $1$ and $p$ whose residue class generates the units modulo $p$). Feel free to edit my response if you feel this needs clarification. $\endgroup$ – David Wheeler Sep 24 '15 at 1:19
  • $\begingroup$ Ah, your second line is saying a given generator needn't be prime, and the third is saying it might be open if there is always a generator that is prime ($<n$). Nevermind. $\endgroup$ – whacka Sep 24 '15 at 1:22
  • $\begingroup$ I understand that the sequence $(a_k): a_k = a_0 + kp$ contains infinitely many (and thus at least one, right?) primes. This is the theorem you refer to yes? $\endgroup$ – David Wheeler Sep 24 '15 at 1:25
  • $\begingroup$ Yes, that is Dirichlet's theorem that I referred to. $\endgroup$ – whacka Sep 24 '15 at 3:20

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.