Polynomial long division

대수학(algebra)에서, 다항식 긴 나눗셈(polynomial long division)은 하나의 다항식(Polynomial)을 같거나 낮은 차수(degree)의 다른 다항식으로 나눌 수 있는 알고리듬(algorithm)으로써, 긴 나눗셈(long division)이라고 불리는 익숙한 산술 기법의 일반화된 버전입니다. 복잡한 나눗셈 문제를 작은 문제로 분리하기 때문에, 손으로 쉽게 할 수 있습니다. 때때로 조립 제법(synthetic division)이라고 불리는 속기 버전을 사용하는 것이, 쓰는 것도 적고 계산도 줄어서, 더 빠릅니다.

다항식 긴 나눗셈은 다항식의 유클리드 나눗셈(Euclidean division of polynomials)을 구현하는 알고리듬으로, 두 다항식 A (피제수(dividend))와 B (제수(divisor))에서 시작하여, 만약 B가 영이 아니면, 표현

A = BQ + R,

및 R = 0 또는 R의 차수는 B의 차수보다 낮은 것을 만족하는 몫(quotient) Q와 나머지(remainder) R을 생성합니다. 이들 조건은 Q와 R을 고유하게 정의하며, 이것은 Q와 R이 그들을 계산하기 위해 사용된 방법에 의존하지 않음을 의미합니다.

결과 R=0이 발생하는 것과 다항식 A가 B를 인수(factor)로 갖는 것은 필요충분(iff) 조건입니다. 따라서, 긴 나눗셈은 하나의 다항식이 다른 다항식을 하나의 인수로 갖는지 여부를 테스트하기 위한 방법이고, 만약 그렇다면, 그것을 인수화하기 위한 방법입니다. 예를 들어, 만약 A의 근(root) r이 알려지면, A를 (x–r)로 나눔으로써 인수화될 수 있습니다.

Example

Polynomial long division

나누어지는 식(dividend:피제수) $x^{3}-2x^{2}-4$ 을 나누는 식(divisor:제수) $x-3$ 에 의한 나눗셈의 몫과 나머지를 구해 보겠습니다.

나누어지는 식을 다음처럼 다시 씁니다 (이때, 모든 차수가 표현되도록, 계수가 0인 단항식을 포함합니다):

x^{3}-2x^{2}+0x-4.

몫과 나머지는, 그럼 다음, 다음 과정을 거쳐 구할 수 있습니다:

나누어지는 식의 첫 번째 항을 나누는 식의 최고차 항(x의 가장 큰 거듭제곱을 가진 것을 의미하는데, 이 경우에서 x)으로 나눕니다. 결과를 막대 위에 씁니다 (x³ ÷ x = x²).
${\begin{array}{l}{\color {White}x-3)x^{3}-2}x^{2}\\x-3{\overline {)x^{3}-2x^{2}+0x-4}}\end{array}}$
방금 얻은 결과(최종 몫의 첫 번째 항)에 나누는 식을 곱합니다. 나누어지는 식의 처음 두 항 아래에 결과를 씁니다 ( $x 2 \cdot (x - 3) = x 3 - 3 x 2$ ).
${\begin{array}{l}{\color {White}x-3)x^{3}-2}x^{2}\\x-3{\overline {)x^{3}-2x^{2}+0x-4}}\\{\color {White}x-3)}x^{3}-3x^{2}\end{array}}$
원래 나누어지는 식의 적절한 항으로부터 방금 얻은 곱을 빼고 (이때, 음의 부호를 가진 것을 빼는 것은 양의 부호를 가진 것을 더하는 것과 같음에 주의해야 합니다), 아래에 결과를 씁니다 ( $(x 3 - 2 x 2) - (x 3 - 3 x 2) = -2 x 2 + 3 x 2 = x 2$ ). 그런 다음, 나누어지는 식으로부터 다음 항을 "가져와서 쓰십시오".
${\begin{array}{l}{\color {White}x-3)x^{3}-2}x^{2}\\x-3{\overline {)x^{3}-2x^{2}+0x-4}}\\{\color {White}x-3)}{\underline {x^{3}-3x^{2}}}\\{\color {White}x-3)0x^{3}}+{\color {White}}x^{2}+0x\end{array}}$
이전 세 과정을 반복하십시오, 이번에는 나누어지는 식으로 바로 직전에 쓰인 두 항을 사용하십시오.
${\begin{array}{r}x^{2}+{\color {White}1}x{\color {White}{}+3}\\x-3{\overline {)x^{3}-2x^{2}+0x-4}}\\{\underline {x^{3}-3x^{2}{\color {White}{}+0x-4}}}\\+x^{2}+0x{\color {White}{}-4}\\{\underline {+x^{2}-3x{\color {White}{}-4}}}\\+3x-4\\\end{array}}$
단계 4를 반복하십시오. 이번에는, "가져와서 쓸 것"이 없습니다.
${\begin{array}{r}x^{2}+{\color {White}1}x+3\\x-3{\overline {)x^{3}-2x^{2}+0x-4}}\\{\underline {x^{3}-3x^{2}{\color {White}{}+0x-4}}}\\+x^{2}+0x{\color {White}{}-4}\\{\underline {+x^{2}-3x{\color {White}{}-4}}}\\+3x-4\\{\underline {+3x-9}}\\+5\end{array}}$

막대 위의 다항식은 몫 q(x)이고, 남겨진 숫자 (5)는 나머지 r(x)입니다.

{x^{3}-2x^{2}-4}=(x-3)\,\underbrace {(x^{2}+x+3)} _{q(x)}+\underbrace {5} _{r(x)}

산술에 대해 긴 나눗셈(long division) 알고리듬은 위의 알고리듬과 매우 비슷한데, 변수 x는, 산술의 긴 나눗셈에서, 특정 숫자 10에 의해 대체됩니다.

Polynomial short division

Blomqvist의 방법^[1]은 위의 긴 부분을 축약한 버전입니다. 이 연필-과-종이 방법은 다항식 긴 나눗셈과 동일한 알고리듬을 사용하지만, 나머지를 결정하기 위해 암기로 하는 계산(mental calculation:암산)이 사용됩니다. 이것은 적은 쓰기를 요구하고, 따라서 일단 숙달되면 더 빠른 방법이 될 수 있습니다.

나눗셈은 처음에 긴 곱셈과 비슷한 방식으로, 맨 위에 나누어지는 식을 적고 그 아래에 나누는 식을 씁니다. 몫은 왼쪽에서 오른쪽으로 막대 아래에 쓰일 것입니다.

${\begin{matrix}\qquad \qquad x^{3}-2x^{2}+{0x}-4\\{\underline {\div \quad \qquad \qquad \qquad \qquad x-3}}\end{matrix}}$

나누어지는 식의 첫 번째 항을 나누는 식의 최고차 항으로 나누세요 (x³ ÷ x = x²). 결과를 막대 아래에 쓰십시오. x³은 나머지를 남기지 않고 나누어지므로, 따라서 백슬래시와 함께 사용된 것으로 표시할 수 있습니다. 결과 x²은 그런 다음 나누어지는 식의 두 번째 항 -3에 곱하십시오 = -3x²입니다. -2x²-(-3x²) = x²를 빼서 부분 나머지를 결정하십시오. -2x²를 사용된 것으로 표시하고 새로운 나머지 x²를 그것 위에 쓰십시오.

${\begin{matrix}\qquad x^{2}\\\qquad \quad {\bcancel {x}}^{3}+{\bcancel {-2}}x^{2}+{0x}-4\\{\underline {\div \qquad \qquad \qquad \qquad \qquad x-3}}\\x^{2}\qquad \qquad \end{matrix}}$

나머지의 최고차 항을 나누는 식의 최고차 항으로 나누세요 (x² ÷ x = x). 막대 아래에 결과 (+x)를 쓰십시오. x²은 나머지를 남기지 않고 나누어졌고, 따라서 사용된 것으로 표시될 수 있습니다. 결과 x는 그런 다음 나누는 식의 두 번째 항 -3 에 곱하십시오 = -3x입니다. 0x-(-3x) = 3x를 빼서 부분 나머지를 결정하십시오. 0x를 사용된 것으로 표시하고 새로운 나머지 3x 그것 위에 쓰십시오.

${\begin{matrix}\qquad \qquad \quad {\bcancel {x}}^{2}\quad 3x\\\qquad \quad {\bcancel {x}}^{3}+{\bcancel {-2}}x^{2}+{\bcancel {0x}}-4\\{\underline {\div \qquad \qquad \qquad \qquad \qquad x-3}}\\x^{2}+x\qquad \end{matrix}}$

나머지 식의 최고차 항을 나누는 식의 최고차 항으로 나누세요 (3x ÷ x = 3). 막대 아래에 결과 (+3)을 쓰십시오. 3x는 나머지를 남기지 않으므로, 따라서 나뉘어 사용된 것으로 표시될 수 있습니다. 결과 3에 그런 다음 나누는 식의 두 번째 항 -3에 곱하십시오 = -9입니다. -4-(-9) = 5을 빼서 부분 나머지를 결정하십시오. 사용된 것으로 -4를 표시하고 새로운 나머지 5를 그것 위에 쓰십시오.

${\begin{matrix}\quad \qquad \qquad \qquad {\bcancel {x}}^{2}\quad {\bcancel {3x}}\quad 5\\\qquad \quad {\bcancel {x}}^{3}+{\bcancel {-2}}x^{2}+{\bcancel {0x}}{\bcancel {-4}}\\{\underline {\div \qquad \qquad \qquad \qquad \qquad x-3}}\\x^{2}+x+3\qquad \end{matrix}}$

막대 아래의 다항식은 몫 q(x)이고, 위에 남은 수 (5)는 나머지 r(x)입니다.

Pseudocode

알고리듬은 다음으로 유사-코드(pseudocode) 표현될 수 있는데, 여기서 +, −, 및 ×는 다항식 산술을 표현하고 /는 두 항의 단순한 나눗셈을 표현합니다:

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)

이것은 차수(n) < 차수(d)일 때 동일하게 잘 작동하는 것에 주목하십시오; 해당 경우에서 결과는 단지 자명한 (0, n)입니다.

이 알고리듬은 위의 종이와 연필 방법을 정확하게 묘사합니다: d는 ")"의 왼쪽에 기록됩니다; q는 수평 직선 위에, 항별로 쓰이고, 마지막 항은 t의 값입니다; 수평 직선 아래의 영역은 r의 연속적인 값을 계산하고 쓰기 위해 사용됩니다.

Euclidean division

B ≠ 0을 만족하는 다항식 (A, B)의 모든 각 쌍에 대해, 다항식 나눗셈은 다음을 만족하는 몫 Q와 나머지 R를 제공합니다:

A=BQ+R,

그리고 R=0 또는 차수(R) < 차수(B)입니다. 게다가 (Q, R)은 이 속성을 가지는 다항식의 고유한 쌍입니다.

A와 B로부터 고유하게 정의된 다항식 Q와 R을 얻는 과정은 유클리드 나눗셈(Euclidean division) (때때로 나눗셈 변환(division transformation))이라고 불립니다. 다항식 긴 나눗셈은 따라서 유클리드 나눗셈에 대해 하나의 알고리듬(algorithm)입니다.^[2]

Applications

Factoring polynomials

때때로 다항식의 하나 이상의 근이 알려져 있습니다, 아마도 그것은 유리 근 정리(rational root theorem)를 사용하여 구할 수 있습니다. 만약 차수 n의 다항식 P(x)의 한 근 r이 알려져 있으면 다항식 긴 나눗셈은 P(x)를 형태 (x − r)(Q(x))으로 인수분해하기 위해 사용될 수 있습니다. 여기서 Q(x)는 차수 n – 1의 다항식입니다. Q(x)는 나눗셈 과정에서 얻은 단순한 몫입니다; r은 P(x)의 근으로 알려져 있기 때문에, 그것의 나머지는 반드시 0이어야 합니다.

마찬가지로, 만약 하나 이상의 근이 알려져 있으면, 그들 중 하나 (r)의 선형 인수 (x − r)는 Q(x)를 얻기 위해 원래 다항식 P(x)를 나눌 수 있고, 그런 다음 다른 근, s의 선형 항은 Q(x)를 나눌 수 있고, 이 과정을 계속할 수 있습니다. 대안적으로, 그것들은 모두 한 번에 나눌 수 있습니다: 예를 들어 선형 인수 x − r 및 x − s는 곱해서 이차 인수 x² − (r + s)x + rs를 얻을 수 있는데, 이것은 원래 다항식 P(x)를 나누어 차수 n − 2의 몫을 얻을 수 있습니다 (이때, 나머지는 0입니다).

이런 방법으로, 때때로 4보다 큰 차수의 다항식의 모든 근이, 비록 그것이 항상 가능하지는 않을지라도, 얻어질 수 있습니다. 예를 들어, 만약 유기 근 정리는 오차 다항식(quintic polynomial)의 하나의 (합리) 근을 구할 수 있다면, 그것은 차수 4의 몫을 구하기 위해 인수분해될 수 있습니다; 사차 다항식(quartic polynomial)의 근에 대해 명시적 공식은 사차의 다른 네 근을 찾기 위해 사용될 수 있습니다.

Finding tangents to polynomial functions

다항식 긴 나눗셈은 특정 점 x = r에서 다항식 P(x)로 정의된 함수의 그래프(graph of the function)에 접하는(tangent) 직선의 방정식을 찾기 위해 사용될 수 있습니다.^[3] 만약 R(x)가 P(x)를 (x – r)²으로 나눈 나머지이면, 함수 y = P(x)의 그래프에 x = r에서 접선의 방정식은, r이 다항식의 근인지 여부에 상관없이, y = R(x)입니다.

Example

x=1

에서 다음 곡선에 접하는 직선의 방정식을 구하십시오:

y=x^{3}-12x^{2}-42.

다항식을

(x-1)^{2}=x^{2}-2x+1

로 나누십시오:

{\begin{array}{r}x-10\\x^{2}-2x+1{\overline {)x^{3}-12x^{2}+0x-42}}\\{\underline {x^{3}-{\color {White}0}2x^{2}+{\color {White}1}x}}{\color {White}{}-42}\\-10x^{2}-{\color {White}01}x-42\\{\underline {-10x^{2}+20x-10}}\\-21x-32\end{array}}

접선은

y=-21x-32

입니다.

Cyclic redundancy check

순환 중복 검사(cyclic redundancy check)는 전송된 메시지의 오류를 발견하기 위해 다항식 나눗셈의 나머지를 사용합니다.

Notes

^ Blomqvist’s division: the simplest method for solving divisions?, retrieved 2019-12-10
^ S. Barnard (2008). Higher Algebra. READ BOOKS. p. 24. ISBN 1-4437-3086-6.
^ Strickland-Constable, Charles, "A simple method for finding tangents to polynomial graphs", Mathematical Gazette 89, November 2005: 466-467.

[1] Blomqvist’s division: the simplest method for solving divisions?, retrieved 2019-12-10

[2] S. Barnard (2008). Higher Algebra. READ BOOKS. p. 24. ISBN 1-4437-3086-6.

[3] Strickland-Constable, Charles, "A simple method for finding tangents to polynomial graphs", Mathematical Gazette 89, November 2005: 466-467.

[1]

[2]

[3]

Example

Polynomial long division

Polynomial short division

Pseudocode

Euclidean division

Applications

Factoring polynomials

Finding tangents to polynomial functions

Example

Cyclic redundancy check

See also

Notes