godingMath

조립제법이란 다항식을 일차식으로 나눈 몫과 나머지를 곱셈과 덧셈만을 반복하여  빠르게 구하는 방법입니다. 다항식을 일차식으로 나누면 특별한 귀납적 관계를 발견할 수 있습니다. 이 귀납적 관계를 핵심원리로 삼아 만들어진 방법이 바로 조립제법입니다. 이 글에서는 일차식의 나눗셈이 가지고 있는 귀납적 관계를 살펴보고 조립제법이 어떻게 이 원리를 사용하고 있는지 알아보겠습니다.

조립제법의 원리

다항식을 일차식 \(x-p\)로 나누었을 때 일어나는 일들

삼차식을 예를 들어 생각해 보겠습니다. (일반적인 \(n\)차 다항식에서도 같은 원리를 적용할 수 있습니다.) 먼저 삼차식 $$f(x)=a_0x^3+a_1x^2+a_2x+a_3$$로 나타내고, 이 식을 일차식 \(x-p\)로 나누면 몫은 이차식, 나머지는 상수가 됩니다. 따라서 몫 \(Q(x)\)와 나머지 \(r\)을 각각 $$Q(x)=b_0x^2+b_1x+b_2, r=b_3$$라 두고, 몫과 나머지를 사용하여 검산식을 만들어 보면 $$\begin{align}
f(x)&=(x-p)(b_0x^2+b_1x+b_2)+b_3\\
&=b_0x^3+(b_1-pb_0)x^2+(b_2-pb_1)x+b_3-pb_2\end{align}$$입니다. 그런데, $$f(x)=a_0x^3+a_1x^2+a_2x+a_3$$이기 때문에,$$\begin{align}
&a_0x^3+a_1x^2+a_2x+a_3\\
&=b_0x^3+(b_1-pb_0)x^2+(b_2-pb_1)x+b_3-pb_2
\end{align}$$이 됩니다. 이제 이 등식에서 양변의 \(x^n\)의 계수를 비교하고, \(b_n\)에 대하여 정리하면 재미있는 패턴을 발견할수 있습니다. $$\begin{array}{c|c}
x^3 &  a_0=b_0 \Leftrightarrow b_0=a_0 \\ \hline
x^2 &  a_1=b_1-pb_0 \Leftrightarrow b_1=a_1+pb_0 \\ \hline
x & a_2=b_2-pb_1\Leftrightarrow b_2=a_2+pb_1 \\ \hline
상수항 &  a_3=b_3-pb_2\Leftrightarrow b_3=a_3+pb_2
\end{array} $$  식을 \(b_n\)에 대하여 정리한 이유는 무엇일까요? 이 식을 어떻게 이용할 수 있을까요? 그리고 이 식에서 어떤 패턴을 발견할 수 있을까요?

조립제법의 귀납적 관계

먼저 식을 \(b_n\)에 대하여 정리한 이유는 몫\(Q(x)\)와 나머지 \(r\)가 \(b_n\)을 사용해서 표현되어 있기 때문입니다 . 다시말해, \(b_n\)을 모두 구한다는 것은 몫의 모든 계수와 상수항, 나머지를 구한다는 것을 의미합니다. 그렇다면 앞에서 정리한 식을 어떻게 사용하는 것이 좋을까요? 먼저 \(b_0\)을 생각해보겠습니다. 앞서 식에서 $$b_0=a_0$$입니다. 단순히 \(a_0\)의 값을 대입하는 것만으로 \(b_0\)의 값을 구할 수 있습니다. 다음으로 \(b_1\)을 살펴보겠습니다. $$b_1=\color{red}{a_1}+p\color{blue}{b_0}$$ 입니다. 이 식에서 가장 주목해야 하는 부분은 $$p\cdot\color{blue}{b_0}$$입니다. \(b_1\)을 구하기 위해서는 \(p\)와 곱할 수 있도록 \(b_0\)를 미리 구해 놓아야 합니다. (\(p\)는 나누는 식 \((x-p)\)의 \(p\)이므로 이미 주어진 상태입니다.)  \(b_2\)를 구할 때에도 마찬가지 입니다. $$b_2=\color{red}{a_2}+p\color{blue}{b_1}$$이므로 \(b_1\)을 미리 구해두어야 하고, \(b_3\)를 구할 때에도 $$b_3=\color{red}{a_3}+p\color{blue}{b_2}$$이므로 \(b_2\)를 미리 구해 놓는 것이 필요합니다. 즉 \(b_n\)을 구할 때에는 다음과 같은 순서대로 구해주어야 합니다. $$b_0\xrightarrow{\times p, +a_1}b_1\xrightarrow{\times p, +a_2} b_2\xrightarrow{\times p, +a_3} b_3$$

이제 이 과정을 일반화하면 몫의 계수 및 나머지 \(b_n\)에 대해 다음과 같은 귀납적인 관계를 만들 수 있습니다. $$\begin{align}
&b_0=a_0;\\
&b_n=a_n+pb_{n-1},\ n\geq 1
\end{align}$$

이 귀납적 관계를 사용하면  이전 단계에서 구해둔 \(b_{n-1}\)에 \(p\)를 곱하고 나누어지는 식의 계수 \(a_n\)을 더하는 것으로 \(b_n\)을 구할 수 있습니다. 즉 이렇게 곱셈과 덧셈을 반복하는 것만으로 일차식 \(x-p\)로 나눈 몫과 나머지를 구할 수 있습니다. 결국 조립제법은 이러한 귀납적 관계를 빠르게 계산할 수 있도록 표의 형태로 정리하도록 만들어 둔 방법입니다. 이것이 바로 조립제법을 쓸 때 왼쪽에서부터 오른쪽으로 이동하며 곱셈과 덧셈을 반복하는 이유입니다.