# Generators for $\mathbb{Z_n}$

I would like to show that $$K$$ is a generator for $$\mathbb{Z}_n$$ $$\iff$$ $$\gcd(K,n)=1$$ and $$1 \leq K .

My Attempt:

Assume $$\gcd(K,n)=1$$ and $$1 \leq K . That means $$K \in \mathbb{Z}_n$$ and so it suffices to show that $$\mathbb{Z}_n\subset \langle K\rangle$$ . Let $$x \in \mathbb{Z}_n$$ be arbitrary and so by bezouts lemma, there exists integers $$a,b$$ such that $$aK+yn=1$$, hence $$x=x^{aK+yn}=x^{aK}$$ (since $$\mathbb{Z}_n$$ under addition is cyclic). But $$x^{aK}=(aK)x=(ax)K$$ and so $$x \in \langle K\rangle$$. Is this proof so far correct? How would I prove the other direction?

## 1 Answer

It seems correct, yes. For the other direction I'd suggest contrapositive. If $$\text{gcd}(K,n)=m,$$ then $$\text{lcm}(K,n)=Kn/m=K(n/m),$$ so $$K$$ has order $$n/m,$$ and $$\left$$ has $$n/m$$ elements. So if $$m\not=1,$$ then $$\left$$ has less than $$n$$ elements, and $$\left\not=\mathbb{Z}_n.$$

• I'm not sure why it would have to have order n\m, may you please clarify? – orientablesurface Apr 13 '19 at 19:14
• Look at $K,K2,K3,...,K(n/m).$ The only term in this list that is congruent to $0$ modulo $n$ is $K(n/m),$ as $K(n/m)$ is the least common multiple of $K$ and $n.$ This is exactly what it means for $K$ to have order $n/m$ in $\mathbb{Z}_n.$ – Melody Apr 13 '19 at 19:33
• Can't I just prove it by saying assume there is another integer r such that $Kr=0$ and the $Kr=K(n/m)$ and so $r= (n/m)$? – orientablesurface Apr 13 '19 at 21:16
• No, it's more nuanced than that. Like, $4\cdot 2\equiv 0(\mod 8)$ and $4\cdot 4\equiv 0(\mod 8),$ but $4\not\equiv 2(\mod 8).$ You could show it by assuming that $1\leq r\leq n/m,$ and then since $n/m$ is the least common multiple deducing that $r=n/m,$ but that's essentially what I said in other words. – Melody Apr 13 '19 at 21:20
• Haha, Idk why but it doesn't seem very intuitive. – orientablesurface Apr 13 '19 at 21:35