In algebra, synthetic division is a method for manually performing Euclidean division of polynomials, with less writing and fewer calculations than long division.

It is mostly taught for division by linear monic polynomials (known as Ruffini's rule), but the method can be generalized to division by any polynomial.

The advantages of synthetic division are that it allows one to calculate without writing variables, it uses few calculations, and it takes significantly less space on paper than long division. Also, the subtractions in long division are converted to additions by switching the signs at the very beginning, helping to prevent sign errors.

Regular synthetic division 
The first example is synthetic division with only a monic linear denominator .

The numerator can be written as .

The zero of the denominator  is .

The coefficients of  are arranged as follows, with the zero of  on the left: 

The  after the bar is "dropped"  to the last row.

The  is multiplied by the  before the bar, and placed in the .

An  is performed in the next column.

The previous two steps are repeated and the following is obtained:

Here, the last term (-123) is the remainder while the rest correspond to the coefficients of the quotient. 
 
The terms are written with increasing degree from right to left beginning with degree zero for  the remainder and the result.

Hence the quotient and remainder are:

Evaluating polynomials by the remainder theorem

The above form of synthetic division is useful in the context of the polynomial remainder theorem for evaluating univariate polynomials. To summarize, the value of  at  is equal to the remainder of the division  of  by 

The advantage of calculating the value this way is that it requires just over half as many multiplication steps as naive evaluation. An alternative evaluation strategy is Horner's method.

Expanded synthetic division 
This method generalizes to division by any monic polynomial with only a slight modification with changes in bold.  Using the same steps as before,  perform the following division:

We concern ourselves only with the coefficients.
Write the coefficients of the polynomial to be divided at the top.

Negate the coefficients of the divisor. 

Write in every coefficient but the first one on the left in an upward right diagonal (see next diagram).

Note the change of sign from  1 to −1 and from −3 to 3 . "Drop" the first coefficient after the bar to the last row.

Multiply the dropped number by the diagonal before the bar, and place the resulting entries diagonally to the right from the dropped entry.

Perform an addition in the next column.

Repeat the previous two steps until you would go past the entries at the top with the next diagonal.

Then simply add up any remaining columns.

Count the terms to the left of the bar.  Since there are two, the remainder has degree one and this is the two right-most terms under the bar. Mark the separation with a vertical bar.

 
The terms are written with increasing degree from right to left beginning with degree zero for both the remainder and the result.

The result of our division is:

For non-monic divisors 

With a little prodding, the expanded technique may be generalised even further to work for any polynomial, not just monics. The usual way of doing this would be to divide the divisor  with its leading coefficient (call it a):

then using synthetic division with  as the divisor, and then dividing the quotient by a to get the quotient of the original division (the remainder stays the same). But this often produces unsightly fractions which get removed later, and is thus more prone to error. It is possible to do it without first reducing the coefficients of .

As can be observed by first performing long division with such a non-monic divisor, the coefficients of  are divided by the leading coefficient of  after "dropping", and before multiplying.

Let's illustrate by performing the following division:

A slightly modified table is used:

Note the extra row at the bottom. This is used to write values found by dividing the "dropped" values by the leading coefficient of  (in this case, indicated by the /3; note that, unlike the rest of the coefficients of , the sign of this number is not changed).

Next, the first coefficient of  is dropped as usual:

and then the dropped value is divided by 3 and placed in the row below:

Next, the new (divided) value is used to fill the top rows with multiples of 2 and 1, as in the expanded technique:

The 5 is dropped next, with the obligatory adding of the 4 below it, and the answer is divided again:

Then the 3 is used to fill the top rows:

At this point, if, after getting the third sum, we were to try and use it to fill the top rows, we would "fall off" the right side, thus the third sum is the first coefficient of the remainder, as in regular synthetic division. But the values of the remainder are not divided by the leading coefficient of the divisor:

Now we can read off the coefficients of the answer. As in expanded synthetic division, the last two values (2 is the degree of the divisor) are the coefficients of the remainder, and the remaining values are the coefficients of the quotient:

and the result is

Compact Expanded Synthetic Division 

However, the diagonal format above becomes less space-efficient when the degree of the divisor exceeds half of the degree of the dividend. Consider the following division:

It is easy to see that we have complete freedom to write each product in any row as long as it is in the correct column, so the algorithm can be compactified by a greedy strategy, as illustrated in the division below:

The following describes how to perform the algorithm; this algorithm includes steps for dividing non-monic divisors:

Python implementation 

The following snippet implements Expanded Synthetic Division in Python for arbitrary univariate polynomials:

def expanded_synthetic_division(dividend, divisor):
    """Fast polynomial division by using Expanded Synthetic Division. 
    Also works with non-monic polynomials.

    Dividend and divisor are both polynomials, which are here simply lists of coefficients. 
    E.g.: x**2 + 3*x + 5 will be represented as [1, 3, 5]
    """
    out = list(dividend)  # Copy the dividend
    normalizer = divisor[0]
    for i in range(len(dividend) - len(divisor) + 1):
        # For general polynomial division (when polynomials are non-monic),
        # we need to normalize by dividing the coefficient with the divisor's first coefficient
        out[i] /= normalizer

        coef = out[i]
        if coef != 0:  # Useless to multiply if coef is 0
            # In synthetic division, we always skip the first coefficient of the divisor,
            # because it is only used to normalize the dividend coefficients
            for j in range(1, len(divisor)):
                out[i + j] += -divisor[j] * coef

    # The resulting out contains both the quotient and the remainder,
    # the remainder being the size of the divisor (the remainder
    # has necessarily the same degree as the divisor since it is
    # what we couldn't divide from the dividend), so we compute the index
    # where this separation is, and return the quotient and remainder.
    separator = 1 - len(divisor)
    return out[:separator], out[separator:]  # Return quotient, remainder.

See also
Euclidean domain
Greatest common divisor of two polynomials
Gröbner basis
Horner scheme
Polynomial remainder theorem
Ruffini's rule

References

External links

Computer algebra
Division (mathematics)
Polynomials
조립제법(組立除法, Synthetic division)이란 다항식을 내림차순으로 정리하여 계수들만 표기하는 간단한 계수들의 조립에서 간단한 곱셈과 덧셈으로만 이루어지는 적은 계산을 통해  다항식의 긴 나눗셈(Polynomial long division)을 보다 효율적이고 간단하게 수행하는 방법이다.

어떤 다항식을 특별히 일차식으로 나눗셈을 할 경우,Ruffini의 규칙(Ruffini's rule)이라 한다.이 규칙은 나누는 수(일차식)의 상수항의 부호에 (-1)을 곱하여 그 수를 중심으로 삼아, 뺄셈을 덧셈과 곱셈형식으로 전환시키는 원리를 지니고있다. 이 원리를 토대로 조립제법은 직접하는 다항식의 나눗셈의 뺄셈과정보다 더 익숙한 덧셈과 곱셈과정만으로 답을 추구할 수 있다는 의의를 지니고 있다.

이 부분에서 정의한 조립제법은 최고차항의 계수가 1인 다항식으로 나눌 때만 가능하다. 따라서 최고차항의 계수가 1이 아닌 경우는 1로 변형하여 조립제법을 한 다음, 구해진 몫의 계수를 조정하는 별도의 계산이 필요할 수 밖에 없다. 예를 들어서 최고차항의 계수가 2일 경우에는 그 식을 2로 나눠서 조립제법을 한 다음, 그 몫의 검산식의 양변에 2를 곱해주는 것이다.

조립제법의 뜻 풀이

조립제법(Synthetic division)을 영어로 직역하면 (종합적으로) 합성한 나눗셈을 의미하는데, 이는 나누어지는 다항식(피제수)의 각 항들을 내림차순으로 정리하여 계수들만 정렬시키고, 나눌 다항식(제수)의 상수항에 (-1)을 곱함으로써 부호를 바꾼 항을 왼쪽 칸에 배열시켜 계수들을 합성시키는 이 과정에 초점을 맞춰이름을 지었다고 할 수 있다.

조립제법(組立除法)은 Synthetic division를 한자어로 번역한 것으로, 의미는 대체적으로 같다. 피제수와 제수의 각 계수들을 특정하게 배열(組)하여 알맞게 조립제법의 형태를 세우고(立) 이 형식으로 나눗셈을 수행하는 것(除)을 의미한다.

조립제법의 이름은 조립제법을 하는 방법에 초점을 두어 정의되었다. 무엇보다 간편한 나눗셈을 수행하기 위해, 조립제법을 하는 방법을 강조하고있는데에 초점을 둔 것이다.

일차항 계수가 1인 일차식으로 나누기의 예 
다음 나눗셈을 수행하려고 한다.

먼저 피제수의 모든 계수를 내림차순으로 쓴다. 이때, 보이지 않는 항까지 모두 써야 한다. (이 예에서는 일차식의 계수에 해당한다)

제수의 계수의 부호를 바꾼다.

제수의 최고차항을 제외한 나머지 계수를 세로줄의 왼쪽에 쓴다.

첫 번째 계수는 그대로 내려온다.

그 다음 맨 좌측선 너머에 쓴 수(여기서는 3)와 내려온 계수를 곱하여 그 피제수의 다음 계수 아래쪽에 쓴다.

같은 열에 위치한 가로선 위쪽의 이 값을 더하여 가로선 아래쪽에 쓴다.

이전의 두 단계를 반복하여 마지막까지 쓴다.

일차식으로 나누었으므로, 가로줄 아래쪽에 나열된 수 중에서 가장 우측의 수는 나머지를 의미하고, 나머지 수들은 내림차순으로 몫의 계수들을 의미하게 된다. 그리하여 나눗셈의 결과는 다음과 같음을 알 수 있다.

일차항 계수가 1이 아닌 일차식으로 나누기의 예 
다음 나눗셈을 수행하려고 한다.

먼저 피제수의 모든 계수를 내림차순의 순서로 쓴다. 이때, 보이지 않는 항까지 모두 써야 한다. (이 예에서는 일차식의 계수에 해당한다)

나누는 식의 상수항을 반대 부호로 하여 세로줄의 왼쪽에 쓴다.
나누는 식의 최고차항 계수 2는 부호를 바꾸지 않고 나누기 기호 /를 그 좌측에 붙여서(즉 /2 기호로 히여) 가로줄 밑, 세로줄 바로 좌측에 적어준다.

첫 번째 계수는 그대로 내려온다. 그대로 내려온 것을 2로 나누어(즉 /2 하여) 그 밑에 적는다.

앞에서 마지막에 적었던 1/2에 3을 곱하여 다음 열의 가로줄 바로 위에 적어 준다.

방금 적었던 3/2은 그 위의 -12와 합한 값을 가로 줄 바로 밑에 적어 주고, 또 이를 /2 하여 또 바로 그 밑에 적어준다.

앞에서 마지막에 적었던 -21/4에 3을 곱하여 다음 열의 가로줄 바로 위에 적어 준다.

방금 적었던 -63/4은 그 위의 0과 합한 값을 가로 줄 바로 밑에 적어 주고, 또 이를 /2 하여 또 바로 그 밑에 적어준다.

이전의 단계를 계속 반복한다. 마지막 단계에서는 /2(나누기 2)를 하지 않는다.

일차식 2x - 3으로 나누었으므로, 수평줄 바로 아래쪽에 나열된 수 중에서 가장 우측의 수 -525/8은 나머지를 의미하고, 수평줄의 아래 아래에 놓인 수들(즉 가장 밑에 놓인 수들)은 몫의 내림차순 계수들을 의미하게 된다. 그리하여 나눗셈의 결과는 다음과 같음을 알 수 있다.

최고차항 계수가 1인 이차식으로 나누는 조립제법의 예 
이러한 조립제법은 제수의 차수가 더 높은 경우에도 사용가능하다. 다음의 예제를 살펴보자.

먼저 피제수의 계수를 모두 쓴다.

제수의 계수의 부호를 바꾼다.

제수의 최고차항을 제외한 나머지 계수들을 대각선 방향으로 써 내려간다.

피제수의 첫 번째 계수는 그대로 내려온다.

내려간 계수는 좌측의 값과 곱하여 대각선 위로 올라간다.

가로선 위쪽의 같은 열의 수들을 세로로 더해서 가로선 아래쪽에 쓴다.

이전의 두 단계를 반복하여 끝까지 계산한다.

마지막 부분을 더해서 아래쪽에 쓴다.

이차식으로 나누었으므로, 가로줄 아래쪽에 나열된 수 중에서 우측 두 수는 나머지의 계수를 의미하고, 나머지 수들은 내림차순으로 몫의 계수들을 의미하게 된다. 그리하여 나눗셈의 결과는 다음과 같음을 알 수 있다.

만약 최고차항의 계수가 1이 아닌 이차식의 경우 맨 앞에서 서술한 대로 적절한 수를 곱해서 제수의 최고차항의 계수를 1로 만들어줘야 한다.

같이 보기 
 다항식 장제법

각주

외부 링크 
 

기호 계산
나눗셈
대수학