When can $\mathbb{Z}/p\mathbb{Z}$ be recovered by $[0]$ and $[k ^n]$?

Question

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

Answer 1

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.

Answer 2

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$.