An integer $k$ is a generator of group $\mathbb{Z_n}$ if and only if $\gcd(k, n)=1$ An integer $k$ is a generator of the group $\mathbb{Z_n}$ if and only if $\gcd(k, n)=1$.
So $\langle k\rangle=\mathbb{Z_n}$ iff $\gcd(k,n) = 1$.
Is there any general way to prove this?
I see that it's so obvious but can't find a general way to prove it.
By Bezout, the integer has an inverse $\bmod n$ precisely when $(n,k)=1$.
But, $1$ generates $\Bbb Z_n$.  So once you can get $1$ it's all over.
If $\gcd(n,k)=d &gt; 1$, then $k/d$ is an integer, so
$$n . \frac{k}{d} = 0 \in \mathbb{Z}_n$$
so the order of $k$ is less than $n/d$, so it is striclty less than $n$, so $k$ does not generate $\mathbb{Z}_n$.
If $\gcd(n,k)=1$, then there exists $a,b$ such that $ak+bn=1$, so
$$ak=1 \in \mathbb{Z}_n$$
so the subgroup generated by $k$ contains $1$, which generates $\mathbb{Z}_n$, so it contains $\mathbb{Z}_n$, so it is $\mathbb{Z}_n$.