Tour:Elements of multiplicative group equal generators of additive group
This article adapts material from the main article: elements of multiplicative group equal generators of additive group
This page is part of the Groupprops guided tour for beginners (Jump to beginning of tour)
PREVIOUS: Multiplicative group modulo n| UP: Introduction four (beginners)| NEXT: Multiplicative group modulo a prime is cyclic
General instructions for the tour | Pedagogical notes for the tour | Pedagogical notes for this part
WHAT YOU NEED TO DO:
- Carefully understand the statement below, and try proving it yourself.
- Need the proof and make sure you understand it.
Contents
Statement
Let be a positive integer, and consider the group of integers modulo n. Then, an element in this is a generator for the group of integers modulo
if and only if it is an element of the multiplicative group modulo
.
Note that these are also the same as the elements in that are relatively prime to
, and the number of such elements is
.
Proof
Generator of additive group implies element of multiplicative group
If is a generator of
, then some integer multiple of
must be equal to the element
. Thus, there exists
such that
in
. Viewing
as a congruence class modulo
, we see that
is invertible modulo
, and hence is in the multiplicative group.
Element of multiplicative group implies generator of additive group
If is a element of the multiplicative group modulo
, there exists an integer
such that
. Thus, the cyclic subgroup containing
must also contain
. But any subgroup containing
must equal the whole group
, so
generates the whole group.
This page is part of the Groupprops guided tour for beginners (Jump to beginning of tour)
PREVIOUS: Multiplicative group modulo n| UP: Introduction four (beginners)| NEXT: Multiplicative group modulo a prime is cyclic
General instructions for the tour | Pedagogical notes for the tour | Pedagogical notes for this part