# Prove: Generator of cyclic group of order $n$ has $k^{th}$ root iff $\gcd(n,k) = 1$

Suppose $G$ is a cyclic group with generator $a$ of order $n$. Let integer $k > 1$.

Prove: $a$ has a $k^{th}$ root iff $\gcd(n,k) = 1$.

What I have so far:

Suppose $\gcd(n,k) = 1$. Then there are integers $p,q$ such that $$np + kq = 1$$ So we have $$a^{np+kq} = a^{np}a^{kq} = (a^n)^p a^{kq} = ea^{kq} = a^{kq}$$ where $e \in G$ is the identity. Then $$a^{kq} = a \Rightarrow (a^q)^k = a$$ so there exists $b = a^q \in G$ such that $b^k = a$. This proves one part.

Now suppose there is a $b \in G$ such that $b^k = a$. How would we show that $\gcd(n,k) = 1$?

Thanks.

Suppose that $a= b^k$. We must have $b = a^r$ for some integer $r$ since $a$ generates $G$. Therefore $a = b^k = a^{rk}$. Hence $rk \equiv 1 \thinspace (mod \thinspace n)$ and so $gcd(k,n) = 1$.