1
$\begingroup$

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

My Attempt:

Assume $\gcd(K,n)=1$ and $1 \leq K <n$. 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?

$\endgroup$
1
$\begingroup$

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<K\right>$ has $n/m$ elements. So if $m\not=1,$ then $\left<K\right>$ has less than $n$ elements, and $\left<K\right>\not=\mathbb{Z}_n.$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I'm not sure why it would have to have order n\m, may you please clarify? $\endgroup$ – orientablesurface Apr 13 '19 at 19:14
  • $\begingroup$ 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.$ $\endgroup$ – Melody Apr 13 '19 at 19:33
  • $\begingroup$ 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)$? $\endgroup$ – orientablesurface Apr 13 '19 at 21:16
  • $\begingroup$ 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. $\endgroup$ – Melody Apr 13 '19 at 21:20
  • $\begingroup$ Haha, Idk why but it doesn't seem very intuitive. $\endgroup$ – orientablesurface Apr 13 '19 at 21:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.