Need to prove this :
Let $a$ element in $\mathbb Z_n$ , then $a$ is the generator of group $(\mathbb Z_n,+)$ iff $\gcd(a,n)=1$
Have no idea how to prove this, would appreciate some guidance.
Need to prove this :
Let $a$ element in $\mathbb Z_n$ , then $a$ is the generator of group $(\mathbb Z_n,+)$ iff $\gcd(a,n)=1$
Have no idea how to prove this, would appreciate some guidance.
For the harder direction, consider the group elements $1\cdot a$, $2\cdot a$. and so on up to $n\cdot a$. Here $k\cdot a$ is an abbreviation for $a+a+\cdots +a$ ($k$ times).
If $1\le x\lt y \le n$, then $x\cdot a$ and $y\cdot a$ are distinct elements of our group. For suppose to the contrary that $x\cdot a\equiv y\cdot a\pmod{n}$. Then $n$ divides $(y-x)\cdot a$. But $n$ and $a$ are relatively prime, so $n$ divides $y-x$. This is impossible, since $1\le y-x\le n-1$.
Thus the objects $1\cdot a$, and so on up to $n\cdot a$ are distinct elements of our group. But the list has length $n$, so these must be all the elements of our group. This shows that $a$ is a generator of our group.
Hint: $n$ and $m$ are relatively primes iff there exist integers $u$ and $v$ such that $un+vm=1$.
Hint: if $a$ generates the group then $\bar 1$ should be obtained from $a$. But what does this mean in terms of congruence $\pmod n$?
Just a useful theorem which generalizes your question:
Theorem: Let $G=\langle a \rangle$ be a cyclic group of order $n$. If $b\in G$ and $b=a^s$, then $b$ can generate a subgroup of $G$ of order $\frac{n}{\gcd(n,s)}$.
Here you are looking for thoes elements which generate whole group. And we know that all elements in $\mathbb Z_n$ are as $a^s$ for some $s$ wherein $a$ is the generator of $\mathbb Z_n$. If we take $a=1$ when $\mathbb Z_n=\{0,1,2,...,n-1\}$ then $x=s.1$ will generate whole group, according to above theorem, if $(s,n)=1$. This is what you want and other answers tell.