□

By Corollary 1.17, we see that the definition of sgn is independent of the chosen order of elements in {1, . . . , n}, because the definition of a transposition is independent of this order. So, if X is a finite set and π a permutation of X, we can define sgn(π). In particular, considering a finite group G, we can start with any order of G’s elements and every order defines the same sign sgn(g) ∈ {1, −1} for g ∈ G; to see this, consider the permutation x ↦ gx on G induced by g.

Remark 1.19. The kernel of sgn: Sn → {1, −1} is the alternating group An on n elements. These are the permutations with sign 1. The elements of An are also called even permutations, while permutations of sign −1 are called odd permutations. Corollary 1.17 shows that the even permutations are those generated by an even number of transpositions. It is also noteworthy that all groups An for n ≥ 5 have no nontrivial normal subgroups. This property led to the insight that polynomial equations of degree 5 or higher generally cannot be resolved with so-called root expressions. The theorem is accordingly named after Ruffini and Abel and its discovery was the beginning of Galois theory.

◊

1.4 Rings

Historically, the common properties of different number systems such as the integers and the complex numbers were the main motivation for algebraic structures. Each of these structures has two operations, addition and multiplication, and there are certain connections between them. This led to the notion of a ring. Formally, a ring is given by a tuple (R, +, ⋅, 0, 1), where (R, +, 0) is an Abelian group and (R, ⋅, 1) a monoid such that multiplication distributes over addition

The latter is called the distributivity property. Weusuallywrite R instead of (R,+,⋅,0,1). Note that

and symmetrically r0 = 0, that is, 0 is a zero element for multiplication. The ring R is commutative if multiplication is commutative. The zero ring R = {0} is the only ring with 0 = 1. An element having a multiplicative inverse is a unit and R∗ = { r ∈ R | ∃s : rs = sr = 1 } is called the group of units or the multiplicative group of R. Note that 1 ∈ R∗. A skew field is a ring R with R∗ = R {0}, that is, all elements have a multiplicative inverse except for 0. A commutative skew field is called a field. The integers ℤ form a commutative ring and we have ℤ∗ = {1, −1}, that is, ℤ is not a field. For n > 1, the n × n matrices over ℤ form a noncommutative ring. The rationals ℚ, the reals ℝ, and the complex numbers ℂ are the fields.

Example 1.20. If R is a ring, then RR = { f : R → R | f is a mapping } forms a ring with pointwise addition and multiplication. Formally, for f, g ∈ RR the mappings f +g ∈ RR and f ⋅ g ∈ RR are defined by

Even if R is a field, RR is not a field.

◊

A subset I ⊆ R is an additive subgroup of R if (I, +, 0) is a subgroup of (R, +, 0). Multiplicative submonoids are defined similarly. A subset S of a ring R is a subring if it is both an additive subgroup and a multiplicative submonoid. In particular, every subring is a ring with the same 0 and 1. A subring S of a field R is called subfield if S itself is a field. An additive subgroup I ⊆ R satisfying R ⋅ I ⋅ R ⊆ I is called an ideal. An ideal can only be a subring if 1 belongs to I, but then we have I = R. The subsets {0} and R are the trivial ideals of R. We will see in Theorem 1.32 that all ideals in ℤ are of the form nℤ.

The set of additive cosets of I is R/I = {r + I | r ∈ R }. Since addition in R is commutative, R /I forms an Abelian group with addition

Let us define multiplication on R /I by

As the following computation shows, this definition is well defined:

The associativity of multiplication and the distributive property for R /I now follow from the corresponding properties in R. We call R/I the quotient ring of R modulo I. The elements of R /I are called residue classes or residues. We say r is congruent to s modulo I if r + I = s + I. In computations modulo I, we can switch back and forth between representatives and classes. Let X ⊆ I. If every element r ∈ I can be written as r = Σx∈X rxxsx with rx , sx ∈ R such that rx ≠ 0 ≠ sx for only finitely many x, then X generates I. If a finite generating set exists, then the ideal is called finitely generated. An ideal I is principal if it is generated by a single element, that is, if I = RrR for some r ∈ R. In ℤ, every ideal is principal because it is generated by the greatest common divisor of all its elements; see Theorem 1.32.

A mapping φ: R → S between rings R and S is called a (ring) homomorphism if the following conditions hold for all x, y ∈ R:

The first property means that φ is a group homomorphism with respect to addition. This also implies φ(0) = 0. The last two properties guarantee that φ is a monoid homomorphism with respect to multiplication. In particular, (c) does not follow from(b). A bijective ring homomorphism is a ring isomorphism because, due to bijectivity, the inverse mapping is a homomorphism, too. If I ⊆ R is an ideal, then R → R /I, r ↦ r + I defines a ring homomorphism.

Let φ: R → S be a ring homomorphism. Its kernel is the ideal ker(φ) = { r ∈ R | φ(r) = 0 }. The image of φ is the subring im(φ) = { φ(r) | r ∈ R } of S. Unlike im(φ), the ideal ker(φ) is not a subring unless im(φ) = {0}. In analogy to Theorem 1.10, one can show that I is an ideal if and only if I is the kernel of a ring homomorphism φ: R → S; see Exercise 1.24.

Example 1.21. Let R be a ring and r ∈ R. Then the mapping φ: RR → R, f ↦ f(r) is a ring homomorphism. Its kernel is ker(φ) = { f : R → R | f(r) = 0 }. The mappings with a zero at r form an ideal in RR.

◊

Example 1.22. Consider the derivative operator

We have (f +g)' = f ' +g, that is, D is a group homomorphism with respect to addition. On the other hand, ker(D) = {f | f is a constant mapping } is not an ideal. Therefore, D is not a ring homomorphism.

◊

The following theorem is analogous to the homomorphism theorem for groups.

Theorem 1.23 (Homomorphism theorem for rings). Let φ: R → S be a ring homomorphism. Then, φ induces the ring isomorphism

Proof: The set φ(r+ker(φ)) has only one element, namely φ(r). Therefore, r+ker(φ) ↦ φ(r) defines a ring homomorphism. From Theorem1.12, it follows that it is a bijection, and bijective ring homomorphisms are isomorphisms.

□

An easy consequence of the homomorphism theorem for rings is that homomorphisms of finite fields into themselves are bijective. We show a more general statement.

Corollary 1.24. Ring homomorphisms from a field into a ring with 0 ≠ 1 are injective. In particular, all homomorphisms between fields are injective.

Proof: Let φ be a homomorphism and suppose that φ(z) = 0 for z ≠ 0. Then, 1 = φ(1) = φ(z−1z) = φ(z−1) ⋅ φ(z) = φ(z−1) ⋅ 0 = 0, contradicting the assumption. Thus ker(φ) = {0}, and the homomorphism theorem for rings 1.23 yields injectivity.

□

An ideal M ⊆ R is maximal if M ≠ R and there is no ideal I with M ⊊ I ⊊ R. Note that R itself is an ideal. Thus, the “largest” ideal R is not maximal in R.

Theorem 1.25. An ideal M ⊆ R in a commutative ring R is maximal if and only if R/M is a field.

Proof: Let M ⊆ R be maximal and x + M ∈ R/M a residue class with x ∉ M. We show that x +M is invertible in R /M. Note that M + xR is an ideal. Since M is maximal and x ∉ M, it follows that M + xR = R. Then, 1 can be written as 1 = m + xy for m ∈ M and y ∈ R. The product xy is congruent to 1 modulo M and thus y + M is the multiplicative inverse. This shows that each class x + M in R /M, except the zero element M, is invertible. Consequently, R /M is a field.

Now for the converse, let R/M be a field. Then 1 ∉ M, because 0 ≠ 1 in all fields. Let I ⊆ R be an ideal with M ⊊ I, and consider x ∈ I M. Then x +M ≠ 0 + M and since R/M is a field, there is r ∈ R such that (x + M) ⋅ (r + M) = 1 + M. Then 1 + M = xr + M; therefore R = R + M = xR + M ⊆ I because I is an ideal containing both xR and M. This shows I = R, so M is maximal.

□

An element r of a ring R is a zero divisor if there exists s ∈ R {0} with rs = 0 or sr = 0. For example, in the ring ℤ/6ℤthenumbers 2 and 3 are zero divisors. Invertible elements cannot be zero divisors. A ring is a domain if 0 is the only zero divisor. By this definition, in domains we always have 0 ≠ 1. An integral domain is a commutative domain.

For an integer k ∈ ℤand a ring (R, +, ⋅, 0R, 1R), we define

We therefore write k ∈ R, meaning the element k ⋅1R. In this notation, for 0, 1 ∈ ℤ, we have 0 = 0R ∈ R and 1 = 1R ∈ R. Two cases are possible. Either all positive integers in R are different from zero or there is a smallest positive number n with n = 0 in R. In the first case, we say that R has characteristic 0; in the second case, the characteristic is n with n > 0. In any case, we denote the characteristic of R by char(R). The ideal char(R)⋅ℤ is the kernel of the homomorphism ℤ→ R, k ↦ k⋅1R. The homomorphism theorem for rings 1.23 shows that ℤ/char(R)ℤ is isomorphic to a subring of R. Every subring S of R has the same characteristic as R.

Lemma 1.26. Let R be a domain. Then, either char(R) = 0 or char(R) is prime.

Proof: Suppose that char(R) = mn with m, n > 1. Since mn = 0 and m ≠ 0 ≠ n in R, both m and n are zero divisors in R.

□

Fields have no zero divisors and therefore their characteristic is either zero or a prime number. Fields of characteristic zero contain ℤ as a subring, and since all s ≠ 0 are invertible, fractions are elements of the field for all r, s ∈ ℤ with s ≠ 0. Thus, these fields contain the rational numbers ℚ as uniquely determined subfield. Other examples for fields of characteristic zero are ℝ, ℂ or . All fields of characteristic p for prime number p contain ℤ/pℤ. Therefore, the fields ℚ and ℤ/pℤ are minimal with respect to set inclusion; they are called prime fields.

The binomial coefficient for x ∈ ℂand k ∈ ℤis defined as follows:

For k ≥ 0, we have exactly k factors in both the numerator and the denominator; in particular, for k = 0 both products are empty and thus evaluate to the neutral element 1. For n, k ∈ ℕ, we obtain . For all x ∈ ℂ and k ∈ ℤ, the following addition theorem holds:

This can be seen as follows. For k < 0, both sides are 0, whereas for k = 0, both sides evaluate to 1. Now let k > 0. Then, For n ∈ ℕ, we have Now by induction, using the addition theorem, we see that the binomial coefficient is an integer for all n, k ∈ ℕ. In particular, the binomial coefficients for n ∈ ℕ and k ∈ ℤ can be interpreted as multiples of the neutral element 1R in any ring R.

Theorem 1.27 (Binomial theorem). Let R be a commutative ring. For all x, y ∈ R andall n ∈ ℕ, we have

Proof: The sum on the right-hand side runs over all k ∈ ℤ, but almost all of these summands are zero. This convention is often helpful, because index shifts are made much easier. The proof is by induction on n. For n = 0, both sides reduce to the neutral element 1R. Now let n > 0. Then

□

The binomial theorem is an important tool for the consideration of mappings r ↦ rp in commutative rings.

Theorem 1.28. Let R be a commutative ring with prime characteristic p. Then, r → rp defines a ring homomorphism.

Proof: Clearly, 1p = 1 and(rs)p = rp sp. It remains to show that (r+s)p = rp+sp. Bythe binomial theorem All binomial coefficients for 1 ≤ k ≤ p−1 are divisible by p. Since the characteristic of R is p, all these binomial coefficients are zero in R and thus

□

The homomorphism in Theorem 1.28 is usually referred to as the Frobenius homomorphism named after Ferdinand Georg Frobenius (1849–1917). It is especially interesting for fields, because in this case it is, by Corollary 1.24, injective and thus, for finite fields, necessarily also bijective. As an application of Theorem 1.28 for R = ℤ/pℤ, we prove Fermat’s little theorem (named after Pierre de Fermat, 160?–1665). In particular, on prime fields ℤ/pℤ the Frobenius homomorphism is the identity.

Theorem 1.29 (Fermat’s little theorem). Let p be prime. Then, ap ≡ a mod p for all a ∈ ℤ.

Proof: It suffices to prove the claim for a ∈ ℕ. We proceed by induction on a. For a = 0, the statement is true. Now, (a + 1)p ≡ ap + 1p ≡ a + 1 mod p. The first congruence follows from Theorem 1.28 and the second from the induction hypothesis.

□

In particular, under the assumptions of Theorem 1.29, for all a ∈ ℤ which are invertible in ℤ/pℤ, we obtain ap−1 ≡ 1 mod p.

1.5 Modular arithmetic

Let us start with a quick repetition of the most basic terms. The greatest common divisor of two integers k and ℓ is denoted by gcd(k, ℓ); it is the largest natural number that divides both k and ℓ. The greatest common divisor of k and 0 is defined as the number |k|. Two numbers are coprime if their greatest common divisor is 1. For computations in the quotient ring ℤ/nℤ, for integers k, ℓ, and n the following notation is used:

It means that k + nℤ = ℓ + nℤ, that is, k and ℓ differ by a multiple of n. If this holds, we say that k is congruent to ℓ modulo n; the integer n is called modulus. By k mod n, we denote the unique number r ∈ {0, . . . , |n| − 1} satisfying k ≡ r mod n. Frequently, k mod n is taken as representative of the residue class k + nℤ. By (ℤ/nℤ)∗, we denote the group of units of the ring ℤ/nℤ. These are the residue classes that have a multiplicative inverse.

1.5.1 Euclidean algorithm

The Euclidean algorithm (Euclid of Alexandria, around 300 BC) is an efficient method for computing the greatest common divisor. Since gcd(k, ℓ) = gcd(−k, ℓ) = gcd(ℓ, k), it suffices to consider natural numbers 0 < k ≤ ℓ. Let ℓ = qk + r for 0 ≤ r < k. The integer r is called the remainder and we have r = ℓ mod k. Each number dividing k and the remainder r also divides the sum ℓ = qk + r. Each number dividing k and ℓ also divides the difference r = ℓ − qk. This yields a recursive version of the Euclidean algorithm

If k ≤ ℓ, then after two recursive calls, the smaller parameter is less than k/2. In particular, the recursion depth is in (log k).

The next theorem is often named after Étienne Bézout (1730–1783) who showed a corresponding statement for polynomials.

Theorem 1.30 (Bézout’s lemma). Let k, ℓ ∈ ℤ. Then there exist a, b ∈ ℤ such that:

Proof: We may assume that ℓ > k > 0, all other cases are either trivial or can be reduced to this case. Let r0 = ℓ and r1 = k. The Euclidean algorithm successively computes remainders r0 > r1 > r2 ⋅⋅ ⋅ > rn > rn+1 = 0 satisfying

for appropriate qi ∈ ℕ. It follows gcd(k, ℓ) = gcd(ri+1, ri) = gcd(0, rn) = rn. We now show that for all i ∈ {0, . . . , n} there are integers ai and bi such that ai ri+1 + bi ri = rn. For i = n, we can set an = 0 and bn = 1. Let now i < n and ai+1 and bi+1 already defined, that is ai+1ri+2 + bi+1ri+1 = rn. With ri+2 = ri − qi+1ri+1, we obtain (bi+1 − ai+1qi+1)ri+1 + ai+1ri = rn. Thus, ai = bi+1 − ai+1qi+1 and bi = ai+1 have the desired property.

□

The proof presented above yields the following procedure: the extended Euclidean algorithm computes gcd(k, ℓ) and, additionally, two numbers a and b with the property ak + bℓ = gcd(k, ℓ).

Let n ∈ ℕ. For each number k that is coprime to n, the extended Euclidean algorithmprovides two integers a, b with ak +bn = 1. Modulo n, we obtain ak ≡ 1 mod n. Thus, a is a multiplicative inverse of k. We have a closer look at (ℤ/nℤ)∗, the invertible elements of ℤ/nℤ, in the following theorem:

Theorem 1.31. Let n ∈ ℕ. Then the following statements hold:

Proof: (a) We have k ∈ (ℤ/nℤ)∗ if and only if 1 can be written in the form 1 = kℓ+mn. By Theorem 1.30, this is equivalent to gcd(k, n) = 1.

(b)The ring ℤ/nℤ is a field if and only if all nonzero elements are invertible. By (a) this means that all numbers from 1 to n −1 are coprime to n. This in turn is equivalent to primality.

(c)If gcd(k, n) = 1, then k is invertible in (ℤ/nℤ)∗. Hence, the multiplication with k has an inverse mapping, thereby showing that it is a bijective function. For the converse, suppose that x ↦ kx is surjective. Then, the element 1 has a preimage, and thus there exists x ∈ ℤ with kx ≡ 1 mod n. It follows kx + ℓn = 1 for some ℓ ∈ ℤ. This shows gcd(k, n) = 1.

□

1.5.2 Ideals in the integers

Ideals are a concept from algebra which also plays an important role in modular arithmetic. The interest in ideals of ℤ comes from the fact that divisibility in ℤ can be formulated in terms of subset relations of ideals. We have

From the following theorem, we obtain a converse of this statement: each subset relation of ideals in ℤ represents some divisibility of numbers.

Theorem 1.32. Let I be an ideal of ℤ. Then, there is a unique number n ∈ ℕsuch that I = nℤ. Here, n is the greatest common divisor of all numbers in I. Particularly,

Proof: If I = {0}, then n = 0 satisfies the assertion. Let now I ≠ {0}. For all a, b ∈ I, we can find p, q ∈ ℤwith gcd(a, b) = ap + bq. So, gcd(a, b) ∈ I if and only if a, b ∈ I. The claim now follows from the observation that the greatest common divisor of all numbers in I is the uniquely determined smallest positive number in I.

□

Actually, the proof of Theorem 1.32 shows that all ideals in a ring are generated by a single element as soon as division with the remainder is available. This, for example, is also the case in polynomial rings over fields; see Section 1.6. Another advantage of the algebraic point of view on modular arithmetic is that by using algebraic concepts one might find simpler formulations and new interpretations for certain interrelations and contexts.

If I and J are ideals of a ring R, then I ∩ J is an ideal, too. For k,ℓ ∈ ℤ by lcm(k, ℓ) ∈ ℕ, we denote the least common multiple of k and ℓ. A tight relation between lcm and gcd is given by lcm(k, ℓ) ⋅ gcd(k, ℓ) = |k| ⋅ |ℓ|.

Theorem 1.33.

Proof: Since kℤ ∩ ℓℤ is an ideal of ℤ, by Theorem 1.32, there exists n ∈ ℕ with kℤ∩ ℓℤ = nℤ. From nℤ ⊆ kℤ and nℤ ⊆ ℓℤ, we obtain k | n and ℓ | n. So, n is a common multiple of k and ℓ and thus n ≥ lcm(k, ℓ). Let t be any common multiple of k and ℓ. Then, tℤ ⊆ kℤ ∩ ℓℤ = nℤ and consequently n | t. This shows n ≤ lcm(k, ℓ) and therefore n is the least common multiple of k and ℓ.

□

1.5.3 Chinese remainder theorem

For coprime numbers k and ℓ, the quotient ring ℤ/kℓℤ can be decomposed into the components ℤ/kℤ and ℤ/ℓℤ. This is exactly what is stated by the Chinese remainder theorem. The most important part of the statement is the following lemma.

Lemma 1.34. For coprime numbers k, ℓ ∈ ℤ, the following mapping is surjective:

Furthermore, π induces a bijection between ℤ/kℓℤ and ℤ/kℤ×ℤ/ℓℤ by the mapping (x mod kℓ) ↦ (x mod k, x mod ℓ).

Proof: Consider (x+kℤ, y+ℓℤ). Since k and ℓ are coprime, there are numbers a, b ∈ ℤ with ak + bℓ = 1. Thus, bℓ ≡ 1 mod k and ak ≡ 1 mod ℓ. For x, y ∈ ℤ, we obtain the following properties of yak + xbℓ:

But then π(yak + xbℓ) = (x + kℤ, y + ℓℤ) and π is surjective. We have π(x) = π(x) for all x' ∈ x + kℓℤ, so (x mod kℓ) ↦ (x mod k, x mod ℓ) is well defined. Therefore, π induces a surjection of Z /kℓℤ onto ℤ/kℤ×ℤ/ℓℤ. Finally, we observe that both Z /kℓℤ and ℤ/kℤ×ℤ/ℓℤ have kℓ elements. Thus, the induced mapping is bijective.

□

If R1 and R 2 are rings, we can define a ring structure on the Cartesian product R1 × R 2 by component-wise addition and multiplication. More specifically, addition is defined by (x1, y1) + (x2, y2) = (x1 + x2, y1 + y2). The zero element is given by the pair (0, 0) ∈ R1 × R2. Similarly, multiplication is defined by (x1, y1) ⋅ (x2, y2) = (x1 ⋅ x2, y1 ⋅ y2) and the neutral element is (1, 1). This ring is called the direct product of R1 and R2.

In a somewhat more elementary form, the following theorem is originally due to Sun Tzu in the 3rd century. However, it was only published in 1247 by Qin Jiushao (ca. 1202–1261).

Theorem 1.35 (Chinese remainder theorem). Let k, ℓ ∈ ℤ be coprime. Then the following mapping defines an isomorphism of rings:

Proof: The mapping is compatible with addition and multiplication and corresponds to the bijective mapping from Lemma 1.34.

□

A consequence of the Chinese remainder theorem is that, for the coprime numbers k and ℓ, the multiplicative group (ℤ/kℓ)∗ is isomorphic to (ℤ/kℤ)∗ × (ℤ/ℓℤ)∗.

1.5.4 Euler’s totient function

In this section, we deal with the number of elements in (ℤ/nℤ)∗. To this end, we define Euler’s totient function φ(n) as

By Theorem 1.31, the function φ(n) counts the integers in the range from 1 to n which are coprime to n. Thus φ(1) = 1. The Chinese remainder theorem yields

for the coprime numbers k and ℓ. This is due to the fact that x + kℓℤ is invertible if and only if both x + kℤ and x + ℓℤ are invertible. To determine the value of the totient function for arbitrary numbers, we only have to find the value of φ(n) for the cases where n is a prime power pk. So, let p be prime and k ≥ 1.From the numbers1, . . . , pk exactly the pk−1 numbers p, 2p, . . . , pk are divisible by p and therefore not coprime to pk. The remaining pk − pk−1 numbers are coprime to pk. This shows

Hence, we can compute φ(n) for any number n as soon as we know its prime factorization. An important property of Euler’s totient function is due to the following generalization of Fermat’s little theorem.

Theorem 1.36 (Euler). If gcd(a, n) = 1, then aφ(n) ≡ 1 mod n.

Proof: This is an immediate consequence of Corollary 1.5 since a ∈ (ℤ/nℤ)∗ and φ(n) is the order of the group (ℤ/nℤ)∗.

In particular, we can determine the inverse of any element a ∈ (ℤ/nℤ)∗ by computing aφ(n)−1. We write Σd|n φ(d) for the sum over all φ(d) such that d is a positive divisor of n.

Theorem 1.37.

Proof: Consider the following set of n fractions:

By cancellation, we can write every fraction as for the coprime numbers k and d such that d | n. Hence, we obtain

Grouping the fractions by their denominator yields the following partition of N into disjoint sets:

Finally, |{ k/d | 0 ≤ k < d, gcd(k, d) = 1 }| = |{ k | 0 ≤ k < d, gcd(k, d) = 1 }| = φ(d) completes the proof.

□

The following theorem gives an important connection between group theory and modular arithmetic.

Theorem 1.38. Let G be a cyclic group of order n and d be a positive divisor of n. Then, G has φ(d) elements of order d.

Proof: Let g ∈ G be a generator. By ψ(d), we denote the number of elements of order d. Since the order of every element in G divides n, we have Σd|n ψ(d) = n. By Theorem 1.37, it suffices to show that ψ(d) ≥ φ(d) for every divisor d of n. Consider k ∈ {1, . . . , d − 1} with gcd(k, d) = 1. Let

We have Since n does not divide for i ∈ {1, . . . , d − 1}, we have for all i ∈ {1, . . . , d − 1}. Thus, the order of h is d. Every number k ∈ (ℤ/dℤ)∗ defines an element of order d such that different numbers define different group elements. This completes the proof of ψ(d) ≥ φ(d).

□

1.6 Polynomials and formal power series

Throughout this section, R is a commutative ring. A formal power series with coefficients in R is an infinite sequence (a0, a1, . . . ) where all ai are from R. A polynomial is a formal power series with ai = 0 for almost all i ∈ ℕ. As usual by almost all, we mean “all but finitely many.” The degree of a polynomial f = (a0, a1, . . . ) is denoted by deg(f) and it is the maximum index d ∈ ℕ with ad ≠ 0. The polynomial f with ai = 0 for all i ∈ ℕ is called the zero polynomial and we define its degree to be −∞. Polynomials of degree at most 0 are called constants; they are identified with the elements of R.We usually write a formal power series (a0, a1, . . . ) as a formal sum

Here, we read X as a formal symbol or as a variable. A polynomial can be written as a finite formal sum

If f is not the zero polynomial, wemay require that d = deg(f) and ad ≠ 0. In this case, we call ad the leading coefficient of the polynomial f(X). The leading coefficient of the zero polynomial is zero by definition. A formal power series (a0, a1, . . . ) can also be interpreted as a mapping ℕ → R with i ↦ ai. We denote the set of formal power series by RX and the set of polynomials by R[X]. The latter is called the polynomial ring over R. The set of formal power series RX is a ring

In this ring, the polynomials form a subring but not an ideal. A polynomial f ∈ R[X] can also be interpreted as a polynomial mapping f ̃ : R → R by substituting values for the variable X

The mapping f ↦ f ̃ is called the evaluation homomorphism. To simplify notation, we write f(r) instead of f ̃(r). The notation f(r) is extended to formal power series, provided that the value of the infinite series Σi≥0 ai ri is well defined in the ring R. This depends on the notion of convergence in R. In any case, for power series we have f(0) = a0. The mappings RX → R with f ↦ f(0) and R[X] → RR with f ↦ f̃ are ring homomorphisms, which in general, however, are not injective. If R is finite, then RR is also finite, whereas R[X] for R ≠ {0} is infinite.

If R is an infinite field, for example, R = ℚ or R = ℝ, then the polynomial mapping f ̃ corresponding to f can only be the constant zero function if all the coefficients of f are zero. In this case, we can therefore identify polynomials and polynomial mappings. Since very often polynomials are only considered over ℚ or ℝ, the distinction between polynomials and polynomial mappings might look artificial and unnecessary. But for finite fields it is necessary, as the following example shows.

Example 1.39. Let R = ℤ/2ℤ and f(X) = X2 + X ∈ R[X]. Then, f(X) has degree 2 and it is not the zero polynomial. But if f(X) is interpreted as the mapping f ̃ : ℤ/2ℤ → ℤ/2ℤ, r ↦ r2 + r, we find that f ̃ is the zero function since f(0) = f(1) = 0 for 0, 1 ∈ ℤ/2ℤ.

◊