Polynomial long division
Polynomial long division is an algorithm for dividing a polynomial by another polynomial of lower or equal degree, analogous to the long division process for integers, resulting in a quotient and a remainder where the degree of the remainder is less than the degree of the divisor.[1] The process formalizes the division algorithm for polynomials, which states that for any polynomials P(x) (the dividend) and D(x) (the divisor) with \deg(D) \geq 1, there exist unique polynomials Q(x) (the quotient) and R(x) (the remainder) such that P(x) = D(x) \cdot Q(x) + R(x) and \deg(R) < \deg(D).[2] This method is essential in algebra for simplifying expressions, factoring polynomials, and solving equations, particularly when synthetic division is not applicable for non-linear divisors.
To perform polynomial long division, the polynomials are first written in standard form with descending powers of the variable, inserting zero coefficients for any missing terms to ensure alignment.[1] The steps—divide, multiply, subtract, and bring down—mirror those of integer long division but operate on coefficients and powers of the variable.[1]
When the divisor is linear, such as x - c, the process simplifies to synthetic division, which uses only the coefficients and avoids explicit polynomial multiplication and subtraction, making it more efficient for evaluation and root-finding via the remainder theorem, where the remainder equals P(c).[1] Polynomial long division underpins advanced topics like partial fraction decomposition,[3] where it is used when the numerator degree is greater than or equal to the denominator's, and the Euclidean algorithm for polynomials, facilitating greatest common divisor computations in algebraic structures.[4]
Fundamentals
Definition
Polynomial long division is an algorithm in algebra for dividing one polynomial, known as the dividend, by another polynomial, called the divisor, to obtain a quotient polynomial and a remainder polynomial such that the degree of the remainder is strictly less than the degree of the divisor.[1] This method mirrors the long division process used for integers, adapting it to the structure of polynomials.[4]
The underlying principle is formalized by the division algorithm for polynomials. For polynomials f(x) and g(x) in the polynomial ring F over a field F (such as the rational numbers \mathbb{Q} or the real numbers \mathbb{R}), with g(x) \neq 0, there exist unique polynomials q(x) and r(x) in F satisfying
f(x) = q(x) g(x) + r(x),
where either r(x) = 0 or \deg(r(x)) < \deg(g(x)).[5]
Polynomial long division presupposes proficiency in fundamental polynomial operations, namely addition and scalar multiplication of terms, as well as multiplication and addition of entire polynomials, though these are not elaborated here.[6] While early work on polynomial arithmetic dates to the 10th century, the technique of long division emerged in 16th- and 17th-century algebra texts amid the development of symbolic notation for polynomials.[7]
Historical context
Early contributions to polynomial arithmetic trace to the Persian mathematician Al-Karaji (c. 953–1029 CE), who around 1000 CE established rules for operations on polynomials, including division of sums of monomials by monomials, treating polynomials as independent algebraic objects free from geometric constraints.[8] Al-Karaji's innovations in Al-Fakhri fi'l-jabr wa'l-muqabala laid foundational groundwork for algebraic manipulations, though his work focused primarily on positive terms and practical computations.[9]
This approach was extended and systematized by European algebraists in the late 16th century, with François Viète (1540–1603) advancing symbolic notation in works like his 1591 treatise Zeteticorum libri quinque, enabling more systematic handling of polynomial expressions to solve Diophantine-style problems.[10] Viète's methods marked a shift toward modern symbolic algebra.
Key milestones in the 17th century included full formalization by René Descartes (1596–1650) in La Géométrie (1637), which integrated polynomial division into analytic geometry for resolving equations and constructing curves, and by Isaac Newton (1643–1727), who employed it extensively in his interpolation formulas and binomial series expansions.[11] By the 19th century, the technique was incorporated into abstract algebra through the development of polynomial rings, as seen in the ideal theory of David Hilbert (1862–1943) and Richard Dedekind (1831–1916), where division algorithms underpin unique factorization domains.[12]
Pre-European developments, such as those by Indian mathematicians like Bhaskara II (1114–1185) on polynomial equations, also contributed to the algebraic tradition. Drawing from integer long division traditions, Paolo Ruffini (1765–1822) simplified the process in 1809 with his rule for linear divisors, reducing steps by omitting explicit polynomial terms and directly computing coefficients, which paved the way for synthetic division as an efficient variant.[13] This evolution reflects broader influences from the Euclidean algorithm, adapted for gcd computations in polynomial rings during the rise of algebraic number theory.
Algorithm
Long division steps
Polynomial long division follows a systematic procedure analogous to the long division algorithm used for integers, adapted to handle polynomials arranged in descending powers of the variable.[14][1] The process begins by aligning the dividend (the polynomial to be divided) and the divisor (the polynomial by which to divide) by their degrees, ensuring both are written with terms in descending order and inserting zero coefficients for any missing powers to maintain alignment.[15][16]
The detailed steps are as follows:
-
Divide the leading term (highest-degree term) of the current dividend by the leading term of the divisor to obtain the first term of the quotient. This term's degree is the difference in degrees between the dividend and divisor, and its coefficient is the ratio of the leading coefficients.[14][1]
-
Multiply the entire divisor by this quotient term, aligning the result by degrees with the current dividend.[15][16]
-
Subtract the resulting polynomial from the current dividend, term by term, paying close attention to coefficients and signs to avoid errors in tracking.[14][1]
-
Bring down the next term from the original dividend (if any) to form the new current dividend, which becomes the remainder after subtraction.[15][16]
-
Repeat steps 1 through 4 with the new current dividend until the degree of the remainder is less than the degree of the divisor. The process stops here, as further division is not possible.[14][1]
Special cases arise depending on the relative degrees. If the degree of the divisor is greater than the degree of the dividend at the start, the quotient is zero, and the entire dividend serves as the remainder.[15][16] For exact division, the final remainder is zero, indicating the divisor is a factor of the dividend.[1][14]
The underlying relation is expressed by the division algorithm for polynomials:
f(x) = q(x) \cdot g(x) + r(x)
where f(x) is the dividend, g(x) is the divisor, q(x) is the quotient, and r(x) is the remainder with \deg r < \deg g (or r(x) = 0). This equation holds identically for all x, and the steps iteratively build q(x) and r(x).[15][16]
To ensure accuracy, always arrange polynomials in descending powers before starting and meticulously track coefficients during subtraction, as misalignment can lead to incorrect results.[1][14]
Short division variant
Synthetic division, also known as the short division variant of polynomial long division, is a tabular method used to divide a polynomial by a linear binomial of the form x - c, where c is a constant, thereby avoiding the need for explicit polynomial multiplication and subtraction as in the full long division process.[17][18] This technique streamlines the computation by organizing coefficients in a compact array, making it particularly efficient for evaluating polynomials or testing potential roots.
The process begins by listing the coefficients of the dividend polynomial f(x) in descending order of degree, including zeros for any missing terms, with the value c (the root of the divisor) placed to the left. The first coefficient is brought down unchanged to form the start of the bottom row. Then, multiply this value by c and write the product beneath the next coefficient; add them to obtain the new bottom entry. Repeat this multiplication and addition for each subsequent coefficient until the end of the row. The resulting bottom row provides the coefficients of the quotient polynomial (one degree less than the dividend), while the final entry is the remainder.[17][19][18]
For a polynomial f(x) divided by x - c, the synthetic division yields quotient coefficients directly from the array, and the remainder equals f(c) as per the remainder theorem, which states that the remainder of such a division is the polynomial evaluated at x = c.[17][18]
This method offers advantages such as fewer arithmetic operations, the elimination of variable notation during calculations, and reduced likelihood of errors compared to traditional long division, making it especially useful for repeated root testing in polynomial factorization.[18][19] However, its primary limitation is applicability only to linear divisors of the form x - c with leading coefficient 1, rendering it unsuitable for higher-degree divisors or non-monic linear factors.[18][19]
Examples
Basic division
To illustrate the basic process of polynomial long division, consider dividing the quadratic polynomial x^2 + 3x + 2 by the linear polynomial x + 1. This example follows the standard long division steps for polynomials, where the goal is to find the quotient and remainder such that the dividend equals the divisor times the quotient plus the remainder, with the degree of the remainder less than the degree of the divisor.[20]
The setup resembles numerical long division, with the divisor placed outside a division bracket and the dividend inside, arranged in descending powers of x:
x + 2
x + 1 | x² + 3x + 2
-(x² + x )
-----------
2x + 2
-(2x + 2)
---------
0
x + 2
x + 1 | x² + 3x + 2
-(x² + x )
-----------
2x + 2
-(2x + 2)
---------
0
Begin by dividing the leading term of the dividend by the leading term of the divisor: \frac{x^2}{x} = x. This is the first term of the quotient. Multiply x by the entire divisor: x(x + 1) = x^2 + x. Align and subtract this product from the dividend: (x^2 + 3x + 2) - (x^2 + x) = 2x + 2.[20]
Next, divide the new leading term $2x by the leading term of the divisor: \frac{2x}{x} = 2. This is the second term of the quotient. Multiply $2 by the divisor: $2(x + 1) = 2x + 2. Subtract: (2x + 2) - (2x + 2) = 0. Since the remainder is 0 and its degree is less than that of the divisor, the process ends. The quotient is x + 2 and the remainder is 0.[20]
To verify, multiply the divisor by the quotient: (x + 1)(x + 2) = x^2 + 2x + x + 2 = x^2 + 3x + 2, which matches the original dividend, confirming the division is exact with no remainder.[20]
Division with remainder
In polynomial long division, a non-zero remainder occurs when the dividend cannot be exactly factored by the divisor, resulting in an incomplete division process that terminates once the degree of the remaining polynomial is less than the degree of the divisor.[1] This aligns with the division algorithm for polynomials, which states that for any polynomials P(x) (dividend) and D(x) (divisor) with \deg D(x) \geq 1, there exist unique polynomials Q(x) (quotient) and R(x) (remainder) such that P(x) = D(x) \cdot Q(x) + R(x) and \deg R(x) < \deg D(x).[1] The condition \deg R(x) < \deg D(x) ensures the algorithm halts, preventing infinite division, and allows representation of the dividend in a form useful for further analysis, such as evaluating limits or partial fraction decomposition.[1]
Consider the example of dividing x^3 + 2x^2 - 6x - 6 by x^2 - x - 2. The divisor has degree 2, so the process continues until the remainder has degree less than 2. Begin by dividing the leading term of the dividend (x^3) by the leading term of the divisor (x^2), yielding the first partial quotient term x.
Multiply x by the divisor:
x \cdot (x^2 - x - 2) = x^3 - x^2 - 2x.
Subtract this from the dividend:
(x^3 + 2x^2 - 6x - 6) - (x^3 - x^2 - 2x) = 3x^2 - 4x - 6.
Now divide the leading term of this new polynomial ($3x^2) by x^2, giving the next partial quotient term 3. The full quotient is thus x + 3.
Multiply 3 by the divisor:
$3 \cdot (x^2 - x - 2) = 3x^2 - 3x - 6.
Subtract:
(3x^2 - 4x - 6) - (3x^2 - 3x - 6) = -x.
The remainder is -x, which has degree 1, less than the divisor's degree of 2, so the division stops. The partial quotients x and 3 accumulate to form the complete quotient, illustrating how the algorithm builds the result incrementally while respecting the degree condition.[1]
To verify, expand the quotient and remainder form:
(x^2 - x - 2)(x + 3) + (-x) = x^3 + 2x^2 - 6x - 6,
which matches the original dividend. This confirms the division's accuracy and highlights the role of the remainder in capturing the "leftover" portion that cannot be expressed as integer multiples of the divisor.[1]
Theoretical foundations
Euclidean algorithm connection
Polynomial long division serves as the foundational operation in the Euclidean algorithm for polynomials over a field, enabling the computation of the greatest common divisor (GCD) in polynomial rings such as k, where k is a field.[21] This algorithm mirrors the process for integers but operates on polynomial degrees instead of absolute values, ensuring termination due to the decreasing degree of remainders.[22]
The Euclidean algorithm proceeds by repeated applications of polynomial division: given polynomials f(x) and g(x) with \deg f \geq \deg g > 0, divide f(x) by g(x) to obtain quotient q(x) and remainder r(x) such that f(x) = q(x) g(x) + r(x) where \deg r < \deg g or r(x) = 0. Then, \gcd(f(x), g(x)) = \gcd(g(x), r(x)), and the process recurses on g(x) and r(x) until the remainder is zero; the last non-zero remainder is the GCD, unique up to multiplication by units (non-zero constants in the field).[21] This recursive division guarantees that the algorithm terminates in at most \deg f + 1 steps, as each remainder has strictly lower degree.[22]
The division algorithm underpinning this process ensures the uniqueness of the quotient and remainder pair for any f(x), g(x) in k, provided k is an integral domain, which holds for fields.[21] For instance, consider computing \gcd(x^2 - 1, x - 1) over the rationals: dividing x^2 - 1 by x - 1 yields quotient x + 1 and remainder 0, since (x + 1)(x - 1) = x^2 - 1, so the GCD is x - 1 (up to units).[22]
This framework applies specifically over fields, where the polynomial ring k is a Euclidean domain, facilitating unique factorization into irreducibles up to units and associates.[21] It extends more broadly to unique factorization domains, though the algorithmic efficiency relies on the division property.[22]
Pseudocode
Polynomial long division can be expressed algorithmically through pseudocode, providing a clear, step-by-step procedure suitable for implementation in programming languages. This representation assumes polynomials are encoded as lists of coefficients in descending order of degree, where the first element is the coefficient of the highest-degree term and trailing zeros are omitted. The algorithm computes the quotient and remainder such that f(x) = g(x) \cdot q(x) + r(x) with \deg(r) < \deg(g).[23]
The following pseudocode outlines the process:
function DividePoly(f_coeffs, g_coeffs):
if g_coeffs is empty or g_coeffs[0] == 0:
raise error "Division by zero polynomial"
r_coeffs = copy of f_coeffs // current remainder starts as dividend
initial_diff = length(f_coeffs) - length(g_coeffs)
if initial_diff >= 0:
q_coeffs = [0] * (initial_diff + 1) // quotient coefficients, descending order
else:
q_coeffs = [] // zero quotient
while length(r_coeffs) >= length(g_coeffs) and r_coeffs[0] != 0:
// Compute leading quotient term
lead_q = r_coeffs[0] / g_coeffs[0]
deg_diff = length(r_coeffs) - length(g_coeffs)
q_index = initial_diff - deg_diff
q_coeffs[q_index] = lead_q
// Subtract lead_q * g from r (aligned at leading terms)
for i from 0 to length(g_coeffs) - 1:
r_coeffs[i] -= lead_q * g_coeffs[i]
// Trim leading zeros from r_coeffs
while length(r_coeffs) > 0 and r_coeffs[0] == 0:
remove first element from r_coeffs
// If r_coeffs is empty, set to [0]
if r_coeffs is empty:
r_coeffs = [0]
// Trim leading zeros from q_coeffs
while length(q_coeffs) > 0 and q_coeffs[0] == 0:
remove first element from q_coeffs
if q_coeffs is empty:
q_coeffs = [0]
return q_coeffs, r_coeffs
function DividePoly(f_coeffs, g_coeffs):
if g_coeffs is empty or g_coeffs[0] == 0:
raise error "Division by zero polynomial"
r_coeffs = copy of f_coeffs // current remainder starts as dividend
initial_diff = length(f_coeffs) - length(g_coeffs)
if initial_diff >= 0:
q_coeffs = [0] * (initial_diff + 1) // quotient coefficients, descending order
else:
q_coeffs = [] // zero quotient
while length(r_coeffs) >= length(g_coeffs) and r_coeffs[0] != 0:
// Compute leading quotient term
lead_q = r_coeffs[0] / g_coeffs[0]
deg_diff = length(r_coeffs) - length(g_coeffs)
q_index = initial_diff - deg_diff
q_coeffs[q_index] = lead_q
// Subtract lead_q * g from r (aligned at leading terms)
for i from 0 to length(g_coeffs) - 1:
r_coeffs[i] -= lead_q * g_coeffs[i]
// Trim leading zeros from r_coeffs
while length(r_coeffs) > 0 and r_coeffs[0] == 0:
remove first element from r_coeffs
// If r_coeffs is empty, set to [0]
if r_coeffs is empty:
r_coeffs = [0]
// Trim leading zeros from q_coeffs
while length(q_coeffs) > 0 and q_coeffs[0] == 0:
remove first element from q_coeffs
if q_coeffs is empty:
q_coeffs = [0]
return q_coeffs, r_coeffs
This algorithm handles edge cases such as division by a zero polynomial by raising an error, and produces a constant or zero remainder when the degree condition is met. Coefficients are processed assuming descending order, with leading zeros trimmed iteratively to maintain efficiency.[23]
The time complexity of this implementation is O(n m), where n = \deg(f) and m = \deg(g), arising from up to n - m + 1 iterations, each involving O(m) operations for multiplication and subtraction.[24]
This pseudocode is adaptable to computer algebra systems; for instance, SymPy's div function implements polynomial division over various domains, returning quotient and remainder while handling descending coefficient order and zero divisors via exceptions. Similarly, Mathematica's PolynomialQuotientRemainder performs the division, supporting univariate cases with automatic remainder computation when the degree condition holds.[25][26]
Applications
Factoring polynomials
Polynomial long division is essential in the factoring process for polynomials with rational coefficients, as it enables the systematic decomposition into lower-degree factors by verifying potential divisors and obtaining exact quotients when divisions are exact. The method leverages the Rational Root Theorem to identify candidate linear factors, which are then tested via division to reduce the polynomial's degree iteratively.[27]
The Rational Root Theorem posits that if a polynomial f(x) = a_n x^n + \cdots + a_0 with integer coefficients has a rational root p/q in lowest terms, then p divides the constant term a_0 and q divides the leading coefficient a_n.[28] Possible rational roots are thus enumerated from these factors, and for each candidate r, long division by the linear polynomial x - r is performed. If the remainder is zero, x - r is a factor, and the resulting quotient polynomial, of degree one less than the original, is factored further using the same approach.[29] This process relies on the polynomial division algorithm, which ensures a unique quotient and remainder for any divisor.[30]
For example, to factor x^3 - 6x^2 + 11x - 6, the Rational Root Theorem suggests possible rational roots \pm 1, 2, 3, 6. Testing x = 1 gives f(1) = 0, confirming it as a root. Long division by x - 1 yields the quotient x^2 - 5x + 6, which factors as (x - 2)(x - 3), so the full factorization over the rationals is (x - 1)(x - 2)(x - 3).[31]
If testing all possible linear factors yields no exact divisions, the polynomial has no rational linear factors. In such cases, for degrees greater than three, one may attempt factorization into quadratic factors by proposing a quadratic divisor (often guided by assuming integer coefficients and solving for them) and using long division to check for a zero remainder.[32] The iterative application of long division continues on any resulting quotients until the polynomial is expressed as a product of irreducible factors over the rationals—linear factors for roots or quadratic factors with negative discriminant.[27]
Root finding and synthetic division
The remainder theorem states that for a polynomial f(x) and a constant c, the remainder when f(x) is divided by x - c is f(c).[1] Consequently, c is a root of f(x) if and only if the remainder is zero, meaning x - c is a factor of f(x).[17]
Synthetic division provides an efficient method to apply the remainder theorem by evaluating f(c) and obtaining the quotient when dividing by x - c, particularly for polynomials with integer coefficients.[33] This technique is especially useful in root finding, where potential rational roots are tested from the list of candidates given by the rational root theorem: for a polynomial f(x) = a_n x^n + \cdots + a_0 with integer coefficients, any rational root p/q (in lowest terms) satisfies p dividing a_0 and q dividing a_n.[34] To test a candidate c, synthetic division is performed using the coefficients of f(x); a zero remainder confirms c as a root and yields the quotient polynomial for further analysis.[28]
For example, consider the polynomial f(x) = x^3 - 3x^2 - 4x + 12. The rational root theorem suggests possible rational roots \pm 1, \pm 2, \pm 3, \pm 4, \pm 6, \pm 12. Testing c = 2:
2 | 1 -3 -4 12
| 2 -2 -12
-----------------
1 -1 -6 0
2 | 1 -3 -4 12
| 2 -2 -12
-----------------
1 -1 -6 0
The remainder is 0, confirming that 2 is a root and x - 2 is a factor; the quotient is x^2 - x - 6.[17]
Once a root is found, deflation reduces the polynomial's degree by dividing out the linear factor, allowing repeated application of synthetic division to identify additional roots of the quotient.[1] This process continues until the polynomial is fully factored into linear and irreducible components over the rationals.[28]
Curve tangents
Polynomial long division provides an algebraic method to determine the tangent line to a curve defined by a polynomial equation at a specified point, without relying on the formal rules of calculus. For an explicit polynomial curve y = p(x), where p(x) is a polynomial of degree at least 1, the tangent at a point (a, p(a)) touches the curve with multiplicity at least 2. To find the slope m, perform long division of p(x) - p(a) by (x - a), yielding a quotient polynomial q(x). The slope is then m = q(a), as this represents the first-order approximation of the difference quotient.[35]
This approach extends to the equation of the tangent line, given by y - p(a) = m (x - a). For higher-order contact, dividing p(x) by (x - a)^2 produces a remainder that is the linear tangent polynomial mx + b, where b = p(a) - m a, confirming the line's form directly from the division.[35]
Consider the example of the cubic curve y = x^3 - 3x at the point (1, -2). First, compute p(1) = -2. Divide x^3 - 3x + 2 by (x - 1) using long division:
\begin{array}{r|r}
x - 1 & x^3 + 0x^2 - 3x + 2 \\
& \quad x^2 + x - 2 \\
\hline
& \quad x^3 - x^2 \\
& \quad \quad x^2 - x \\
& \quad \quad \quad x - 2 \\
& \quad \quad \quad x - 1 \\
& \quad \quad \quad \quad 1 \\
\end{array}
The quotient is q(x) = x^2 + x - 2, so m = q(1) = 1 + 1 - 2 = 0. The tangent line is y + 2 = 0(x - 1), or y = -2, which is horizontal and touches the curve at the local maximum.[35]
For implicit curves defined by f(x, y) = 0, such as circles or conics, similar algebraic techniques ensure the tangent line intersects the curve with a double root at the point of tangency.[36]
This algebraic technique for tangents originated in the 17th century, predating the formalization of calculus, and was employed by René Descartes to approximate tangents to algebraic curves through elimination and root multiplicity analysis, avoiding limits.[36]
Cyclic redundancy checks
Cyclic redundancy checks (CRCs) employ polynomial long division over the finite field GF(2) to generate error-detecting codes in digital communication systems. In this context, the message to be transmitted is represented as a polynomial whose coefficients are bits (0 or 1), and division is performed using modulo-2 arithmetic, where subtraction is equivalent to addition via XOR operations. The CRC value is the remainder obtained when this message polynomial, shifted by appending zeros, is divided by a fixed generator polynomial of degree k, ensuring the transmitted frame is divisible by the generator and thus detectable for errors at the receiver.[37]
The computation process begins by appending k zeros to the message polynomial, where k is one less than the degree of the generator polynomial, effectively multiplying the message by x^k. This augmented polynomial is then divided by the generator using long division adapted for GF(2), yielding a quotient (discarded) and a remainder of degree less than k. The remainder serves as the CRC checksum, which is XORed with the appended zeros and attached to the original message for transmission. At the receiver, the entire received frame is divided by the same generator; a zero remainder confirms integrity, while a nonzero remainder indicates errors. This method leverages the division algorithm efficiently due to the binary nature of GF(2).[38]
For example, consider a generator polynomial g(x) = x^3 + x + 1, represented in binary as 1011 (degree 3, so k=3). For a message 1001101 (polynomial x^6 + x^4 + x^3 + 1), append three zeros to get 1001101000. Performing mod-2 long division:
- The leading term x^6 divided by x^3 gives x^3; multiply generator by x^3 (1011 shifted left by 3: 1011000) and XOR with the current dividend portion.
- Continue shifting and XORing for each step, resulting in a remainder of 101 after processing all bits.
The transmitted frame is then 1001101101, and the CRC checksum is 101.[38]
Key properties of CRCs stem from this division: they detect all burst errors of length up to the generator degree k, all single-bit errors (if the generator has at least two terms), and certain multi-bit errors depending on the generator's irreducibility. The use of polynomial division in GF(2) ensures computational efficiency, as operations simplify to bitwise XORs. In practice, this division is often implemented using linear feedback shift registers (LFSRs), which mimic the synthetic division process by shifting bits through XOR gates configured to the generator polynomial's taps, enabling high-speed hardware realization akin to synthetic division for polynomials.[39][38]
CRCs are standardized in numerous protocols, such as Ethernet's CRC-32 in IEEE 802.3, which uses the generator x^{32} + x^{26} + x^{23} + x^{22} + x^{16} + x^{12} + x^{11} + x^{10} + x^8 + x^7 + x^5 + x^4 + x^2 + x + 1 for robust error detection in frame transmission.[40]