as follows, where +, −, and × represent polynomial arithmetic, and / represents simple division of two terms: function n / d is require d ≠ 0 q ← 0 r ← n // At each step n = d × q + r while r ≠ 0 and degree(r) ≥ degree(d) do t ← lead(r) / lead(d) // Divide the leading terms q ← q + t r ← r − t × d return (q, r) This works equally well when degree(n) < degree(d); in that case the result is just the trivial (0, n). This algorithm describes exactly the above paper and pencil method: is written on the left of the ")"; is written, term after term, above the horizontal line, the last term being the value of ; the region under the horizontal line is used to compute and write down the successive values of . Euclidean division For every pair of polynomials (A, B) such that B ≠ 0, polynomial division provides a quotient Q and a remainder R such that and either R=0 or degree(R) < degree(B). Moreover (Q, R) is the unique pair of polynomials having this property. The process of getting the uniquely defined polynomials Q and R from A and B is called Euclidean division (sometimes division transformation). Polynomial long division is thus an algorithm for Euclidean division. Applications Factoring polynomials Sometimes one or more roots of a polynomial are known, perhaps having been found using the rational root theorem. If one root r of a polynomial P(x) of degree n is known then polynomial long division can be used to factor P(x) into the form where Q(x) is a polynomial of degree n − 1. Q(x) is simply the quotient obtained from the division process; since r is known to be a root of P(x), it is known that the remainder must be zero. Likewise, if more than one root is known, a linear factor in one of them (r) can be divided out to obtain Q(x), and then a linear term in another root, s, can be divided out of Q(x), etc. Alternatively, they can all be divided out at once: for example the linear factors and can be multiplied together to obtain the quadratic factor which can then be divided into the original polynomial P(x) to obtain a quotient of degree In this way, sometimes all the roots