M4P14 Elementary Number Theory Algebra Handout

This handout is intended for those who have not been to M2P2 and M2P4.

Finite abelian groups.

Let G be a finite set with an operation that associates to any two elements of G an element of G. We denote this operation by +, so that if a and b are in G, then a + b is again an element of G. The properties that this operation has to satisfy are

(1) associativity: (a + b) + c = a + (b + c) for any a, b, c ∈ G;

(2) there exists a distinguished element in G, denoted by 0, such that a + 0 = 0 + a = a for any a ∈ G;

(3) for any a ∈ G there exists b ∈ G such that a + b = 0;

(4) commutativity: a + b = b + a for any a, b ∈ G (groups satisfying (4) are called abelian or commutative).

An isomorphism of groups is a bijection G_{1} → G_{2} that matches the group operation on both sides.

An example of group is G = ℤ/n with its additive structure. Every element of ℤ/n is obtained from \overline{1} by adding it with itself a certain number of times. A finite group G that has a element g such that every element of G is obtained by adding g with itself a certain number of times is called cyclic, and g is called a generator. (G may have more than one generator or none.) Note that any finite cyclic group of n elements is isomorphic to ℤ/n. We build an isomorphism by sending a generator to \overline{1} ∈ ℤ/n.

Another example of group: binary vectors (x_{1}, …, x_{n}), x_{i} = 0 or 1, with coordinate-wise addition modulo 2. Here the zero element is (0, …, 0).

Exercise: Check that all the axioms hold. Show that if n > 1, then this group is not cyclic.

Consider the product ℤ/n_{1}×… ℤ/n_{m}, i.e., the set of m-tuples (x_{1}, …, x_{m}), where each x_{i} is in ℤ/n_{i}. Define the group structure as the coordinate-wise addition. Again, it is easy to check that all the axioms hold. The main theorem about finite abelian groups is that every group is of such a form. A more learned expression is: “every finite abelian group is isomorphic to a product of cyclic groups”.

For g ∈ G, and m a positive integer we write mg for g + g + … + g ∈ G (m times).

An order of an element g ∈ G is the smallest positive integer m such that mg = 0. Why does such a number exists? Since G is finite there must exist two distinct positive integers r and s such that rg = sg. Assume w.l.o.g. that r > s. Let h ∈ G be the inverse of g, that is, h + g = 0. Then rg = sg implies (r − 1)g = rg + h = sg + h = (s − 1)g. Do this s times. We obtain (r − s)g = 0. Hence the set of positive integers m such that mg = 0 is not empty, thus it contains a smallest element.

Lagrange’s theorem says that the order of any g ∈ G divides the number of elements in G. The proof runs like this. Let n be the order of g. A coset of a ∈ G is defined as the set {a, a+g, a+2g, …, a+(n−1)g}. Let a, b ∈ G. Then the cosets of a and of b either coincide or are disjoint. (Indeed, if a + rg = b + sg and, say r ≥ s, then after adding sh to both sides we obtain b = a + (r − s)g. Hence b is in the coset of a, and so is any element of the coset of b. Since every coset has n elements, the cosets of a and of b are the same.) Thus G is a disjoint union of subsets of cardinality n. Therefore, n divides |G|.

Exercise: adapt this proof to show that if H ⊂ G is a subgroup (i.e., a subset that is a group under the group operation inherited from G), then |H| divides |G|.

Rings and ideals.

A ring R is an abelian group with the group operation written additively, and another operation, written as multiplication. The multiplication satisfies axioms similar to the group axioms above except for the existence of the inverse. These are:

(a) associativity: (ab)c = a(bc) for any a, b, c ∈ R;

(b) there exists a distinguished element in R, denoted by 1, such that a × 1 = 1 × a = a for any a ∈ R;

(c) commutativity: ab = ba for any a, b ∈ R (rings satisfying (c) are called commutative).

Moreover, there is an axiom that links addition and multiplication:

(d) distributivity: (a + b)c = ac + bc for any a, b, c ∈ R.

Two rings are isomorphic if there is a bijection between them such that the addition and multiplication of both sides are the same.

There are many examples of commutative rings: integers ℤ, polynomials with coefficients in ℝ or ℤ, continuous functions ℝ → ℝ.

An ideal I ⊂ R is a subset that is closed under addition and taking the additive inverse (a ∈ I implies −a ∈ I), and such that for any a ∈ I and r ∈ R we have ar ∈ I. For example, multiples of a given integer m form an ideal mℤ ⊂ ℤ; functions that equal 0 at a given point form an ideal in the ring of continuous functions.

The quotient ring R/I is the set of equivalence classes with respect to the equivalence relation: a ∼ b if and only if a − b ∈ I. R/I is indeed a ring with addition and multiplication defined by

(a + I) + (b + I) = a + b + I, (a + I)(b + I) = ab + I.

The fact that I is an ideal ensures these operations are well defined, that is, the result does not depend on the choice of a representative in the equivalence class. Applying this construction to the ideal mℤ ⊂ ℤ we get the ring ℤ/m.

Exercise: show that the quotient of the ring of continuous functions by the ideal of functions vanishing at some point x_{0} is isomorphic to ℝ. Hint: consider the map f ↦ f(x_{0}).

An element r ∈ R is invertible if there exists s ∈ R such that rs = 1. A ring where every non-zero element is invertible is called a field. Examples of fields: ℚ, ℝ, ℂ, ℤ/p, where p is prime (the last statement follows from the fact that any integer not divisible by p is invertible mod p). The set of invertible elements of R is denoted by R^{∗}. It satisfies all the group axioms, including the existence of the inverse element, hence R^{∗} is a group (under multiplication). Thus R is a field if and only if R^{∗} = R \ {0}. The ring ℤ is not a field: indeed, ℤ^{∗} = {±1}.

Exercise: Prove that

(a) the invertible elements in the ring of polynomials are constants;

(b) the invertible elements in the ring of continuous functions are functions ℝ → ℝ^{∗}.

Let m_{1}, …, m_{k} ∈ ℤ_{>0} such that hcf(m_{i}, m_{j}) = 1 if i ≠ j. The Chinese remainder theorem says that the map

n + m_{1} … m_{k}ℤ ↦ (n + m_{1}ℤ, …, n + m_{k}ℤ)

is an isomorphism of ℤ/m_{1} … m_{k} with the product of rings ℤ/m_{1} × … × ℤ/m_{k}. The groups of invertible elements in isomorphic rings are isomorphic, hence the group (ℤ/m_{1} … m_{k})^{∗} is isomorphic to the product of groups (ℤ/m_{1})^{∗} × … × (ℤ/m_{k})^{∗}.

The group (ℤ/m)^{∗} may or may not be cyclic, that is, generated by one element. An integer that gives a generator, when it exists, is called a primitive root mod m. The primitive root theorem says that (ℤ/m)^{∗} is cyclic precisely when m = 1, 2, 4, p^{k}, 2p^{k}, where p is an odd prime. In other words, for these m the group (ℤ/m)^{∗} is isomorphic to ℤ/φ(m). (The isomorphism sends a primitive root mod m to \overline{1}.) The most important particular case is the fundamental fact that the multiplicative group of the field in p elements is cyclic (i.e., (ℤ/p)^{∗} is isomorphic to ℤ/(p − 1)).

Exercise: If p is an odd prime prove that squares in (ℤ/p)^{∗} are a subgroup of order (p − 1)/2.

Exercise: Let a, b ∈ ℤ_{>0}. Show that ℤ/a × ℤ/b is cyclic if and only if hcf(a, b) = 1. Hint: ℤ/a × ℤ/b is cyclic if and only if it has a generator, that is, an element of order ab.

Exercise: Show that any subgroup of a cyclic group is cyclic.