An advantage of this purely formal point of view is that invertibility of formal power series does not depend on convergence. Moreover, certain properties of the ring R can directly be transferred to the ring of formal power series RX.

Theorem 1.40. The following properties transfer from R to RX:

Proof: (a) If R has a zero divisor, then so does RX because R is a subring. Nowlet R be an integral domain and f = (a0, a1, . . . ) and g = (b0, b1, . . . ) be two elements of R X{0}. Let ai be the first nonzero coefficient of f and b j the first nonzero coefficient of g. Then, f ⋅ g = (c0, c1, . . . ) with

In particular, f ⋅ g is not the zero polynomial. Thus, RX is an integral domain.

(b)If f is invertible, so must be f(0) since (f ⋅ g)(0) = f(0) ⋅ g(0). For the converse, let f = (a0, a1, . . . ) and assume that f(0) = a0 ∈ R is invertible. Define b0 by a0 ⋅ b0 = 1. Now, let k ≥ 1 and (b0, . . . , bk−1) be already defined. Then define bk by

Then, we obtain a formal power series g = (b0, b1, . . . ) in the ring RX with the property (f ⋅ g) = 1 = (1, 0, 0, . . . ).

□

Example 1.41. The inverse of the formal power series Σi≥0 X i is 1 − X.

◊

Theorem 1.42 (Degree formula). Let f, g ∈ R[X]. Then, we have

Proof: These statements are true if f = 0 or g = 0. Thus, we can assume that

The first statement follows from The product of f and g has the form Thus, deg(fg) ≤ deg(f) + deg(g). If an or bm is not a zero divisor, then anbm ≠ 0 and thus deg(fg) = deg(f) + deg(g).

□

Remember that each integer i can be interpreted as an element of R by i-fold summation of 1 ∈ R. The derivative of a formal power series f(X) = Σi≥0 aiXi is defined by

Theorem 1.43. For derivatives, the following rules hold:

Proof: Let f = Σi≥0 aiXi and g = Σi≥0 biXi. Then:

□

Similar to Theorem 1.43, one can give an abstract proof for the derivation rules of and f(g(X)), provided that the expressions are defined over the formal power series.

Theorem 1.44. Let g ∈ R[X] {0} such that its leading coefficient is invertible in the ring R. For every f ∈ R[X], there are unique polynomials q, r ∈ R[X] with

Proof: We show the existence and uniqueness of q and r by induction on deg(f). If deg(f) < deg(g), then q = 0 and r = f is necessary and sufficient. Now let f(X) = and deg(f) = n ≥ m = deg(g). Consider the polynomial , where bm is the leading coefficient of g. Its degree is n and the coefficient of X n is an. Therefore, the degree of is less than n. For all polynomials q and r, the following two equations are equivalent:

By the induction hypothesis, there are unique polynomials q̂ and r̂ with f̂ = q̂g + r̂ and deg(r̂ ) < m. The identity f(X) = q(X) ⋅ g(X) + r(X) with deg(r) < m holds if and only if and r(X) = r(̂ X).

□

The proof of Theorem 1.44 provides an algorithm for the division of polynomials with remainder, called polynomial division. In the following example, let R = ℤ/4ℤ. Similar to the classical method for integer division, we demonstrate the method on polynomials f(X) = X5 + 2X3 + 3X and g(X) = 3X2 + 2X + 1 from R[X]

For arbitrary rings R – including polynomial rings – we write s | t if the element s ∈ R divides the element t ∈ R, that is, if r ∈ R exists with rs = t. For f, g, r ∈ R[X], we write f mod g = r if deg(r) < deg(g) and there is a polynomial q ∈ R[X] satisfying f = qg + r. In fields, using this notation we can apply the (extended) Euclidean algorithm on two polynomials f and g. Analogous to Theorem 1.32, we obtain the following statement.

Theorem 1.45. Let F be a field. Then every ideal in F[X] is principal. If t, t' ∈ F[X] generate the same ideal, then there exists a ∈ F ∗ with t' = at.

Proof: Let I ⊆ F[X] be an ideal different from {0}, and t ∈ I a polynomial of minimum degree in I {0}. For each f ∈ I, by Theorem 1.44 there is a representation f = qt+r with deg(r) < deg(t). From r = f − qt ∈ I, we obtain r = 0, and thus any polynomial f ∈ I belongs to the principal ideal generated by t. Now let t, t' ∈ F[X] be two polynomials generating the same principal ideal I. If t = 0, then necessarily t' = 0 also holds. So, let t ≠ 0 ≠ t. After a scalar multiplication with an appropriate a ∈ F ∗, we can assume that t and t' have the same leading coefficient. Then, t − t' ∈ I on the one hand has a smaller degree than t, and on the other hand t − t' = qt for a polynomial q ∈ F[X]. This yields t = t' and the claim follows.

□

Corollary 1.46. Let F be a field and f, g ∈ F[X] with f ≠ 0. Then there exists a unique polynomial t ∈ F[X] having the following three properties:

Proof: From Theorem 1.45, we see that the ideal generated by f and g is a principal ideal and is generated by a polynomial t. Because of f ≠ 0, also t ≠ 0; and using a scalar multiplication we can assume that the leading coefficient of t is 1 ∈ F. This implies (a), since t is generated by f and g. Property (b) holds, since f and g are generated by t. The condition (c) is guaranteed by assumption, which also shows the uniqueness of t.

□

The polynomial t from Corollary 1.46 is a polynomial of maximum degree dividing f and g. Therefore, t is called the greatest common divisor gcd(f, g) of the polynomials f and g. Two polynomials are called coprime if their greatest common divisor is the polynomial 1. The next corollary shows that coprime polynomials f and g have no common roots, that is, there is no s ∈ R with f(s) = 0 = g(s).

Corollary 1.47. Let s ∈ R and f ∈ R[X]. Then

Proof: It is sufficient to show (b). Suppose that f(X) = q(X)(X − s) + a. Then, f(s) = q(s) ⋅ (s − s) + a = 0 + a = a. Now let f(s) = a. By Theorem 1.44 there are q, r ∈ R[X] with f(X) = q(X)(X − s)+ r(X) and deg(r) < deg(X − s) = 1. So, r ∈ R follows. Moreover, we obtain a = f(s) = q(s)(s − s) + r = 0 + r = r.

□

An element s ∈ R is called a root (or a zero) of the polynomial f ∈ R[X] if f(s) = 0. The multiplicity of a root s ∈ R of a polynomial f ∈ R[X] {0} is the maximum n ∈ ℕ such that (X − s)n | f . Corollary 1.47 states that the multiplicity of a root is always at least 1. A root is called simple if its multiplicity is 1; otherwise a root is called multiple.

The following theorem shows that, for integral domains, the degree of a polynomials is an upper bound for the number of roots. In general, this is not true. Consider the polynomial f(X) = X2 + X of degree 2 over the ring ℤ/6ℤ. The four roots of this polynomial are 0, 2, 3 and 5. This results in two factorizations f(X) = X(X + 1) and f(X) = X2 + X = X2 − 5X + 6 = (X − 2)(X − 3). All elements of ℤ/6ℤ are roots of the polynomial g(X) = X 3 − X. In particular, for arbitrary rings the degree does not give a bound on the number of roots.

Theorem 1.48. Let R be an integral domain. The number of roots of a polynomial f ∈ R[X] with f ≠ 0 is at most deg(f). This is still true if multiple roots are counted according to their multiplicity.

Proof: If s1 ∈ R is a root of f , then by Corollary 1.47, we first have f(X) = (X − s1)q1(X) for a polynomial q1(X) ∈ R[X] with deg(q1) = deg(f)−1. If s2 ∈ R is a root of q1(X), we obtain f(X) = (X − s1)(X − s2)q2(X) for q2(X) ∈ R[X] with deg(q2) = deg(f) − 2. Here, s1 = s2 can possibly hold. We continue this decomposition procedure for f until

for qm(X) ∈ R[X] with deg(qm) = deg(f) − m ≥ 0 such that qm has no roots in R. If f(s) = 0 for some arbitrary root s ∈ R, then, because R has no zero divisors, at least one of the factors (s − si) has to be zero. This shows that the elements s1, . . . , sm with m ≤ deg(f) are the only roots of f .

□

The following lemma provides a relationship between the derivative of a polynomial and the simplicity of roots.

Proposition 1.49. Let R be an integral domain and f ∈ R[X] with f ≠ 0. A root s ∈ R of f is simple if and only if f (s) ≠ 0.

Proof: If s has at least a multiplicity of 2, then (X − s)2 divides f . By the rule for the derivatives of products given in Theorem 1.43, the polynomial (X − s) divides f' (X) and therefore f' (s) = 0. Suppose that s is a simple root. Then, f can be written as f(X) = (X − s) ⋅ g(X). Now g(s) ≠ 0 because otherwise (X − s) would divide g and thus (X − s)2 would divide f. The derivative of f is f' (X) = g(X) + (X − s) ⋅ g'(X). Thus, we have f' (s) = g(s) + 0 ⋅ g'(s) = g(s) ≠ 0.

□

From Corollary 1.47 and Proposition 1.49, we obtain the following statement:

Corollary 1.50. Let F be a field and f ∈ F[X]. If f and f' are coprime, then all roots of f are simple roots.

□

Let f ∈ R[X] and 〈f〉, the ideal f ⋅ R[X] generated by f . For the quotient ring R[X]/〈f〉, we write R[X]/f for short. If we write a ≡ b mod f , this means a + 〈f〉 = b + 〈f〉 in R[X]/f .

Let F be a field. A nonconstant polynomial f ∈ F[X] is called irreducible if f cannot be written as the product of two polynomials of strictly lower degree. In particular, any linear polynomial X −a is irreducible. From Theorem 1.42 (c) and Corollary 1.47 ,we can directly conclude that a polynomial of degree 2 or 3 is irreducible if and only if it has no roots.

Theorem 1.51. Let F be a field and f ∈ F[X]. Then, F[X]/f is a field if and only if f is irreducible.

Proof: First, let f be irreducible and let g ∈ F[X] 〈f〉. Then f and g are coprime. By Corollary 1.46, there exist polynomials a, b ∈ F[X] such that af + bg = 1. Now bg ≡ 1 mod f . Therefore, in F[X]/f every nonzero residue class is invertible, which means that F[X]/f is a field. Note that since deg(f) > 0, the ring F[X]/f is not zero.

For the converse, let f be not irreducible, that is, f is constant or a product of polynomials of smaller degree. First, suppose that f is constant. In the case of f = 0, the quotient F[X]/0 is isomorphic to F[X] and the latter is not a field since polynomials having roots cannot be inverted. If f is a nonzero constant, then F[X]/f is the zero ring and thus not a field. If the polynomial f can be written as a product of two polynomials of strictly smaller degree, f = gh, then g ≢ 0 mod f and h ≢ 0 mod f but gh ≡ 0 mod f . Thus F[X]/f contains zero divisors and therefore is not a field.

□

Next, we examine the size of F[X]/f .

Theorem 1.52. Let F be a field and f ∈ F[X] {0}. Then, F[X]/f as an additive group is isomorphic to F deg(f).

Proof: Let d = deg(f) and Fd = { g ∈ F[X] | deg(g) < d }. As an additive group Fd is isomorphic to F d since a polynomial of degree less than d is defined by the sequence of coefficients (a0, . . . , ad−1) ∈ Fd. The homomorphism g ↦ g mod f from Fd to F[X]/f is surjective because, by Theorem 1.44, the residue classes of F[X]/f have representatives of degree less than d. It is injective since g = g mod f for all g ∈ F d. This proves the theorem.

□

Example 1.53. Let F = ℤ/2ℤand f = X3+X+1 ∈ F[X]. In F[X]/f, we have f ≡ 0 mod f . Since −1 = +1 holds in F, this is equivalent to X3 ≡ X + 1 mod f . This allows us to reduce exponents i ≥ 3 in Xi. For example, we obtain

Since deg(f) = 3 and f(r) ≠ 0 for all r ∈ F, f is irreducible in F[X]. Using Theorems 1.51 and 1.52, we finally see that F[X]/f is a field with eight elements.

◊

Example 1.54. The Advanced Encryption Standard (AES) works with the irreducible polynomial X8 + X4 + X3 + X +1 of degree 8 over F = ℤ/2ℤ. Here, all computations are done in the field F[X]/(X8 + X 4 + X3 + X +1). This field contains 256 elements that can be represented by 1 byte each, the ith bit being the coefficient of Xi for 0 ≤ i ≤ 7. The addition operation is the bitwise exclusive-or of 2 bytes and the multiplication rule follows directly from the polynomial representation given above.

◊

1.7 Hilbert’s basis theorem

A commutative ring R is called Noetherian if each ideal is generated by a finite set. The term refers to Emmy Noether who was a student of Hilbert and the first female university professor for mathematics in Germany. Hilbert’s basis theorem states that polynomial rings over Noetherian rings are Noetherian themselves. It formed the basis for the rapid development of algebraic geometry in the 20th century. We will restrict our considerations to commutative rings throughout this section.

Every field F is a Noetherian ring since the only two ideals {0} and F require at most one generating element. The ring ℤ is Noetherian since, according to Theorem 1.32, every ideal is principal. By Theorem 1.45, also every ideal of the polynomial ring F[X] in one variable X over a field F is principal; therefore F[X] is Noetherian, too. In the polynomial ring ℂ[X, Y] in two variables, the ideal 〈X, Y〉 is not principal because if f(X, Y) is supposed to generate the polynomial X, then Y must not occur in f(X, Y). But then the polynomial Y cannot be generated by f(X, Y). As we shall see, ℂ[X, Y] is Noetherian. Generally, the polynomial ring R[X1, . . . , Xn] in n variables is defined inductively as R[X1, . . . , Xn] = R[Xn] for R' = R[X1, . . . , Xn−1].

Theorem 1.55 (Hilbert’s basis theorem). Let n ∈ ℕand R be aNoetherian commutative ring. Then the polynomial ring R[X1, . . . , Xn] is Noetherian.

Proof: Since R[X1, . . . , Xn] = R[Xn] for R' = R[X1, . . . , Xn−1], it suffices to show the theorem for the polynomial ring R[X] in one variable. Let I ⊆ R[X] be an ideal. For f ∈ I, let ℓf be the leading coefficient of f. For f, g ∈ I, both ℓf + ℓg and ℓf − ℓg are the leading coefficients of polynomials of degree at most max{deg(f), deg(g)} in I. The set { ℓf | f ∈ I } is an ideal in R. So, there is a finite set of polynomials B' ⊆ I such that

Let d = max{ deg(b) | b ∈ B' }. For every, e < d the set { ℓf | f ∈ I, deg(f) ≤ e } is an ideal in R. Thus there is a finite set Be ⊆ I satisfying

We let B = B' ∪⋃e<d Be. For each f ∈ I, there exists g ∈ 〈B〉 with deg(f) = deg(g) and ℓf = ℓg. By induction on the degree, we have f − g ∈ 〈B〉. This yields f ∈ 〈B〉 and I is generated by the finite set B.

□

A typical application of Hilbert’s basis theorem is the following situation. Let F be a field and N ⊆ Fn be the set of roots of polynomials ⊆ F[X1, . . . , Xn]. That is

Then, N is already the set of roots of a finite subset B ⊆ because N is the set of roots of 〈〉. According to Hilbert’s basis theorem, it is sufficient to have a finite “basis” B' ⊆ 〈〉. If each element of B' is generated by elements from , these generators from F provide the desired subset B.

1.8 Fields

Throughout this section, F is a field and char(F) its characteristic. If char(F) = 0, then F contains the rational numbers ℚas its prime field. For char(F) ≠ 0, the characteristic is a prime number p and F contains the finite field ℤ/pℤ as its prime field, which we also denote by p. One also frequently runs across the expression GF(p) for p. Here, GF stands for Galois field. The multiplicative group of finite fields is always cyclic. The same holds for all finite multiplicative subgroups of the complex numbers. This follows from the next theorem.

Theorem 1.56. Every finite subgroup of the multiplicative group F ∗ is cyclic.

Proof: Let U be a finite subgroup of F ∗ with order n. Let d1, . . . , dn be the orders of the elements of U and d = lcm(d1, . . . , dn). Each of the n elements of U is a root of the polynomial X d − 1. From Theorem 1.48, we obtain d ≥ n because a polynomial of degree d cannot have more than d roots. Since di | n for all i, we have d | n and thus d = n. In U, there exists an element α of order d. This can be seen as follows. Let u1 and u2 be elements of orders d1 and d2, respectively. There exist powers and of u1 and u2, respectively, such that their orders and are coprime and satisfy lcm By Theorem 1.8, the order of is lcm(d1, d2). From d = n we now obtain 〈α〉 = U.

□

Corollary 1.57. Let U ⊆ F ∗ be a finite multiplicative subgroup with at least two elements. Then, Σu∈U u = 0.

Proof: Let n be the order of U and g be a generating element. Since n ≥ 2, we have g ≠ 1. Moreover

and therefore The result follows since { gi | 0 ≤ i < n} = U.

□

A field extension E of F is a field that contains F as a subfield. We want to show that, to each polynomial f ∈ F[X], there is a field extension E such that f can be decomposed into linear factors in E [X], that is, E contains (not necessarily different) elements β, α1, . . . , αd such that d = deg(f) and in E[X]. Here, β ∈ F is the leading coefficient of f . In particular, for finite fields F, the field extension E and the elements αi ∈ E can effectively be determined. We call the field E a splitting field of f over F.

Theorem 1.58. Let f ∈ F[X] with leading coefficient β. Then there is a field extension E and α1, . . . , αd ∈ E with d = deg(f) such that din E[X]. If F is finite, then we can assume E to be finite.

Proof: If d ≤ 1, there is nothing to do since f already has the desired form. So, let d > 1. If f is not irreducible, then f can be decomposed into a product f = gh with deg(g) < d and deg(h) < d. The statement is now obtained by induction. First, let E' be the splitting field of g over F. We then construct the splitting field E of h over E' .

□

Finally, let f be irreducible. Then, E' = F[X]/f is a field by Theorem 1.51. From the finiteness of F, together with Theorem 1.52, we conclude that E ' is finite, too. After renaming the variable X to α, we can write E' ' = F [α]/f(α) and use X again as the name of a variable. In E', by construction we have f(α) = 0. Thus, α is a root and f ∈ E'[X] can be decomposed into f(X) = (X − α)g(X), where deg(g) < d. Note that the leading coefficient of g is β. Inductively, for g and E' there is a field extension E where g splits into linear factors. Thus, over E [X] we obtain

where the leading coefficient of f is still β ∈ F. Substituting αd = α, we obtain the desired result

□

A field E is algebraically closed if every nonzero polynomial f(X) ∈ E [X] admits a factorization for β, αi ∈ E. Applying Theorem 1.58 “infinitely often” to a field F and all polynomials over this field leads to the so-called algebraic closure of F. By construction, the algebraic closure of F is algebraically closed. The formal proof for the existence of the algebraic closure is based on the axiom of choice. Furthermore, one can show that the algebraic closure of a field is unique up to isomorphism; this means that all minimal field extensions of F where every polynomial splits into linear factors are isomorphic. The algebraic closure of a field F is always infinite, even if F itself is finite. The complex numbers ℂ are the algebraic closure of the field of real numbers ℝ but not of the rational numbers ℚ because, among others, the number π is not in the algebraic closure of ℚ.

Let n ≥ 1 and G ⊆ ℂ be the set of roots of the polynomial X n − 1 over the complex numbers ℂ. Since the polynomial X n − 1 and its derivative nXn−1 are coprime, Xn − 1 has n different roots. These roots form a finite subgroup of ℂ∗. By Theorem 1.56, the group G is cyclic of order n. This shows that every cyclic group can be found as a subgroup of ℂ∗. We now want to examine the situation in arbitrary fields.

Theorem 1.59. Let n ≥ 1 be an integer with char(F) ∤ n. Then there is a field extension E of F and an element α ∈ E ∗ of order n such that

We call α a primitive root of unity of order n.

Proof: We already know that f(X) = Xn − 1 splits into linear factors in an appropriate field extension E. The roots of f(X) form a finite subgroup of E ∗ consisting of at most n elements. By Theorem 1.56, this subgroup is cyclic. Furthermore, we have f' (X) = nXn−1. Since char(F) does not divide n, we have f' (α) ≠ 0 for all α ∈ E∗. Since f(0) ≠ 0, all roots of X n − 1 are simple. Thus, they are pairwise distinct and the cyclic subgroup is generated by an element α of order n.

□

1.9 Finite fields

A special case of Theorem 1.56 shows that the multiplicative group of finite fields is always cyclic. This fact is of central importance for the study of finite fields.

Every field is a vector space over its prime field. In particular, a finite field F is a finite-dimensional vector space over its prime field p for a prime number p. If the dimension is n, then F contains exactly pn elements. We state this property in the following theorem and give an alternative proof that does not require linear algebra, but uses Cauchy’s theorem instead.

Theorem 1.60. Let F be a finite field of characteristic p. Then there exists n ≥ 1 with |F| = pn.

Proof: By Lemma 1.26, the number p is prime. Then, in the additive group of F, all nonzero elements have order p. By Cauchy’s theorem (Theorem 1.9), for every prime divisor q of |F|, there is an element of order q. Thus, p is the only prime divisor of |F| and hence, |F| = pn for an appropriate exponent n ≥ 1.

□

Theorem 1.61. Let p be a prime number and n ≥ 1. Then there exists a field with pn elements.

Proof: Let q = pn and let E be a finite splitting field of f(X) = Xq − X over p. The field E exists by Theorem 1.58. The derivative of f is f' (X) = −1. Thus, f and f' ' are coprime and, by Corollary 1.50, all roots of f are simple. This shows that Xq − X has exactly q different roots in E. By Theorem 1.28, the n-fold application of the Frobenius automorphism yields an automorphism φ: E → E, x ↦ xq. The roots of f are those elements x which satisfy φ(x) = x. These elements form a field with pn elements.

□

Theorem 1.62. Let F and K be finite fields and |K| a power of |F|. Then, F is isomorphic to a subfield of K.

Proof: Let |F| = q = pn for a prime number p and n ≥ 1. By Theorem 1.56, both F ∗ and K ∗ are cyclic. First, let α be a generator of F ∗. Then, α is a root of the polynomial Xq−1−1 ∈ p[X]. Let f be a factor of Xq−1−1 with f(α) = 0 in F such that f is irreducible in p[X]. By Theorem 1.51, the quotient ring p[X]/f is a field. The homomorphism φ: p[X]/f → F, g(X) ↦ g(α) is well defined and thus surjective. Therefore, φ is an isomorphism by Corollary 1.24. Without loss of generality, we assume that F = p[X]/f in the remainder of the proof.

Since K contains qk elements for some k ≥ 1, its prime field is p. The cyclic group K ∗ contains qk−1 elements and thus it contains a cyclic subgroup of order q −1. Therefore, Xq−1 − 1 can be decomposed into linear factors over K, and f as a divisor of Xq−1 − 1 has a root β ∈ K. We now define a homomorphism ψ: Fp[X]/f → K, g(X) ↦ g(β). As a homomorphism of fields it is injective and thus F appears as an isomorphic subfield of K.

□

An immediate consequence of the previous theorem is that, up to isomorphism, every finite field is uniquely determined by its number of elements. This justifies the notation q or GF(q), respectively, for the field with q elements. By combining the results in this section, we obtain the following classification of finite fields.

Corollary 1.63. For every prime power q > 1, up to isomorphism there is a unique field q with q elements. Moreover, all finite fields are of this form.

Proof: By Theorem 1.61, there exists a field q with q elements. By Theorem 1.62, this field is unique up to isomorphism. Finally, by Theorem 1.60, there are no other finite fields.

□

Example 1.64. Let n ≥ 1. By Theorem 1.61, there is a field extension E over 2 with 2n elements and it can be written as E = 2[X]/f for an irreducible polynomial f(X) ∈ 2[X] of degree n. If we regard E as a vector space over 2, then the elements 1, X, . . . , Xn−1 from E are linearly independent. If we define αi = (0 ⋅⋅ ⋅ 010 ⋅⋅ ⋅ 0) with 1 at the (n − i)th position from the left, then Xi ↦ αi induces a bijection between E and the set n of 0 − 1 sequences of length n. Here, any polynomial of degree less than n is represented by the sequence of its coefficients. In particular, this yields the structure of a field on n.

Now let f(X) = X3 + X2 + 1 ∈ 2[X]. This polynomial has no roots in 2. Its degree is 3, so f is irreducible and E = 2[X]/f is a field with eight elements. The elements of E are the linear combinations of 1, X, X2 with coefficients from 2. The sequences of these coefficients result in a representation of E by 0 − 1 sequences of length 3. Multiplying such sequences, for example, we obtain

because (X2 + 1)(X2 + X + 1) ≡ 1 mod f in 2[X].

◊

1.10 Units modulo n

We have seen that the group of units (ℤ/nℤ)∗ is cyclic if n is prime. In this section, we want to describe the structure of the multiplicative group (ℤ/nℤ)∗ for prime powers n. The structure of (ℤ/nℤ)∗ for arbitrary numbers n can then be obtained using the Chinese remainder theorem. Considering the group G = (ℤ/8ℤ)∗, we can identify G with the odd numbers 1, 3, 5, 7. We have a2 = 1 for all a ∈ G. Particularly G, being of order 4, is not a cyclic group. We start with two technical lemmas.