# Prove that the generators of $\mathbb{Z}_n$ are the integers $r$ such that $0\leq r <n$ and $\gcd(r,n)=1$. [duplicate]

Can someone tell me whether my solution is okay? I based it off a proof for a more general theorem about cyclic groups and generators.

Prove that the generators of $\mathbb{Z}_n$ are the integers $r$ such that $0\leq r <n$ and $\gcd(r,n)=1$.

Let $\mathbb{Z}_{n}=\langle 1 \rangle$. Since $0\leq r <n$, $\langle r\rangle \subset \langle 1 \rangle$. Then let $\mathbb{Z}_n=\langle r \rangle$ and assume that $d=\gcd(r,n)>1$. Then there exist integers $t$ and $s$ such that $r=td$ and $n=sd$. Then $rs=tds=tn=1$ (since $|\mathbb{Z}_n|=|\langle 1 \rangle|=n$). Then $|\langle r\rangle|\leq s<n$. This forms a contradiction (if $|\mathbb{Z}_n|=n$ and $\mathbb{Z}_{n}=\langle r \rangle$ with $|\langle r\rangle|<n$, then $|\mathbb{Z}_n|\neq n$) by assuming that $\gcd(r,n)>1$.

## marked as duplicate by Jyrki Lahtonen group-theory StackExchange.ready(function() { if (StackExchange.options.isMobile) return; $('.dupe-hammer-message-hover:not(.hover-bound)').each(function() { var$hover = $(this).addClass('hover-bound'),$msg = $hover.siblings('.dupe-hammer-message');$hover.hover( function() { $hover.showInfoMessage('', { messageElement:$msg.clone().show(), transient: false, position: { my: 'bottom left', at: 'top center', offsetTop: -7 }, dismissable: false, relativeToBody: true }); }, function() { StackExchange.helpers.removeMessages(); } ); }); }); Aug 17 '18 at 6:42

There are several issues. For instance, you can't say “Let $\mathbb{Z}=\langle1\rangle$”, because an assertion of the type “Let $A=\cdots$” should be a definition of $A$ and you are clearly not defining $\mathbb{Z}_n$.
Your idea of proving that if $\gcd(r,n)>1$, then $\langle r\rangle\neq\mathbb{Z}_n$ is correct. What you proved was that $\bigl\lvert\langle r\rangle\bigr\rvert<n=\lvert\mathbb{Z}_n\rvert$. But this is only half of what you were supposed to have proved. Indeed, it remains to be proved that if $\gcd(r,n)=1$, then $\langle r\rangle=\mathbb{Z}_n$. This can be done noting that, if $0<k,k'\leqslant n$ and $k\neq k'$, then $kr\neq k'r$ in $\mathbb{Z}_n$; which means that $n\nmid kr-k'r$. But that's easy: if $n\mid(k-k')r$ then, since $\gcd(r,n)=1$, then $n\mid k-k'$, which is impossible, since$$k-k'\in\bigl\{\pm1,\pm2,\ldots\pm(n-1)\bigr\}\setminus\{0\}.$$This proves that $\bigl\lvert\langle r\rangle\bigr\rvert=n=\lvert\mathbb{Z}_n\rvert$ and that therefore $\langle r\rangle=\mathbb{Z}_n$.