Tour:Multiplicative group modulo n

From Groupprops
Jump to: navigation, search
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