Tour:Multiplicative group modulo n

This page is part of the Groupprops guided tour for beginners (Jump to beginning of tour)
PREVIOUS: Multiplicative monoid modulo n| UP: Introduction four (beginners)| NEXT: Elements of multiplicative group equal generators of additive group
General instructions for the tour | Pedagogical notes for the tour | Pedagogical notes for this part

WHAT YOU NEED TO DO:

• Understand the definition stated below.
• Convince yourself of the explanation that invertibility is the same as being relatively prime to $n$.
• Go through the examples, and convince yourself of facts (1) and (2).

Definition

Let $n$ be a positive integer. The multiplicative group modulo $n$ is the subgroup of the multiplicative monoid modulo n comprising the elements that have inverses.

Equivalently, it is the group, under multiplication, of elements in $\{0,1,2,\dots ,n-1\}$ that are relatively prime to $n$. (The two definitions are equivalent because if $a$ and $n$ are relatively prime, there exist integers $x,y$ such that $ax+ny=1$, so $ax\equiv 1\mod n$).

Facts

1. The order of the multiplicative group modulo $n$ equals the number of elements in $\{0,1,2,\dots ,n-1\}$ that are relatively prime to $n$. This number is termed the Euler-phi function or Euler totient function of $n$, and is denoted $\varphi (n)$.
2. For a prime $p$, $\varphi (p)=p-1$. In other words, every nonzero element less than $p$ is invertible modulo $p$.
3. The multiplicative group modulo $n$ is a cyclic group if and only if $n=2,4,p^{k},2p^{k}$ for $p$ an odd prime and $k$ a natural number.

This page is part of the Groupprops guided tour for beginners. Make notes of any doubts, confusions or comments you have about this page before proceeding.
PREVIOUS: Multiplicative monoid modulo n| UP: Introduction four (beginners)| NEXT: Elements of multiplicative group equal generators of additive group