tailieunhanh - Ebook A Concrete introduction to higher algebra (3/E): Part 2

Part 2 book “A Concrete introduction to higher algebra” has contents: Unique factorization, the fundamental theorem of algebra, congruences and the ch inese remainder theorem, fast polynomial multiplication, cyclic groups and cryptography, carmichael numbers, quadratic reciprocity, quadratic applications, and other contents. | Chapter 14 Unique Factorization In this chapter we show that every polynomial of degree >1 with coefficients in a field factors uniquely (in a sense to be defined) into a product of irreducible polynomials. To reach this result, we follow the same development as for natural numbers: the division theorem, Euclid’s Algorithm and Bezout’s Identity. A. Division Theorem Let p(x) = ad xd +. . .+a1 x+a0 be a polynomial with coefficients in a field F. Recall that if ad = 0, then d is the degree of p(x), and ad is called the leading coefficient of p(x). If p(x) has degree 0, and suppose it has r distinct roots a1 , . . . , ar . in F. We must show r 2, can you find a commutative ring R and a polynomial f (x) of degree 2 with at least n roots in R? (Try choosing R = Z/mZ with m a product of many distinct primes.) 12. Let F p = Z/pZ be the field of p elements, where p is an odd prime. Label the elements of F p as 0, 1, 2, . . ., p − 1 modulo p. Prove Wilson’s Theorem: (p − 1)! ≡ −1 (mod p) 14 Unique Factorization 299 as follows: observe that, by Fermat’s Theorem, the polynomial f (x) = x p−1 − 1 in F p [x] has 1, 2, . . . , p − 1 as roots. Apply the Root Theorem to get a complete factorization of x p−1 − 1 into linear factors, and then compare the constant term of the product of the factors with the constant term of f (x). 13. Let F p be the field of p elements with p an odd prime, as in the last exercise. Explain why the polynomial x2 − 1 in F p [x] has only the roots 1 and p − 1. Show then that every number a with 1 < a < p − 1 has an inverse modulo p that is not congruent to a modulo p. Using that observation, prove Wilson’s Theorem. B. Greatest Common Divisors With the Division Theorem in hand, we can obtain Euclid’s Algorithm and Bezout’s Identity for polynomials, just as we did for natural numbers in Chapter 3. Let f , g be in F[x] where F is a field. A polynomial p in F[x] is a greatest common divisor (.) of f and g if p divides f and p divides g, and any