CIS 798. The groups Z_n and Z_n^*.

• Equivalence classes: Each natural number n induces a partition on the set Z of integers: for an integer x, we write [x]_n for its equivalence class modulo n, which is the set of all integers that are equal to x modulo n. For example, if n equals 17 and x equals 5, then [x]_n is the set {-29,-12,5,22,39,...}. In our course, we already wrote expressions such as

  x = y mod n.

  which means that the classes [x]_n and [y]_n are equal.

• The group Z_n: This group has as elements the equivalence classes [0]_n, [1]_n, ..., [n-1]_n; note that there are n many such classes. Its identity element is the class [0]_n, which is a two-sided identity for the addition of classes, defined as

  [x]_n + [y]_n =^def [x+y]_n.

  Exercise: Compute the class [11]₁₃ + [5]₁₃.

  In the exercises, you will show that this definition actually makes sense. Note that this addition is associate, that [0]_n is a two-sided identity for this addition and that each class [x]_n has an additive inverse, namely the class [-x]_n. Thus, (Z_n,+,[0]_n) is an example of a finite, commutative group.

  Exercise: Compute the class [11]₁₃ + [5]₁₃ - [8]₁₃.

• The group Z_n^*:
  • First, we define a multiplication on the elements of Z_n:

    [x]_n * [y]_n =^def [x*y]_n.

    In the exercises, you will show that this definition actually makes sense.

  • We call a class [x]_n invertible iff there is some class [y]_n such that [x]_n * [y]_n equals [1]_n. We will also say that x is invertible modulo n.
  • The elements of Z_n^* are exactly the invertible elements of Z_n.
  • Fact: a class [x]_n is invertible iff x has no common factor with n.
  • Consequence: if n is prime, then Z_n^* has n-1 elements, the classes [1]_n, [2]_n, ..., [n-1]_n.
  • Example: if n equals 6, then there are only two invertible classes, namely [1]₆ and [5]₆. All other classes have a common factor with 6. (Question: What is the inverse of [5]₆?)
  • Euler's totient function: For a natural number n, we define Phi(n) to be the number of elements in Z_n^*. For example, we saw that Phi(6)=2 and Phi(p)=p-1 for all primes p.
  • Exercise #11(a) on page 56: Let p and q be prime. Then Phi(p*q)=(p-1)*(q-1).
• Fermat's Theorem: If p is prime and if a is an element of {1,2,...,p-1}, then a^p-1 mod p = 1.

  Since p is prime, a does not have a common factor with p. Therefore, a is invertible modulo p, so it suffices to show that a^p mod p = a, for we can then "divide" both sides of the equation by a. We show a^p mod p = a by mathematical induction on a:

  • Base case: If a equals 1, then a^p mod p equals 1 as well, but this is just a.
  • Inductive step: Assume that a^p mod p = a holds. We need to show that (a+1)^p mod p = a+1 holds as well. For that, we use the binomial theorem, noting that choose(p,k) contains p as a factor if 1 < k < p. Thus, we get (a+1)^p mod p = a^p mod p + 1^p mod p = a^p mod p + 1 = a + 1 by our induction hypothesis.