1
$\begingroup$

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.

  • 1
    You mean a is a generator, not the generator of the group.2012-12-30

4 Answers 4

1

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.

  • 0
    @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.2013-01-06
2

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

  • 0
    @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$.2012-12-30
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$?

  • 0
    You are working whit additive group. So you should use $ka$. See the other hint above.2012-12-30
1

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.