대수학(algebra)에서, 다항식 긴 나눗셈(polynomial long division)은 하나의 다항식(Polynomial)을 같거나 낮은 차수(degree)의 다른 다항식으로 나눌 수 있는 알고리듬(algorithm)으로써, 긴 나눗셈(long division)이라고 불리는 익숙한 산술 기법의 일반화된 버전입니다. 복잡한 나눗셈 문제를 작은 문제로 분리하기 때문에, 손으로 쉽게 할 수 있습니다. 때때로 조립 제법(synthetic division)이라고 불리는 속기 버전을 사용하는 것이, 쓰는 것도 적고 계산도 줄어서, 더 빠릅니다.
다항식 긴 나눗셈은 다항식의 유클리드 나눗셈(Euclidean division of polynomials)을 구현하는 알고리듬으로, 두 다항식 A (피제수(dividend))와 B (제수(divisor))에서 시작하여, 만약 B가 영이 아니면, 표현
\(\quad\)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인 단항식을 포함합니다):
\(\quad\)\(x^3 - 2x^2 + 0x - 4.\)
몫과 나머지는, 그럼 다음, 다음 과정을 거쳐 구해질 수 있습니다:
1. 나누어지는 식의 첫 번째 항을 나누는 식의 최고차 항(x의 가장 큰 거듭제곱을 가진 것을 의미하는데, 이 경우에서 x)으로 나눕니다. 결과를 막대 위에 씁니다 (\(x^3 \div x = x^2\)).
\(\quad\)\(
\begin{array}{l}
{\color{White} x-3 ) x^3 - 2}x^2\\
x-3\overline{) x^3 - 2x^2 + 0x - 4}
\end{array}
\)
2. 방금 얻은 결과(최종 몫의 첫 번째 항)에 나누는 식을 곱합니다. 나누어지는 식의 처음 두 항 아래에 결과를 씁니다 (\(x^2 \cdot (x-3) = x^3-3x^2\)).
\(\quad\)\(
\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}
\)
3. 원래 나누어지는 식의 적절한 항으로부터 방금 얻은 곱을 빼고 (이때, 음의 부호를 가진 것을 빼는 것은 양의 부호를 가진 것을 더하는 것과 같음에 주의해야 합니다), 아래에 결과를 씁니다 (\((x^3-2x^2)-(x^3-3x^2)=-2x^2+3x^2=x^2). 그런 다음, 나누어지는 식으로부터 다음 항을 "가져와서 쓰십시오".
\(\quad\)\(
\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}
\)
4. 이전 세 과정을 반복하십시오, 이번에는 나누어지는 식으로 바로 직전에 쓰인 두 항을 사용하십시오.
\(\quad\)\(
\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}
\)
5. 단계 4를 반복하십시오. 이번에는, "가져와서 쓸 것"이 없습니다.
\(\quad\)\(
\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)입니다.
\(\quad\)\({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의 방법은 위의 긴 부분을 축약한 버전입니다. 이 연필-과-종이 방법은 다항식 긴 나눗셈과 동일한 알고리듬을 사용하지만, 나머지를 결정하기 위해 암기로 하는 계산(mental calculation:암산)이 사용됩니다. 이것은 적은 쓰기를 요구하고, 따라서 일단 숙달되면 더 빠른 방법이 될 수 있습니다.
나눗셈은 처음에 긴 곱셈과 비슷한 방식으로, 맨 위에 나누어지는 식을 적고 그 아래에 나누는 식을 씁니다. 몫은 왼쪽에서 오른쪽으로 막대 아래에 쓰일 것입니다.
\(\begin{matrix} \qquad \qquad x^3-2x^2+{0x}-4 \\ \underline{ \div \quad \qquad \qquad \qquad \qquad x-3 }\end{matrix}\)
나누어지는 식의 첫 번째 항을 나누는 식의 최고차 항으로 나누세요 (\(x^3\div x =x^2\)). 결과를 막대 아래에 쓰십시오. \(x^3\)은 나머지를 남기지 않고 나누어지므로, 따라서 백슬래시와 함께 사용된 것으로 표시할 수 있습니다. 결과 \(x^2\)은 그런 다음 나누어지는 식의 두 번째 항 -3에 곱하십시오 \(= -3x^2\)입니다. \(-2x^2-(-3x^2)=x^2\)를 빼서 부분 나머지를 결정하십시오. \(-2x^2\)를 사용된 것으로 표시하고 새로운 나머지 \(x^2\)를 그것 위에 쓰십시오.
\(\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^2 \div x = x\)). 막대 아래에 결과 (+x)를 쓰십시오. \(x^2\)은 나머지를 남기지 않고 나누어졌고, 따라서 사용된 것으로 표시될 수 있습니다. 결과 x는 그런 다음 나누는 식의 두 번째 항 -3 에 곱하십시오 = -3x입니다. 0x-(-3x) = 3x를 빼서 부분 나머지를 결정하십시오. 0x를 사용된 것으로 표시하고 새로운 나머지 3x 그것 위에 쓰십시오.
\(\begin{matrix} \qquad \qquad \quad\bcancel x^2 \quad3x\\ \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} \quad5\\ \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를 제공합니다:
\(\quad\)\(A=BQ+R,\)
그리고 R=0 또는 차수(R) < 차수(B)입니다. 게다가 (Q, R)은 이 속성을 가지는 다항식의 고유한 쌍입니다.
A와 B로부터 고유하게 정의된 다항식 Q와 R을 얻는 과정은 유클리드 나눗셈(Euclidean division) (때때로 나눗셈 변환(division transformation))이라고 불립니다. 다항식 긴 나눗셈은 따라서 유클리드 나눗셈에 대해 하나의 알고리듬(algorithm)입니다.
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^2-(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) 직선의 방정식을 찾기 위해 사용될 수 있습니다. 만약 R(x)가 P(x)를 \((x-r)^2\)으로 나눈 나머지이면, 함수 y = P(x)의 그래프에 x = r에서 접선의 방정식은, r이 다항식의 근인지 여부에 상관없이, y = R(x)입니다.
Example
\(x=1\)에서 다음 곡선에 접하는 직선의 방정식을 구하십시오:
\(\quad\)\(y = x^3 - 12x^2 - 42.\)
다항식을 \((x-1)^2 = x^2-2x+1\)로 나누십시오:
\(\quad\)\(\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 = - 21 x - 32\)입니다.
Cyclic redundancy check
순환 중복 검사(cyclic redundancy check)는 전송된 메시지의 오류를 발견하기 위해 다항식 나눗셈의 나머지를 사용합니다.