The Division Algorithm for Polynomials Handout Monday March 5, 2012


 Amanda Wilcox
 6 years ago
 Views:
Transcription
1 The Division Algorithm for Polynomials Handout Monday March 5, 0 Let F be a field (such as R, Q, C, or F p for some prime p. This will allow us to divide by any nonzero scalar. (For some of the following, it is sufficient to choose a ring of constants; but in order for the Division Algorithm for Polynomials to hold, we need to be able to divide constants. For much of the following, you can pretend that F = R. Recall that a polynomial in x is an expression of the form f(x = a 0 + a x + a x + + a n x n where x is a symbol and a 0,a,...,a n F. We say that a k is the coefficient of x k, for k = 0,,,...,n. Let F[x] denote the set of all polynomials in x, with coefficients in F. (Thus, for example, R[x] is the set of polynomials in x with real coefficients. The zero polynomial, denoted by 0, is the polynomial whose coefficients are all zero. Two polynomials f(x and g(x are the same, denoted f(x = g(x, if their corresponding coefficients are the same; for example, x + 5x 3 = 5x 3 x + = x + 0x + 5x 3 = 0x 4 + 5x 3 + 0x x +. In particular, we write f(x = 0 if and only if all coefficients of f(x are zero, thus for example, x 0. If p(x = a 0 + a x + a x + + a n x n 0, the degree of p(x, denoted by degp(x, is the largest k such that a k 0. For example, deg ( x +5x 3 = 3, deg (x 0x =, deg ( 8 = 0. We define deg 0 = so that the following proposition holds universally for all polynomials f(x, g(x, with the obvious conventions for adding. Proposition. If f(x,g(x F[x] then deg ( f(xg(x = degf(x + degg(x. Proof. If either of the two polynomials f(x,g(x is zero, then f(xg(x = 0 and the desired equality holds, with both sides equal to by convention. We may therefore assume f(x and g(x are nonzero polynomials. Now f(x = a 0 + a x + a x + + a n x n ; g(x = b 0 + b x + b x + + b m x m where n = degf(x and m = deg g(x; in particular, a n 0 and b m 0. Thus f(xg(x = a 0 b 0 + (a 0 b + a b 0 x + + a n b m x n+m
2 where the last term is the unique term of highest degree in f(xg(x, with coefficient a n b m 0; thus deg ( f(xg(x = n + m = deg f(x + deg g(x. We say that f(x divides g(x in F[x], denoted f(x g(x, if g(x = m(xf(x for some m(x F[x]. The following is obviously analogous to the Division Algorithm for Integers. We omit the proof, which we take to be evident from the usual algorithm of long division. Theorem (Division Algorithm for Polynomials. Let f(x, d(x F[x] such that d(x 0. Then there exist unique polynomials q(x, r(x F[x] such that f(x = q(xd(x + r(x, degr(x < deg d(x. As usual unique means that there is only one pair of polynomials (q(x, r(x satisfying the conclusions of the theorem. We call q(x and r(x the quotient and remainder, respectively. Note that a(x b(x if and only if r(x = 0. Note that the Division Algorithm holds in F[x] for any field F; it does not hold in Z[x], the set of polynomials in x with integer coefficients. A zero or root of f(x is a number a such that f(a = 0. An important consequence of the Division Algorithm is the fact (made explicit by the following theorem that roots of polynomials correspond to linear factors. Theorem 3. Let f(x F[x] and a F. Then f(a = 0 if and only if (x a f(x. Proof. If (x a f(x then f(x = (x am(x for some m(x F[x], and so f(a = 0m(a = 0. Conversely, suppose f(a = 0. By the Division Algorithm, we may write f(x = (x aq(x+r(x for some q(x,r(x F[x] where r(x has degree less than (the degree of x a. If r(x = 0 then we would have (x a f(x, and so we would be done. So let s assume instead that r(x 0, in which case deg r(x = 0, so r = r(x is a nonzero constant. Substituting a for x gives 0 = f(a = 0m(a + r, so r = 0. This contradiction proves that in fact (x a f(x. This argument extends to multiple roots:
3 Theorem 4. If f(x F[x] has distinct roots a,a,...,a n, then f(x is divisible by (x a (x a (x a n. In particular, either f(x 0 or deg f(x n. Proof. Suppose f(x has at least n distinct roots a,a,...,a n. By Theorem 3, we have f(x = (x a g(x for some g(x F[x]. Substituting a for x gives 0 = f(a = (a a g(a where a a 0 since the n roots are distinct. Therefore g(a = 0, and by Theorem 3 we have g(x = (x a h(x for some h(x F[x]. Thus f(x = (x a (x a h(x. Continuing in this way, we eventually obtain f(x = (x a (x a (x a 3 (x a n m(x for some m(x F[x]. Corollary 5. A nonzero polynomial f(x F[x] of degree n cannot have more than n distinct roots. The notion of gcd for integers, generalizes to polynomials as follows. Given two polynomials f(x,g(x F[x], not both zero, we define the greatest common divisor (denoted gcd(f(x, g(x to be the unique monic polynomial of highest degree dividing both f(x and g(x. Here monic means having leading coefficient. Consider the following example: The divisors of f(x = x = ( ( x + x are all polynomials of the form c; c ( x + ; c ( x ; c ( x + ( x where c is an arbitrary nonzero constant. The divisors of g(x = x 3x + = (x (x = ( x ( x are c; c ( ( ( ( x ; c x ; c x x where c is an arbitrary nonzero constant. The common divisors of f(x and g(x have the form c; c ( x where c is an arbitrary nonzero constant. The polynomials of highest degree dividing both f(x and g(x have the form c ( x where c is a nonzero constant. In order that the greatest common divisor of f(x and g(x be welldefined, we choose c = so that the answer is monic; thus gcd ( f(x,g(x = gcd(x, x 3x + = x. The computation of gcd(f(x, g(x does not require knowing how to factorize polynomials; instead, we use Euclid s Algorithm, just as we did with integers. This algorithm, 3
4 in its extended form, also expresses gcd(f(x, g(x as a polynomiallinear combination of f(x and g(x: Theorem 6 (Euclid s Algorithm for Polynomials. Let f(x, g(x F[x] be polynomials, not both zero. Then there exist polynomials r(x, s(x F[x] such that r(xf(x + s(xg(x = gcd ( f(x,g(x. For example, we compute the gcd of the polynomials f(x = 5x 3 + x + 3x 0, g(x = x 3 + x 5x + Q[x]. The steps are almost the same as when computing the gcd of two integers. We proceed to repeatedly apply the Division Algorithm: 8x + 8x 0 = 4 47 f(x = 5g(x + ( 8x + 8x 0 g(x = ( 8 x 6 ( 8x + 8x 0 + ( 47 ( ( 8x x x 47 4 At this point we might want to say that gcd(f(x,g(x = 47 4 x 47 4 = 47 4 (x (the last nonzero remainder. However observe that the much simpler polynomial x divides both f(x and g(x. We choose the gcd to be monic, i.e. its leading coefficient should be. So in this case gcd(f(x,g(x = x and the extended form of the algorithm allows us to write this as a polynomiallinear combination of f(x and g(x: 47 4 x 47 4 = g(x ( 8 x 6 ( 8x + 8x 0; x = 4 47 g(x + ( 94 x + 88 ( 8x + 8x 0 = 4 47 g(x + ( 94 x + ( 88 f(x 5g(x = ( 94 x + 88 f(x + ( 5 94 x g(x. Ugly fractions like this are to be expected when working over Q. Life is much easier working over F p, when coefficients are more simply expressed as elements of {0,,,..., p }. Consider what happens to the preceding example over F 7 : f(x = 5x 3 + x + 3x + 4, g(x = x 3 + x + x + ; f(x = 5g(x + (6x + g(x = (6x + 5(6x + + (3x + 4 6x + = 5(6x + (3x
5 so from 3x+4 = 3(x+6 we obtain gcd(f(x,g(x = x+6 over F 7. The extended version of Euclid s Algorithm over F 7 is also not hard: 3x + 4 = 3(x + 6 = g(x (6x + 5(6x + ; x + 6 = 5g(x + (5x + 3(6x + = 5g(x + (5x + 3(f(x 5g(x = (5x + 3f(x + (3x + 4g(x. It is important to understand how this works (and to be prepared to perform simpler versions of this on a test in the same way that we expect you to be able (in principle to perform arithmetic (including multiplication and division of large integers. However, there is no additional benefit in repeatedly performing such operations by hand once the principles are mastered. For this we may use Maple: The analog of prime numbers, for polynomials, is the concept of an irreducible polynomial. A polynomial p(x F[x] of degree is irreducible if its only divisors are c and cp(x where c is a nonzero constant. The concept of irreducibility depends on the choice of field F; for example, x is irreducible over Q, but not over R where it factors as 5
6 ( x + ( x. The polynomial x + is irreducible over Q and over R, but not over C where it factors as (x + i(x i, i =. Recall Euclid s Lemma for Integers, which states that a prime p divides a product of two integers ab, iff p a or p b. (As usual, this is an inclusive or : we allow the possibility that both a and b are divisible by p. This fact extends to polynomials, with the same proof. Theorem 7 (Euclid s Lemma. Let p(x F[x] be irreducible, and consider two polynomials f(x,g(x F[x]. If f(xg(x is divisible by p(x, then p(x f(x or p(x g(x. Proof. Suppose that p(x f(x; we must prove that p(x g(x. Since p(x f(x where p(x is irreducible, we have gcd(p(x,f(x =. By Euclid s Algorithm, there exist r(x, s(x F[x] such that = r(xp(x + s(xf(x. Then g(x = [g(xr(x]p(x + s(x[f(xg(x] is divisible by p(x as required. A consequence of Euclid s Lemma is the fact that every polynomial has an essentially unique factorization into irreducible factors. By essentially unique, we mean the factorization is unique except for constant scalar multiples. If we factor out the coefficient of the leading term, and then use only monic irreducible factors, then the factorization is unique. This is the analogue (for polynomials of the Fundamental Theorem of Arithmetic (the fact that every positive integer has a unique factorization as a product of primes. HOMEWORK #3 Due Mon March 9, 0:0 am Solutions for this homework will be posted moments after the deadline, and further submissions will not be accepted beyond that time. Submit solutions in class, or to the departmental office (the secretary will put them in my mailbox, or by sliding under my office door, or by . (Remember never to submit homework outside my door. Solutions should be done by hand, but may be checked using Maple or other software (Sage, etc... Show that there do not exist polynomials q(x,r(x Z[x] such that x 3x + 4 = (3x+q(x+r(x and r(x is a constant. Conclude that the Division Algorithm does not hold in Z[x]. 6
7 . Show that there do exist polynomials q(x,r(x Q[x] such that x 3x + 4 = (3x + q(x + r(x and r(x is a constant. (This is an example of the Division Algorithm in Q[x]. The Division Algorithm holds for F[x], where F is any field, such as R, Q or F p. 3. Consider the polynomials f(x,d(x F 5 [x] given by f(x = x 4 + x 3 + 4x + x + 3; d(x = x + x + 3. Find the quotient q(x and remainder r(x when f(x is divided by d(x. Express your answers for q(x and r(x in simplified form using coefficients 0,,, 3, Consider the polynomials f(x,g(x F 7 [x] given by f(x = x 5 + x + ; g(x = x 4 + x +. Determine gcd(f(x,g(x and find r(x,s(x F 7 [x] such that r(xf(x + s(xg(x = gcd ( f(x,g(x. 7
Chapter 4, Arithmetic in F [x] Polynomial arithmetic and the division algorithm.
Chapter 4, Arithmetic in F [x] Polynomial arithmetic and the division algorithm. We begin by defining the ring of polynomials with coefficients in a ring R. After some preliminary results, we specialize
More informationIntroduction to Finite Fields (cont.)
Chapter 6 Introduction to Finite Fields (cont.) 6.1 Recall Theorem. Z m is a field m is a prime number. Theorem (Subfield Isomorphic to Z p ). Every finite field has the order of a power of a prime number
More informationPROBLEM SET 6: POLYNOMIALS
PROBLEM SET 6: POLYNOMIALS 1. introduction In this problem set we will consider polynomials with coefficients in K, where K is the real numbers R, the complex numbers C, the rational numbers Q or any other
More informationQuotient Rings and Field Extensions
Chapter 5 Quotient Rings and Field Extensions In this chapter we describe a method for producing field extension of a given field. If F is a field, then a field extension is a field K that contains F.
More informationit is easy to see that α = a
21. Polynomial rings Let us now turn out attention to determining the prime elements of a polynomial ring, where the coefficient ring is a field. We already know that such a polynomial ring is a UF. Therefore
More informationWinter Camp 2011 Polynomials Alexander Remorov. Polynomials. Alexander Remorov alexanderrem@gmail.com
Polynomials Alexander Remorov alexanderrem@gmail.com Warmup Problem 1: Let f(x) be a quadratic polynomial. Prove that there exist quadratic polynomials g(x) and h(x) such that f(x)f(x + 1) = g(h(x)).
More informationModern Algebra Lecture Notes: Rings and fields set 4 (Revision 2)
Modern Algebra Lecture Notes: Rings and fields set 4 (Revision 2) Kevin Broughan University of Waikato, Hamilton, New Zealand May 13, 2010 Remainder and Factor Theorem 15 Definition of factor If f (x)
More informationFactoring Polynomials
Factoring Polynomials Sue Geller June 19, 2006 Factoring polynomials over the rational numbers, real numbers, and complex numbers has long been a standard topic of high school algebra. With the advent
More information9. POLYNOMIALS. Example 1: The expression a(x) = x 3 4x 2 + 7x 11 is a polynomial in x. The coefficients of a(x) are the numbers 1, 4, 7, 11.
9. POLYNOMIALS 9.1. Definition of a Polynomial A polynomial is an expression of the form: a(x) = a n x n + a n1 x n1 +... + a 1 x + a 0. The symbol x is called an indeterminate and simply plays the role
More informationCHAPTER SIX IRREDUCIBILITY AND FACTORIZATION 1. BASIC DIVISIBILITY THEORY
January 10, 2010 CHAPTER SIX IRREDUCIBILITY AND FACTORIZATION 1. BASIC DIVISIBILITY THEORY The set of polynomials over a field F is a ring, whose structure shares with the ring of integers many characteristics.
More informationSOLVING POLYNOMIAL EQUATIONS
C SOLVING POLYNOMIAL EQUATIONS We will assume in this appendix that you know how to divide polynomials using long division and synthetic division. If you need to review those techniques, refer to an algebra
More informationcalculating the result modulo 3, as follows: p(0) = 0 3 + 0 + 1 = 1 0,
Homework #02, due 1/27/10 = 9.4.1, 9.4.2, 9.4.5, 9.4.6, 9.4.7. Additional problems recommended for study: (9.4.3), 9.4.4, 9.4.9, 9.4.11, 9.4.13, (9.4.14), 9.4.17 9.4.1 Determine whether the following polynomials
More informationModule MA3411: Abstract Algebra Galois Theory Appendix Michaelmas Term 2013
Module MA3411: Abstract Algebra Galois Theory Appendix Michaelmas Term 2013 D. R. Wilkins Copyright c David R. Wilkins 1997 2013 Contents A Cyclotomic Polynomials 79 A.1 Minimum Polynomials of Roots of
More informationFactorization Algorithms for Polynomials over Finite Fields
Degree Project Factorization Algorithms for Polynomials over Finite Fields Sajid Hanif, Muhammad Imran 20110503 Subject: Mathematics Level: Master Course code: 4MA11E Abstract Integer factorization is
More informationminimal polyonomial Example
Minimal Polynomials Definition Let α be an element in GF(p e ). We call the monic polynomial of smallest degree which has coefficients in GF(p) and α as a root, the minimal polyonomial of α. Example: We
More informationLagrange Interpolation is a method of fitting an equation to a set of points that functions well when there are few points given.
Polynomials (Ch.1) Study Guide by BS, JL, AZ, CC, SH, HL Lagrange Interpolation is a method of fitting an equation to a set of points that functions well when there are few points given. Sasha s method
More informationH/wk 13, Solutions to selected problems
H/wk 13, Solutions to selected problems Ch. 4.1, Problem 5 (a) Find the number of roots of x x in Z 4, Z Z, any integral domain, Z 6. (b) Find a commutative ring in which x x has infinitely many roots.
More informationa 1 x + a 0 =0. (3) ax 2 + bx + c =0. (4)
ROOTS OF POLYNOMIAL EQUATIONS In this unit we discuss polynomial equations. A polynomial in x of degree n, where n 0 is an integer, is an expression of the form P n (x) =a n x n + a n 1 x n 1 + + a 1 x
More informationUnique Factorization
Unique Factorization Waffle Mathcamp 2010 Throughout these notes, all rings will be assumed to be commutative. 1 Factorization in domains: definitions and examples In this class, we will study the phenomenon
More information(a) Write each of p and q as a polynomial in x with coefficients in Z[y, z]. deg(p) = 7 deg(q) = 9
Homework #01, due 1/20/10 = 9.1.2, 9.1.4, 9.1.6, 9.1.8, 9.2.3 Additional problems for study: 9.1.1, 9.1.3, 9.1.5, 9.1.13, 9.2.1, 9.2.2, 9.2.4, 9.2.5, 9.2.6, 9.3.2, 9.3.3 9.1.1 (This problem was not assigned
More informationPOLYNOMIAL RINGS AND UNIQUE FACTORIZATION DOMAINS
POLYNOMIAL RINGS AND UNIQUE FACTORIZATION DOMAINS RUSS WOODROOFE 1. Unique Factorization Domains Throughout the following, we think of R as sitting inside R[x] as the constant polynomials (of degree 0).
More informationCopy in your notebook: Add an example of each term with the symbols used in algebra 2 if there are any.
Algebra 2  Chapter Prerequisites Vocabulary Copy in your notebook: Add an example of each term with the symbols used in algebra 2 if there are any. P1 p. 1 1. counting(natural) numbers  {1,2,3,4,...}
More information7. Some irreducible polynomials
7. Some irreducible polynomials 7.1 Irreducibles over a finite field 7.2 Worked examples Linear factors x α of a polynomial P (x) with coefficients in a field k correspond precisely to roots α k [1] of
More informationPUTNAM TRAINING POLYNOMIALS. Exercises 1. Find a polynomial with integral coefficients whose zeros include 2 + 5.
PUTNAM TRAINING POLYNOMIALS (Last updated: November 17, 2015) Remark. This is a list of exercises on polynomials. Miguel A. Lerma Exercises 1. Find a polynomial with integral coefficients whose zeros include
More informationKevin James. MTHSC 412 Section 2.4 Prime Factors and Greatest Comm
MTHSC 412 Section 2.4 Prime Factors and Greatest Common Divisor Greatest Common Divisor Definition Suppose that a, b Z. Then we say that d Z is a greatest common divisor (gcd) of a and b if the following
More information1 = (a 0 + b 0 α) 2 + + (a m 1 + b m 1 α) 2. for certain elements a 0,..., a m 1, b 0,..., b m 1 of F. Multiplying out, we obtain
Notes on realclosed fields These notes develop the algebraic background needed to understand the model theory of realclosed fields. To understand these notes, a standard graduate course in algebra is
More informationGREATEST COMMON DIVISOR
DEFINITION: GREATEST COMMON DIVISOR The greatest common divisor (gcd) of a and b, denoted by (a, b), is the largest common divisor of integers a and b. THEOREM: If a and b are nonzero integers, then their
More informationFactorization in Polynomial Rings
Factorization in Polynomial Rings These notes are a summary of some of the important points on divisibility in polynomial rings from 17 and 18 of Gallian s Contemporary Abstract Algebra. Most of the important
More informationMOP 2007 Black Group Integer Polynomials Yufei Zhao. Integer Polynomials. June 29, 2007 Yufei Zhao yufeiz@mit.edu
Integer Polynomials June 9, 007 Yufei Zhao yufeiz@mit.edu We will use Z[x] to denote the ring of polynomials with integer coefficients. We begin by summarizing some of the common approaches used in dealing
More information3.6 The Real Zeros of a Polynomial Function
SECTION 3.6 The Real Zeros of a Polynomial Function 219 3.6 The Real Zeros of a Polynomial Function PREPARING FOR THIS SECTION Before getting started, review the following: Classification of Numbers (Appendix,
More informationTheory of Matrices. Chapter 5
Chapter 5 Theory of Matrices As before, F is a field We use F[x] to represent the set of all polynomials of x with coefficients in F We use M m,n (F) and M m,n (F[x]) to denoted the set of m by n matrices
More information3.2 The Factor Theorem and The Remainder Theorem
3. The Factor Theorem and The Remainder Theorem 57 3. The Factor Theorem and The Remainder Theorem Suppose we wish to find the zeros of f(x) = x 3 + 4x 5x 4. Setting f(x) = 0 results in the polynomial
More informationMarch 29, 2011. 171S4.4 Theorems about Zeros of Polynomial Functions
MAT 171 Precalculus Algebra Dr. Claude Moore Cape Fear Community College CHAPTER 4: Polynomial and Rational Functions 4.1 Polynomial Functions and Models 4.2 Graphing Polynomial Functions 4.3 Polynomial
More informationThe finite field with 2 elements The simplest finite field is
The finite field with 2 elements The simplest finite field is GF (2) = F 2 = {0, 1} = Z/2 It has addition and multiplication + and defined to be 0 + 0 = 0 0 + 1 = 1 1 + 0 = 1 1 + 1 = 0 0 0 = 0 0 1 = 0
More information1 Homework 1. [p 0 q i+j +... + p i 1 q j+1 ] + [p i q j ] + [p i+1 q j 1 +... + p i+j q 0 ]
1 Homework 1 (1) Prove the ideal (3,x) is a maximal ideal in Z[x]. SOLUTION: Suppose we expand this ideal by including another generator polynomial, P / (3, x). Write P = n + x Q with n an integer not
More informationMath 34560 Abstract Algebra I Questions for Section 23: Factoring Polynomials over a Field
Math 34560 Abstract Algebra I Questions for Section 23: Factoring Polynomials over a Field 1. Throughout this section, F is a field and F [x] is the ring of polynomials with coefficients in F. We will
More informationCHAPTER 5. Number Theory. 1. Integers and Division. Discussion
CHAPTER 5 Number Theory 1. Integers and Division 1.1. Divisibility. Definition 1.1.1. Given two integers a and b we say a divides b if there is an integer c such that b = ac. If a divides b, we write a
More information8 Divisibility and prime numbers
8 Divisibility and prime numbers 8.1 Divisibility In this short section we extend the concept of a multiple from the natural numbers to the integers. We also summarize several other terms that express
More informationSection 4.2: The Division Algorithm and Greatest Common Divisors
Section 4.2: The Division Algorithm and Greatest Common Divisors The Division Algorithm The Division Algorithm is merely long division restated as an equation. For example, the division 29 r. 20 32 948
More information3 Factorisation into irreducibles
3 Factorisation into irreducibles Consider the factorisation of a nonzero, noninvertible integer n as a product of primes: n = p 1 p t. If you insist that primes should be positive then, since n could
More information15. Symmetric polynomials
15. Symmetric polynomials 15.1 The theorem 15.2 First examples 15.3 A variant: discriminants 1. The theorem Let S n be the group of permutations of {1,, n}, also called the symmetric group on n things.
More informationChapter 13: Basic ring theory
Chapter 3: Basic ring theory Matthew Macauley Department of Mathematical Sciences Clemson University http://www.math.clemson.edu/~macaule/ Math 42, Spring 24 M. Macauley (Clemson) Chapter 3: Basic ring
More informationCS 103X: Discrete Structures Homework Assignment 3 Solutions
CS 103X: Discrete Structures Homework Assignment 3 s Exercise 1 (20 points). On wellordering and induction: (a) Prove the induction principle from the wellordering principle. (b) Prove the wellordering
More informationThe cyclotomic polynomials
The cyclotomic polynomials Notes by G.J.O. Jameson 1. The definition and general results We use the notation e(t) = e 2πit. Note that e(n) = 1 for integers n, e(s + t) = e(s)e(t) for all s, t. e( 1 ) =
More informationRESULTANT AND DISCRIMINANT OF POLYNOMIALS
RESULTANT AND DISCRIMINANT OF POLYNOMIALS SVANTE JANSON Abstract. This is a collection of classical results about resultants and discriminants for polynomials, compiled mainly for my own use. All results
More informationr + s = i + j (q + t)n; 2 rs = ij (qj + ti)n + qtn.
Chapter 7 Introduction to finite fields This chapter provides an introduction to several kinds of abstract algebraic structures, particularly groups, fields, and polynomials. Our primary interest is in
More informationReal Roots of Univariate Polynomials with Real Coefficients
Real Roots of Univariate Polynomials with Real Coefficients mostly written by Christina Hewitt March 22, 2012 1 Introduction Polynomial equations are used throughout mathematics. When solving polynomials
More informationSome facts about polynomials modulo m (Full proof of the Fingerprinting Theorem)
Some facts about polynomials modulo m (Full proof of the Fingerprinting Theorem) In order to understand the details of the Fingerprinting Theorem on fingerprints of different texts from Chapter 19 of the
More informationContinued Fractions and the Euclidean Algorithm
Continued Fractions and the Euclidean Algorithm Lecture notes prepared for MATH 326, Spring 997 Department of Mathematics and Statistics University at Albany William F Hammond Table of Contents Introduction
More informationJUST THE MATHS UNIT NUMBER 1.8. ALGEBRA 8 (Polynomials) A.J.Hobson
JUST THE MATHS UNIT NUMBER 1.8 ALGEBRA 8 (Polynomials) by A.J.Hobson 1.8.1 The factor theorem 1.8.2 Application to quadratic and cubic expressions 1.8.3 Cubic equations 1.8.4 Long division of polynomials
More information3 1. Note that all cubes solve it; therefore, there are no more
Math 13 Problem set 5 Artin 11.4.7 Factor the following polynomials into irreducible factors in Q[x]: (a) x 3 3x (b) x 3 3x + (c) x 9 6x 6 + 9x 3 3 Solution: The first two polynomials are cubics, so if
More informationHow To Know If A Domain Is Unique In An Octempo (Euclidean) Or Not (Ecl)
Subsets of Euclidean domains possessing a unique division algorithm Andrew D. Lewis 2009/03/16 Abstract Subsets of a Euclidean domain are characterised with the following objectives: (1) ensuring uniqueness
More information1 if 1 x 0 1 if 0 x 1
Chapter 3 Continuity In this chapter we begin by defining the fundamental notion of continuity for real valued functions of a single real variable. When trying to decide whether a given function is or
More informationDie ganzen zahlen hat Gott gemacht
Die ganzen zahlen hat Gott gemacht Polynomials with integer values B.Sury A quote attributed to the famous mathematician L.Kronecker is Die Ganzen Zahlen hat Gott gemacht, alles andere ist Menschenwerk.
More information1.3 Polynomials and Factoring
1.3 Polynomials and Factoring Polynomials Constant: a number, such as 5 or 27 Variable: a letter or symbol that represents a value. Term: a constant, variable, or the product or a constant and variable.
More information1 Lecture: Integration of rational functions by decomposition
Lecture: Integration of rational functions by decomposition into partial fractions Recognize and integrate basic rational functions, except when the denominator is a power of an irreducible quadratic.
More informationFACTORING POLYNOMIALS IN THE RING OF FORMAL POWER SERIES OVER Z
FACTORING POLYNOMIALS IN THE RING OF FORMAL POWER SERIES OVER Z DANIEL BIRMAJER, JUAN B GIL, AND MICHAEL WEINER Abstract We consider polynomials with integer coefficients and discuss their factorization
More informationSome Polynomial Theorems. John Kennedy Mathematics Department Santa Monica College 1900 Pico Blvd. Santa Monica, CA 90405 rkennedy@ix.netcom.
Some Polynomial Theorems by John Kennedy Mathematics Department Santa Monica College 1900 Pico Blvd. Santa Monica, CA 90405 rkennedy@ix.netcom.com This paper contains a collection of 31 theorems, lemmas,
More informationPrime Numbers and Irreducible Polynomials
Prime Numbers and Irreducible Polynomials M. Ram Murty The similarity between prime numbers and irreducible polynomials has been a dominant theme in the development of number theory and algebraic geometry.
More informationNotes 11: List Decoding Folded ReedSolomon Codes
Introduction to Coding Theory CMU: Spring 2010 Notes 11: List Decoding Folded ReedSolomon Codes April 2010 Lecturer: Venkatesan Guruswami Scribe: Venkatesan Guruswami At the end of the previous notes,
More informationTHE FUNDAMENTAL THEOREM OF ALGEBRA VIA PROPER MAPS
THE FUNDAMENTAL THEOREM OF ALGEBRA VIA PROPER MAPS KEITH CONRAD 1. Introduction The Fundamental Theorem of Algebra says every nonconstant polynomial with complex coefficients can be factored into linear
More informationGCDs and Relatively Prime Numbers! CSCI 2824, Fall 2014!
GCDs and Relatively Prime Numbers! CSCI 2824, Fall 2014!!! Challenge Problem 2 (Mastermind) due Fri. 9/26 Find a fourth guess whose scoring will allow you to determine the secret code (repetitions are
More informationz 0 and y even had the form
Gaussian Integers The concepts of divisibility, primality and factoring are actually more general than the discussion so far. For the moment, we have been working in the integers, which we denote by Z
More information2 Polynomials over a field
2 Polynomials over a field A polynomial over a field F is a sequence (a 0, a 1, a 2,, a n, ) where a i F i with a i = 0 from some point on a i is called the i th coefficient of f We define three special
More informationThe van Hoeij Algorithm for Factoring Polynomials
The van Hoeij Algorithm for Factoring Polynomials Jürgen Klüners Abstract In this survey we report about a new algorithm for factoring polynomials due to Mark van Hoeij. The main idea is that the combinatorial
More informationON GALOIS REALIZATIONS OF THE 2COVERABLE SYMMETRIC AND ALTERNATING GROUPS
ON GALOIS REALIZATIONS OF THE 2COVERABLE SYMMETRIC AND ALTERNATING GROUPS DANIEL RABAYEV AND JACK SONN Abstract. Let f(x) be a monic polynomial in Z[x] with no rational roots but with roots in Q p for
More informationLecture Notes on Polynomials
Lecture Notes on Polynomials Arne Jensen Department of Mathematical Sciences Aalborg University c 008 Introduction These lecture notes give a very short introduction to polynomials with real and complex
More informationU.C. Berkeley CS276: Cryptography Handout 0.1 Luca Trevisan January, 2009. Notes on Algebra
U.C. Berkeley CS276: Cryptography Handout 0.1 Luca Trevisan January, 2009 Notes on Algebra These notes contain as little theory as possible, and most results are stated without proof. Any introductory
More informationThe Method of Partial Fractions Math 121 Calculus II Spring 2015
Rational functions. as The Method of Partial Fractions Math 11 Calculus II Spring 015 Recall that a rational function is a quotient of two polynomials such f(x) g(x) = 3x5 + x 3 + 16x x 60. The method
More informationMathematics Course 111: Algebra I Part IV: Vector Spaces
Mathematics Course 111: Algebra I Part IV: Vector Spaces D. R. Wilkins Academic Year 19967 9 Vector Spaces A vector space over some field K is an algebraic structure consisting of a set V on which are
More informationZeros of Polynomial Functions
Review: Synthetic Division Find (x 25x  5x 3 + x 4 ) (5 + x). Factor Theorem Solve 2x 35x 2 + x + 2 =0 given that 2 is a zero of f(x) = 2x 35x 2 + x + 2. Zeros of Polynomial Functions Introduction
More informationNumber Theory Hungarian Style. Cameron Byerley s interpretation of Csaba Szabó s lectures
Number Theory Hungarian Style Cameron Byerley s interpretation of Csaba Szabó s lectures August 20, 2005 2 0.1 introduction Number theory is a beautiful subject and even cooler when you learn about it
More information10 Splitting Fields. 2. The splitting field for x 3 2 over Q is Q( 3 2,ω), where ω is a primitive third root of 1 in C. Thus, since ω = 1+ 3
10 Splitting Fields We have seen how to construct a field K F such that K contains a root α of a given (irreducible) polynomial p(x) F [x], namely K = F [x]/(p(x)). We can extendthe procedure to build
More informationCollege Algebra  MAT 161 Page: 1 Copyright 2009 Killoran
College Algebra  MAT 6 Page: Copyright 2009 Killoran Zeros and Roots of Polynomial Functions Finding a Root (zero or xintercept) of a polynomial is identical to the process of factoring a polynomial.
More informationToday s Topics. Primes & Greatest Common Divisors
Today s Topics Primes & Greatest Common Divisors Prime representations Important theorems about primality Greatest Common Divisors Least Common Multiples Euclid s algorithm Once and for all, what are prime
More informationABSTRACT ALGEBRA: A STUDY GUIDE FOR BEGINNERS
ABSTRACT ALGEBRA: A STUDY GUIDE FOR BEGINNERS John A. Beachy Northern Illinois University 2014 ii J.A.Beachy This is a supplement to Abstract Algebra, Third Edition by John A. Beachy and William D. Blair
More information11 Ideals. 11.1 Revisiting Z
11 Ideals The presentation here is somewhat different than the text. In particular, the sections do not match up. We have seen issues with the failure of unique factorization already, e.g., Z[ 5] = O Q(
More informationLecture 6: Finite Fields (PART 3) PART 3: Polynomial Arithmetic. Theoretical Underpinnings of Modern Cryptography
Lecture 6: Finite Fields (PART 3) PART 3: Polynomial Arithmetic Theoretical Underpinnings of Modern Cryptography Lecture Notes on Computer and Network Security by Avi Kak (kak@purdue.edu) January 29, 2015
More information1.7. Partial Fractions. 1.7.1. Rational Functions and Partial Fractions. A rational function is a quotient of two polynomials: R(x) = P (x) Q(x).
.7. PRTIL FRCTIONS 3.7. Partial Fractions.7.. Rational Functions and Partial Fractions. rational function is a quotient of two polynomials: R(x) = P (x) Q(x). Here we discuss how to integrate rational
More informationMath 4310 Handout  Quotient Vector Spaces
Math 4310 Handout  Quotient Vector Spaces Dan Collins The textbook defines a subspace of a vector space in Chapter 4, but it avoids ever discussing the notion of a quotient space. This is understandable
More informationDiscrete Mathematics and Probability Theory Fall 2009 Satish Rao, David Tse Note 2
CS 70 Discrete Mathematics and Probability Theory Fall 2009 Satish Rao, David Tse Note 2 Proofs Intuitively, the concept of proof should already be familiar We all like to assert things, and few of us
More informationFACTORING IN QUADRATIC FIELDS. 1. Introduction. This is called a quadratic field and it has degree 2 over Q. Similarly, set
FACTORING IN QUADRATIC FIELDS KEITH CONRAD For a squarefree integer d other than 1, let 1. Introduction K = Q[ d] = {x + y d : x, y Q}. This is called a quadratic field and it has degree 2 over Q. Similarly,
More informationReducibility of Second Order Differential Operators with Rational Coefficients
Reducibility of Second Order Differential Operators with Rational Coefficients Joseph Geisbauer University of ArkansasFort Smith Advisor: Dr. Jill Guerra May 10, 2007 1. INTRODUCTION In this paper we
More informationA number field is a field of finite degree over Q. By the Primitive Element Theorem, any number
Number Fields Introduction A number field is a field of finite degree over Q. By the Primitive Element Theorem, any number field K = Q(α) for some α K. The minimal polynomial Let K be a number field and
More informationApplication. Outline. 31 Polynomial Functions 32 Finding Rational Zeros of. Polynomial. 33 Approximating Real Zeros of.
Polynomial and Rational Functions Outline 31 Polynomial Functions 32 Finding Rational Zeros of Polynomials 33 Approximating Real Zeros of Polynomials 34 Rational Functions Chapter 3 Group Activity:
More informationUNCORRECTED PAGE PROOFS
number and and algebra TopIC 17 Polynomials 17.1 Overview Why learn this? Just as number is learned in stages, so too are graphs. You have been building your knowledge of graphs and functions over time.
More informationPolynomial Factoring. Ramesh Hariharan
Polynomial Factoring Ramesh Hariharan The Problem Factoring Polynomials overs Integers Factorization is unique (why?) (x^2 + 5x +6) (x+2)(x+3) Time: Polynomial in degree A Related Problem Factoring Integers
More informationAlgebra Unpacked Content For the new Common Core standards that will be effective in all North Carolina schools in the 201213 school year.
This document is designed to help North Carolina educators teach the Common Core (Standard Course of Study). NCDPI staff are continually updating and improving these tools to better serve teachers. Algebra
More informationFactoring of Prime Ideals in Extensions
Chapter 4 Factoring of Prime Ideals in Extensions 4. Lifting of Prime Ideals Recall the basic AKLB setup: A is a Dedekind domain with fraction field K, L is a finite, separable extension of K of degree
More information63. Graph y 1 2 x and y 2 THE FACTOR THEOREM. The Factor Theorem. Consider the polynomial function. P(x) x 2 2x 15.
9.4 (927) 517 Gear ratio d) For a fixed wheel size and chain ring, does the gear ratio increase or decrease as the number of teeth on the cog increases? decreases 100 80 60 40 20 27in. wheel, 44 teeth
More informationMATH 289 PROBLEM SET 4: NUMBER THEORY
MATH 289 PROBLEM SET 4: NUMBER THEORY 1. The greatest common divisor If d and n are integers, then we say that d divides n if and only if there exists an integer q such that n = qd. Notice that if d divides
More informationMath Review. for the Quantitative Reasoning Measure of the GRE revised General Test
Math Review for the Quantitative Reasoning Measure of the GRE revised General Test www.ets.org Overview This Math Review will familiarize you with the mathematical skills and concepts that are important
More informationALGEBRAIC NUMBER THEORY AND QUADRATIC RECIPROCITY
ALGEBRAIC NUMBER THEORY AND QUADRATIC RECIPROCITY HENRY COHN, JOSHUA GREENE, JONATHAN HANKE 1. Introduction These notes are from a series of lectures given by Henry Cohn during MIT s Independent Activities
More informationHow To Understand The Theory Of Algebraic Functions
Homework 4 3.4,. Show that x x cos x x holds for x 0. Solution: Since cos x, multiply all three parts by x > 0, we get: x x cos x x, and since x 0 x x 0 ( x ) = 0, then by Sandwich theorem, we get: x 0
More information8 Primes and Modular Arithmetic
8 Primes and Modular Arithmetic 8.1 Primes and Factors Over two millennia ago already, people all over the world were considering the properties of numbers. One of the simplest concepts is prime numbers.
More informationp e i 1 [p e i i ) = i=1
Homework 1 Solutions  Sri Raga Velagapudi Algebra Section 1. Show that if n Z then for every integer a with gcd(a, n) = 1, there exists a unique x mod n such that ax = 1 mod n. By the definition of gcd,
More informationMathematics for Computer Science/Software Engineering. Notes for the course MSM1F3 Dr. R. A. Wilson
Mathematics for Computer Science/Software Engineering Notes for the course MSM1F3 Dr. R. A. Wilson October 1996 Chapter 1 Logic Lecture no. 1. We introduce the concept of a proposition, which is a statement
More information2. Let H and K be subgroups of a group G. Show that H K G if and only if H K or K H.
Math 307 Abstract Algebra Sample final examination questions with solutions 1. Suppose that H is a proper subgroup of Z under addition and H contains 18, 30 and 40, Determine H. Solution. Since gcd(18,
More informationField Fundamentals. Chapter 3. 3.1 Field Extensions. 3.1.1 Definitions. 3.1.2 Lemma
Chapter 3 Field Fundamentals 3.1 Field Extensions If F is a field and F [X] is the set of all polynomials over F, that is, polynomials with coefficients in F, we know that F [X] is a Euclidean domain,
More informationIrreducibility criteria for compositions and multiplicative convolutions of polynomials with integer coefficients
DOI: 10.2478/auom20140007 An. Şt. Univ. Ovidius Constanţa Vol. 221),2014, 73 84 Irreducibility criteria for compositions and multiplicative convolutions of polynomials with integer coefficients Anca
More information