# proving that an element g is primitive

How do I go about proving that an element g is primitive? If I let p be a prime. Is it then the same as proving that every non-zero element in $$Z_p$$ can be written as a power of g?

• That is the definition of what it means to be primitive. So yes. – TonyK May 29 at 10:09

If you can factorize $$p-1$$, then it is enough to show that for all prime divisors $$q$$ of $$p-1$$, $$g^{(p-1)/q}$$ is not equal to $$1$$ mod $$p$$. This can be checked efficiently for $$p$$ in the thousands of digits.