The standard definition is that $a\in\mathbb{Z}$ is a primitive root modulo $p$ if the order of $a$ modulo $p$ is $p-1$.


Let me rephrase, to motivate my generalization: $a\in\mathbb{Z}$ is a primitive root modulo $p$ if the linear recurrence defined by $x\_0=1$, $x\_n=ax\_{n-1}$ for $n\geq1$ has maximum possible period in $\mathbb{Z}/p\mathbb{Z}$.


So, we could define $(a\_1,\ldots,a\_r)\in\mathbb{Z}^r$ to be an $r$-primitive root modulo $p$ when the order $r$ linear recurrence defined by $x\_0=\cdots=x\_{r-2}=0$, $x\_{r-1}=1$, and $x\_n=a\_1x\_{n-1}+\cdots+a\_rx\_{n-r}$ for $n\geq r$ has the maximum possible period (for such sequences) in $\mathbb{Z}/p\mathbb{Z}$.


Is anything known about the generalized version of primitive roots I've described? I chose my initial values $x\_0=\cdots=x\_{r-2}=0$, $x\_{r-1}=1$ in analogy with the Fibonacci numbers, but is there a standard / most general choice? The starting values affect the period a lot, so it's important to be working with the "right" ones, I guess. What is the maximum achievable period for a linear recurrence in $\mathbb{Z}/p\mathbb{Z}$? An obvious upper bound is $p^r-1$, but it's not clear to me that this is the correct number to replace $p-1$ in the standard definition of primitive root. Is anything known in the direction of Artin's conjecture for "$r$-primitive roots", as I've called them?


Other thoughts: because there is no "formula" for the order of $a$ modulo $p$ (this would amount to a formula for the discrete logarithm), there certainly isn't a formula for the period of the linear recurrence defined by $(a\_1,\ldots,a\_r)$ modulo $p$. I tried to come up with one for a while before I realized this, so I just wanted to save anyone else the trouble.



Generalization of primitive roots
If $(a\_1,\ldots,a\_r)$ is an $r$-primitive root in your definition, then the polynomial $x^r-a\_1x^{r-1}-\cdots-a\_r$ is irreducible in $Z/pZ[x]$ and any of
its roots is a generator (i.e. a primitive root) of the multiplicative group of the field of $p^r$ elements and conversely. This maximal period is $p^r-1$. See, e.g., Lidl-Niederreiter Finite Fields.


