# Elements of multiplicative group equal generators of additive group

## 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.