다항식 장제법

1. 개요

다항식 장제법은 다항식을 다른 다항식으로 나누어 몫과 나머지를 구하는 방법이다. 산술의 장제법과 유사하며, 피제수를 제수로 나누는 과정을 통해 몫과 나머지를 결정한다. 다항식 장제법은 다항식의 인수분해, 다항식 함수에 대한 접선 찾기, 순환 중복 검사(CRC) 등 다양한 분야에 적용된다. 다항식 단제법은 다항식 장제법을 간소화한 방법이며, 유클리드 나눗셈을 위한 알고리즘으로도 사용된다.

2. 다항식 장제법

다항식 장제법은 주어진 다항식(피제수)을 다른 다항식(제수)으로 나누어 몫과 나머지를 구하는 방법이다. 산술의 장제법과 유사하게, 다항식에서도 이와 같은 나눗셈 알고리즘을 적용할 수 있다.

예를 들어, 다항식 $(x^3\; -\; 2x^2\; -\; 4)$를 $(x-3)$으로 나눈다고 가정해 보자. 먼저, 피제수를 $x^3\; -\; 2x^2\; +\; 0x\; -\; 4$와 같이 다시 쓴다. 그런 다음, 피제수의 첫 항을 제수의 최고차항으로 나누는 과정을 반복하여 몫과 나머지를 결정한다. 이 과정은 구체적인 단계로 나누어 설명하며, 자세한 내용은 "다항식 장제법의 단계" 하위 섹션에서 확인할 수 있다.

2.1. 다항식 장제법의 단계

1. 피제수의 첫 번째 항을 제수의 최고차항으로 나눈다. 이 결과를 막대 위에 쓴다. (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}
   


2. 제수에 방금 구한 몫의 첫 번째 항을 곱한다. 결과를 피제수의 처음 두 항 아래에 쓴다. (x² · (x − 3) = x³ − 3x²)
   :$$
   \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³ − 2x²) − (x³ − 3x²) = x²) 그리고 피제수의 다음 항을 "내려온다".
   :$$
   \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. 이전 세 단계를 반복한다. 이번에는 방금 쓴 두 항을 피제수로 사용한다.
   :$$
   \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단계를 반복한다. 이번에는 "내려올" 항이 없다.
   :$$
   \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}
   

2.2. 다항식 장제법 예제

$(x^3\; -\; 2x^2\; -\; 4)$를 $(x-3)$으로 나누는 과정은 다음과 같다.

먼저, 피제수(나누어지는 수)를 다음과 같이 다시 쓴다.

:$x^3\; -\; 2x^2\; +\; 0x\; -\; 4$

그런 다음, 아래와 같은 단계를 따라 몫과 나머지를 구한다.

1. 피제수의 첫 번째 항($x^3$)을 제수(나누는 수)의 최고차항($x$)으로 나눈다. 이 값을 막대 위에 적는다. ($x^3\; \backslash div\; x\; =\; x^2$)
:$$
\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$)을 곱한다. 이 결과를 피제수의 처음 두 항 아래에 쓴다. ($x^2\; \backslash cdot\; (x\; -\; 3)\; =\; x^3\; -\; 3x^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}

3. 방금 구한 결과를 원래 피제수의 해당 항에서 뺀다. ($(x^3\; -\; 2x^2)\; -\; (x^3\; -\; 3x^2)\; =\; x^2$) 그 결과를 아래에 적고, 피제수의 다음 항($0x$)을 "내려온다".
:$$
\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. 위의 세 단계를 반복한다. 이번에는 방금 계산한 $x^2$과 내려온 $0x$를 피제수로 사용한다.
:$$
\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단계를 반복한다. 이번에는 "내려올" 항이 없다.
:$$
\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}


따라서 몫은 $x^2\; +\; x\; +\; 3$이고, 나머지는 $5$이다. 이를 수식으로 나타내면 다음과 같다.

:$\{x^3\; -\; 2x^2\; -\; 4\}\; =\; (x-3)(x^2\; +\; x\; +\; 3)\; +\; 5$

이 과정은 산술의 장제법과 유사하며, 변수 $x$를 특정한 숫자(예: 10)로 바꾸면 같은 원리가 적용된다.

2.3. 다항식 단제법

블롬크비스트 방법은 다항식 장제법을 간소화한 것이다. 이 방법은 장제법과 같은 알고리즘을 사용하지만, 암산을 통해 나머지를 계산한다. 따라서 적은 양만 기록하면 되므로, 숙달되면 더 빠른 방법이 될 수 있다.

이 과정은 긴 곱셈과 유사하게 피제수를 맨 위에, 제수를 그 아래에 쓰는 것으로 시작한다. 몫은 왼쪽에서 오른쪽으로 가로선 아래에 쓴다.

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

피제수의 첫 번째 항을 제수의 최고차항으로 나눈다(x³ ÷ x = x²). 결과를 가로선 아래에 적는다. x³은 나누어 떨어지므로 취소선을 긋는다. 결과 x²에 제수의 두 번째 항 −3을 곱하여 −3x²을 얻는다. −2x² − (−3x²) = x²를 계산하여 나머지를 구한다. −2x²에 취소선을 긋고 나머지 x²을 그 위에 적는다.

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


나머지의 최고차항을 제수의 최고차항으로 나눈다(x² ÷ x = x). 결과를 가로선 아래에 (+x)로 적는다. x²은 나누어 떨어지므로 취소선을 긋는다. 결과 x에 제수의 두 번째 항 −3을 곱하여 −3x를 얻는다. 0x − (−3x) = 3x를 계산하여 나머지를 구한다. 0x에 취소선을 긋고 새로운 나머지 3x를 그 위에 적는다.

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


나머지의 최고차항을 제수의 최고차항으로 나눈다(3x ÷ x = 3). 결과를 가로선 아래에 (+3)으로 적는다. 3x는 나누어 떨어지므로 취소선을 긋는다. 결과 3에 제수의 두 번째 항 −3을 곱하여 −9를 얻는다. −4 − (−9) = 5를 계산하여 나머지를 구한다. −4에 취소선을 긋고 새로운 나머지 5를 그 위에 적는다.

:$\backslash begin\{matrix\}\; \backslash quad\; \backslash qquad\; \backslash qquad\; \backslash qquad\backslash bcancel\{x^2\}\; \backslash quad\; \backslash bcancel\{3x\}\; \backslash quad5\backslash \backslash$
\qquad \quad \bcancel{x^3}+\bcancel{-2x^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)이다.

3. 의사코드

다음은 다항식 나눗셈 알고리즘을 나타내는 의사코드이다. +, -, ×는 다항식의 덧셈, 뺄셈, 곱셈을 나타내고, /는 두 항의 나눗셈을 나타낸다.

```
function n / d is
require d ≠ 0
q ← 0
r ← n // 각 단계에서 n = d × q + r

while r ≠ 0 and degree(r) ≥ degree(d) do
t ← lead(r) / lead(d) // 최고차항끼리 나눈다.
q ← q + t
r ← r − t × d

return (q, r)
```

이 알고리즘은 n의 차수가 d의 차수보다 작은 경우에도 작동하며, 이 경우 결과는 (0, n)이다.

이 알고리즘은 종이와 연필을 사용하여 다항식 나눗셈을 하는 방법을 정확하게 묘사한다. d는 ")"의 왼쪽에 쓰고, q는 가로선 위에 각 항별로 쓰며, 마지막 항은 t의 값이 된다. 가로선 아래 영역은 r의 연속적인 값을 계산하고 기록하는 데 사용된다.

4. 유클리드 나눗셈

B ≠ 0인 모든 다항식 쌍(A, B)에 대해, 다항식 나눗셈은 다음과 같은 몫 Q와 나머지 R을 제공한다.

:A = BQ + R

또한 R = 0 또는 deg(R) < deg(B) 중 하나를 만족한다. (Q, R)은 이러한 속성을 가진 유일한 다항식 쌍이다.

A와 B에서 고유하게 정의된 다항식 Q와 R을 얻는 과정을 유클리드 나눗셈(때로는 나눗셈 변환)이라고 한다. 따라서 다항식 장제법은 유클리드 나눗셈을 위한 알고리즘이다.

5. 적용

다항식 장제법은 다양한 분야에서 활용된다.

5.1. 다항식 인수분해

유리근 정리를 사용하여 다항식의 근이 알려져 있을 때, 다항식 장제법을 이용하여 주어진 다항식을 인수분해할 수 있다. 만약 n차 다항식 P(x)의 한 근 r이 알려져 있다면, 다항식 장제법을 사용하여 P(x)를 (x − r)Q(x) 형태로 인수분해할 수 있다. 여기서 Q(x)는 n − 1차 다항식이며, 나눗셈 과정에서 얻어진 몫이다. r이 P(x)의 근이므로 나머지는 0이 된다.

마찬가지로, P(x)의 여러 근 r, s 등이 알려져 있다면, 일차 인자 (x − r)를 나누어 Q(x)를 얻고, 그다음 (x − s)를 Q(x)에서 나누는 과정을 반복할 수 있다. 또는, 이차 인자 (x − r)(x − s) = x² − (r + s)x + rs를 P(x)에서 나누어 n − 2차 몫을 얻을 수도 있다.

이 방법은 특히 삼차 다항식에 유용하며, 때로는 더 높은 차수의 다항식의 모든 근을 구할 수 있게 한다. 예를 들어, 유리근 정리가 오차 다항식의 단일 유리 근을 생성하는 경우, 이를 인수분해하여 사차 다항식 몫을 얻을 수 있으며, 사차 다항식의 근에 대한 명시적인 공식을 사용하여 오차 다항식의 다른 네 개의 근을 찾을 수 있다. 그러나 모든 경우에 가능한 것은 아니며, 순수한 대수적 방법으로 오차 다항식을 풀 수 있는 일반적인 방법은 없다. (아벨-루피니 정리 참조)

5.2. 다항식 함수에 대한 접점 찾기

다항식 장제법은 특정 지점 x = r에서 다항식 P(x)에 의해 정의된 함수의 그래프에 표시된 접선의 방정식을 찾는 데에 사용될 수 있다. 만약 R(x)가 (x – r)^2영어에 의한 P(x)의 나머지 부분이라면 r이 다항식의 근인지 여부에 관계없이 함수 y = P(x)^영어의 그래프에 대한 x = r^영어에서의 접선 방정식은 y = R(x)^영어이다.

예를 들어 다음 곡선에 접하는 직선의 방정식을 구해보자.

:

:x = 1^영어 에서의 접선을 구하기 위해, 다항식을 다음 식으로 나눈다.

:

:

따라서 접선의 방정식은 다음과 같다.

:

5.3. 순환 중복 검사 (CRC)

순환 중복 검사는 다항식 나눗셈 과정에서 나온 나머지를 사용하여 전송된 메시지의 오류를 감지한다.