What are primitive roots modulo n?

Another equivalent definition of a primitive root mod $n$ is (from Wikipedia),

a number $g$ is a primitive root modulo $n$ if every number coprime to $n$ is congruent to a power of $g$ modulo $n$

For example, $3$ is a primitive root modulo $7$, but not modulo $11$, because

Modulo $7$, $$3^0\equiv1,\; 3^1\equiv3,\; 3^2\equiv2,\; 3^3\equiv6,\; 3^4\equiv4,\; 3^5\equiv5,\; 3^6\equiv1\pmod{7}$$

And you got all the possible results: $1, 3, 2, 6, 4, 5$. You can't get a $0$, but $0$ is not coprime to $7$, so it's not a problem. Hence $3$ is a primitive root modulo $7$.

Whereas, modulo $11$, $$3^0\equiv1,\; 3^1\equiv3,\; 3^2\equiv9,\; 3^3\equiv5,\; 3^4\equiv4,\; 3^5\equiv1\pmod{11}$$

And modulo $11$, you only got the possible values $1, 3, 9, 5, 4$ and the sequence starts repeating after $3^5$, sou you will never get a $3^k\equiv2$, for example. Hence $3$ is not a primitive root modulo $11$.

The sequence $g^k$ is always repeating modulo $n$ after some value of $k$, since it can undertake only a finite number of values (so at least one value appears at least twice, for say $r,s$ and $r>s$ you have $g^r \equiv g^{s}$), and one term depends only on the preceding: $g^{k+1}\equiv g\cdot g^k$. Thus $g^{r+k}\equiv g^{s+k}$ for all $k$.

If $g$ and $n$ are coprime, it gets a bit simpler, because $g^k\equiv g^{k'} \pmod{n}$ for some $k, k'$ with $k>k'$ implies $g^{k-k'}\equiv 1$ (you can take the modular inverse because then all $g^k$ are coprime to $n$), then with $r=k-k'$, you have $g^{k+r}\equiv g^kg^r\equiv g^k$ for all $k$.

If $g$ and $n$ are not coprime, it's not as simple: if $g^r \equiv 0 \pmod{n}$ for some $r$ then $g^{k+r}\equiv g^kg^r\equiv 0$ for all $k$. But you may also have a repeating sequence without any $1$, for example, modulo $15$,

$$3^0\equiv1,\; 3^1\equiv3,\; 3^2\equiv9,\; 3^3\equiv12,\; 3^4\equiv6,\; 3^5\equiv3\pmod{15}$$

And it starts repeating after $3^4$, with numbers not coprime to $15$ since $g=3$ is not coprime to $n$ either. And actually, if $g$ and $n$ are not coprime, you never get a $1$ again after $g^0\equiv1 \pmod{n}$, because all $g^k$ have a common factor with $n$.

Alternately, the multiplicative order of $g$ modulo $n$ is the smallest exponent $k$ such that $g^k\equiv 1\pmod{n}$.

Here you see that the multiplicative order of $3$ modulo $7$ is $6$, and the multiplicative order of $3$ modulo $11$ is $5$, so by your definition, $3$ is indeed a primitive root modulo $7$, but not modulo $11$.

Notice also that the multiplicative order of $g$ modulo a prime $p$ is always less or equal to $p-1$, since Fermat's little theorem states that for a prime $p$ and $a$ not divisible by $p$, $a^{p-1}\equiv 1 \pmod{p}$. Then the multiplicative order is also always a divisor of $p-1$, and it leads to a simple algorithm to look for primitive roots:

To test a possible $g$, take the integer factorization of $p-1$, and for every prime factor $d$ of $p-1$, compute $g^{(p-1)/d}$ modulo $p$. If none of these is $1$, then $g$ is a primitive root modulo $p$, since $k=p-1$ is then the smallest $k$ such that $g^k\equiv 1\pmod{p}$.

For large $p$ and using modular exponentiation by squaring, it's much faster than computing all $g^k$ modulo $p$ for $k=0,1,\ldots,p-1$ and checking if all possible values are there (but you still need an integer factorization).

You’re wondering about the ring (with additive structure and multiplicative structure) $\mathbb Z$ modulo $n$, often denoted $\mathbb Z/(n)$. You can add and you can multiply modulo $n$, the operations make good sense.

For a general (not necessarily prime) $n$, the multiplicative structure can be fairly ill-behaved. For instance, when $n=8$, you have $4\cdot2=0$, product of two nonzero things coming out to be zero. There are quantities modulo $n$ (“residues mod $n$”) that have reciprocals, however: for the case $n=15$, we have $2\cdot8=1$, modulo $15$. The residues that do have reciprocals can be denoted $(\mathbb Z/(n))^*$ or some such, and this system is a multiplicative structure on its own, a “multiplicative group”. Under certain circumstances, this multiplicative group is “cyclic”, that is, there is one particular element whose powers run through all the things in $(\mathbb Z/(n))^*$. For instance, you can check that the elements of $(\mathbb Z/(9))^*$ are $\{1,2,4,5,7,8\}$, and you can also check that every one of these is a power of two, modulo nine. When there is such a nice residue as $2$ is here, it’s called a primitive root, and it’s a serious Theorem that when $n$ is a prime, there always is a primitive root. For instance, $n=5$ has $2$ for a p.r., $n=7$ can’t use $2$, but $3$ is a good p.r. There are some helpful guidelines for finding a primitive root, but I don’t want to go there tonight. The important fact is that the only numbers $n$ that have primitive roots modulo $n$ are of the form $2^\varepsilon p^m$, where $\varepsilon$ is either $0$ or $1$, $p$ is an odd prime, and $m\ge0$