Bevis:Vis at et element $m \in \mathbb{Z}_n$ er en generator hvis og bare hvis $\gcd(m, n) = 1$.
$(\Longrightarrow)$ Hvis $m$ er et genererende element for gruppa så er vi gitt at $\{km \pmod{n}: k\in \mathbb{Z} \} = \mathbb{Z}_n$. Dvs. at for konstanter $k_i \in \mathbb{Z}$, må vi ha at $$\begin{alignat*}{2}
k_0m &\equiv 0 \pmod{n} \\
k_1m &\equiv 1 \pmod{n} \\
&\vdots \\
k_{n-1}m &\equiv n-1 \pmod{n}
\end{alignat*}$$ Alle disse er på formen $k_im \equiv i \pmod{n}$ som er ekvivalent med $k_im - yn = i$, som er løsbar hvis og bare hvis $\gcd(m,n) \mid i$. Siden $i=0,1,2,\dots,n-1$, må vi ha $\gcd(m,n)=1$ siden $1$ er det eneste tallet som deler alle disse $i$.
$(\Longleftarrow)$ Av Bézouts lemma $\gcd(m,n)=1 \implies \exists x,y \in \mathbb{Z}: mx+ny = 1 \Longleftrightarrow mx \equiv 1 \pmod{n}$ Gang den siste kongruensen med $k$ for $k=0,1,\dots,n-1$ og da fås at $m(xk) \equiv k \pmod{n}$ og $xk \in \mathbb{Z}$ så $m$ genererer $\mathbb{Z}_n$. $ \blacksquare$