An element of order $\phi(n)$ in $\mathbb{Z}/n\mathbb{Z}$ generates the multiplicative group

Question

Suppose $x$ is an element of order $\phi(n)$ in $\mathbb{Z}/n\mathbb{Z}$. Then every invertible element of $\mathbb{Z}/n\mathbb{Z}$ is a power of $x$.

The lecture taught me that when this is the case, x is called a primitive element, and that I understood. But, how do I prove this theorem?

I know every invertible element has at least $a^{\phi(n)} = 1$, and that order(a) | $\phi(n)$
...but I wouldn't know how to put things together into a valid proof.

Answer 1

Define $\phi(n)$ as $$\phi(n)=\operatorname{Card}\{k,\;1\le k\le n\;| \gcd(k,n)=1\}$$ then it isn't hard to see that $\overline k$ is invertible in $\Bbb Z_n$ if and only if $\gcd(k,n)=1$ so $\phi(n)$ is the cardinal of the group of the invertible elements of $\Bbb Z_n$ and if there's $\overline x$ of order $\phi(n)$ then this group is cyclic generated by $\overline x$ and so every invertible element is a power of $\overline x$.

Answer 2

The number of invertible elements in $\mathbb{Z}/n\mathbb{Z}$ is $\phi(n)$. So if you find an element, $x$ of order $\phi(n)$, this means that there are $\phi(n)$ distinct powers of $x$. This means these powers of $x$ must exhaust all the invertible elements of $\mathbb{Z}/n\mathbb{Z}$