A primitive root mod p is an integer g whose powers g^1, g^2, ..., g^(p-1) exhaust all nonzero residues mod p. Equivalently, g has order p-1. Every prime p has primitive roots, making (Z/pZ)* cyclic of order p-1.
Fermat's Little Theorem tells you that every nonzero residue a mod p satisfies a^(p-1) ≡ 1 (mod p), but it doesn't reveal the *smallest* exponent with this property. The order of a mod p is the smallest positive integer d such that a^d ≡ 1 (mod p). Because a^(p-1) ≡ 1, the order d must divide p-1. Some elements have small order — for instance, 1 always has order 1, and if p-1 is even then −1 has order 2 — but the question is whether any element achieves the maximum possible order p-1. Such an element is a primitive root mod p.
When g is a primitive root, the p-1 powers g, g^2, ..., g^(p-1) are all distinct (if g^i ≡ g^j with i < j, then g^(j-i) ≡ 1, contradicting the minimality of p-1). Since there are exactly p-1 nonzero residues mod p and the powers produce p-1 distinct values, every nonzero residue appears exactly once. The group (Z/pZ)* is cyclic: it is generated by a single element, exactly as the integers mod n under addition are generated by 1. This is a structural fact about primes — non-prime moduli don't always have primitive roots.
The existence of primitive roots mod every prime is a theorem, not obvious. The count is given by Euler's totient function: exactly φ(p-1) of the p-1 nonzero residues are primitive roots. For p = 7, p-1 = 6 and φ(6) = 2, so exactly two primitive roots exist — they are 3 and 5. Verify: 3^1=3, 3^2=2, 3^3=6, 3^4=4, 3^5=5, 3^6=1 (mod 7) — all six residues appear. Once you find one primitive root g, the others are exactly the powers g^k where gcd(k, p-1) = 1.
Primitive roots are the key to defining discrete logarithms: if g is a primitive root mod p and a is any nonzero residue, there is a unique x in {0, 1, ..., p-2} with g^x ≡ a (mod p). This x is the discrete logarithm of a to base g, written log_g(a). Computing discrete logarithms — given g, p, and a, find x — is believed to be computationally hard for large primes. The security of Diffie-Hellman key exchange and ElGamal encryption rests on this hardness. The cyclic structure you've built here is precisely the algebraic foundation these cryptographic protocols exploit.