0
$\begingroup$

In Integer and modular addition of Cyclic group:

For every positive integer n, the set of integers modulo n, again with the operation of addition, forms a finite cyclic group, the group Z/n. An element g is a generator of this group if g is relatively prime to n. Thus, the number of different generators is φ(n), where φ is the Euler totient function, the function that counts the number of numbers modulo n that are relatively prime to n. Every finite cyclic group is isomorphic to a group Z/n, where n is the order of the group.

I have following doubts about the above statements:
(1)

For every positive integer n, the set of integers modulo n, again with the operation of addition, forms a finite cyclic group, the group Z/n.

I am not a nitpicker, but think it should be "again with the operation of addition modulo n", right?

(2)

An element g is a generator of this group if g is relatively prime to n.

How can prove the the g and n must be coprime?

$\endgroup$
  • $\begingroup$ Your "nitpick" is correct. $\endgroup$ – quasi Mar 2 '17 at 8:43
  • 1
    $\begingroup$ If $g,n$ are not coprime, you can't generate $1$. Suppose $g,n$ have a common factor, $d$ say, where $d > 1$. Then any multiple of $g$ will be a multiple of $d$, and will still be a multiple of $d$ after you mod out by $n$, so you can't get $1$. $\endgroup$ – quasi Mar 2 '17 at 8:44
  • $\begingroup$ @quasi Thanks for your comments? Forgive my greedy requirement, how can manifest if g and n are coprime, the g must be the generator? $\endgroup$ – Nan Xiao Mar 2 '17 at 9:24
  • 1
    $\begingroup$ Suppose $g,n$ are coprime. Show that no two of the $n$ numbers $$0,g,2g,...,(n-1)g$$ are congruent mod $n$, hence they are still pairwise non-congruent when modded out by $n$. But then g generates all $n$ elements of $Z_n$. $\endgroup$ – quasi Mar 2 '17 at 9:27
  • $\begingroup$ two of the n numbers are congruent mod n”? If I understand right, the n numbers mod n should generate 0, 1, ... n-1. Right? Thanks! $\endgroup$ – Nan Xiao Mar 2 '17 at 9:55
0
$\begingroup$

Given any number $u \in \Bbb Z$. Saying that $g$ is a generator$\mod n$ is equivalent to say $\exists x, y \in \Bbb Z: u = xg+yn$. But if $g$ and $n$ share a factor $d$ so does $u$, so values of $u$ which are not multiples of $d$ can't be reached.

$\endgroup$

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.