That $\Bbb Z_p^×$ is cyclic. Keith Conrad has amassed, at least, $10$ or $11$ different proofs of this fact
It was proven by Gauß in his $1801$ Disquisitiones Arithmeticae, an existence and a constructive proof. First Lambert, then Euler, then Gauß were playing with the notion of a primitive.
There's a constructive proof in Vinogradov's Elements of Number Theory.
