# group generator

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.

-
You mean a is a generator, not the generator of the group. – 1015 Dec 30 '12 at 17:15

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.

-
May I ask to look at my answer. Thanks Andre for your time and sorry for this request. ;-) – Babak S. Dec 31 '12 at 9:15
@BabakSorouh: It is a good thing to point out the generalization, as you did. And the generalization is certainly correct. My inclination would be to deal with the general after the more concrete special case. – André Nicolas Jan 6 '13 at 16:35

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$?

-
Why the down vote? – Sigur Dec 30 '12 at 17:02
a^k mod n = 1? didnt quite understand.... – baaa12 Dec 30 '12 at 17:06
You are working whit additive group. So you should use $ka$. See the other hint above. – Sigur Dec 30 '12 at 17:08

Hint: $n$ and $m$ are relatively primes iff there exist integers $u$ and $v$ such that $un+vm=1$.

-
OK au+nv=1 I knew that but cant see how it helps me. what are u and v?? – baaa12 Dec 30 '12 at 17:07
@baaa12, $u,v$ are integers. This is a result on number theory. After that you write $au=1-nv$ and take the congruence class, i.e. $\bar a\bar u=\bar 1$. – Sigur Dec 30 '12 at 17:12

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.

-