Primitive Roots modulo p

Question

I'm asked the following question: Prove that $b$ is a primitive root modulo $p \implies$ the smallest positive exponent $e$ such that $b^e \equiv 1 \pmod p$ is $p - 1$.

I know that this could probably be shown easily with Fermat's Little Theorem, but it's posed to the reader before Fermat's Little Theorem is even discussed.

How should I approach this problem? Is there a simple argument for why this is true that doesn't require quite as much ingenuity as the proofs of Fermat's Little Theorem? (i.e., the ones that involve $(p-1)!$ or group theory)

Answer 1

In that case, look at all the powers of $b$, i.e. $b, b^2, b^3 \cdots$ modulo $p$ If $b^e\equiv 1 \mod p$, then the pattern repeats after $b^e$, i.e you get the same $e$ terms. So the totality of all numbers you can generate is $e+1$. But for a primitive root, you generate $p$ terms. So, $e=p-1$.

By the way the same holds for non-primes also. You just replace the condition by $e=\phi(p)$ using the same logic.

Answer 2

If you regard a primitive root module $p$ as being a number $b$ that, when raised to a suitable power, can achieve equivalence with any number coprime to $p$, then the argument can go as follows:

By the definition above, there must be a value $s$ such that $b^s \equiv 1 \bmod p$, which we'll take as the smallest such positive value. However this means that $b^{s+k} \equiv b^k \bmod p$, so $b$ can achieve at most $s$ different equivalences. Since our definition of $b$ requires that powers of $b$ are equivalent to each non-zero residue class of $p$, $s$ must be at least $(p-1)$.

If two positive powers of $b$ less than $p-1$ are in the same equivalence class, say $p-1>d>c$ and $b^c \equiv b^d$, then we would have $b^{d-c}\equiv 1$ and this is not allowed by the previous argument on the definition of $b$. So all $b^k$, $0<k\le s$, are in different equivalence classes, and $s= p-1$.