다항식 장제법

파일:División euclidiana serie.png

다항식 장제법(多項式 長除法, 영어: polynomial long division)은 대수학에서 다항식을 동일하거나 낮은 수준의 다른 다항식으로 나누는 알고리즘으로 장제법이라고 불리는 친숙한 산술 기법의 일반화된 버전이다. 이것은 다른 복잡한 나눗셈 문제를 작은 나눗셈 문제로 분리하기 때문에 손으로 쉽게 수행할 수 있다. 때때로 조립제법이라고 불리는 속기 버전을 사용하는 것이 더 빠르고 적은 쓰기와 적은 계산을 확용하기 때문에 더 빠르다. 또다른 약칭 방법은 다항식 단제법(블롬크비스트(Blomqvist)의 방법)이다.

다항식 장제법은 다항식의 유클리드 나눗셈을 구현하는 알고리즘으로서 2개의 다항식 A(피제수)와 B(제수)에서 시작하여 B가 0이 아닐 경우 몫 Q와 나머지 R을 생성(A = BQ + R)한다. 여기서 R은 0이거나 R의 도가 B의 도보다 낮은 편이다. 이러한 조건은 Q와 R을 고유하게 정의하며 이는 Q와 R이 이들을 계산하는 방법에 의존하지 않는다는 것을 의미한다.

결과적으로 R은 0과 같거나 B가 다항식 A에 요인을 주는 경우에만 발생한다. 따라서 장제법은 하나의 다항식에 다른 요인이 있는 지의 여부를 검증하고 요인으로서 다른 다항식이 있는지 여부를 인수화하기 위한 평균이다. 예를 들어 A의 근 r이 알려진 경우에는 A를 (x – r)로 나누어 인수할 수 있다.

예제

다항식 장제법

"피제수"(dividend) $x^3-2x^2-4$ 나누기 "제수"(divisor) $x-3$의 몫과 나머지를 구하시오.

피제수는 먼저 다음과 같이 다시 작성된다.

$x^3-2x^2+0x-4$

그 후 다음과 같이 몫과 나머지를 결정할 수 있다.

1. 피제수의 1번째 항을 제수의 가장 높은 항(x의 가장 높은 힘을 가진 항을 의미하며 이 경우에는 x이다.)으로 나눈다. 막대 위에 결과를 표시하라(x³ ÷ x = x²).

   $\begin{array}{c}x-3)x^3-2x^2\\ x-3\overline{)x^3-2x^2+0x-4}\end{array}$

2. 방금 얻은 결과(즉 몫의 1번째 조건)에 점수를 곱하라. 피제수의 초반 2가지 조건(x² · (x − 3) = x³ − 3x²)에 따라 결과를 작성한다.

   $\begin{array}{c}x-3)x^3-2x^2\\ x-3\overline{)x^3-2x^2+0x-4}\\ x-3)x^3-3x^2\end{array}$

3. 방금 얻은 결과를 원래 피제수의 적절한 조건(마이너스 기호가 있는 것을 빼는 것은 플러스 기호가 있는 것을 더하는 것과 동등하다는 주의)에서 빼내고 그 결과를 ((x³ − 2x²) − (x³ − 3x²) = −2x² + 3x² = x²) 아래에 기록한다. 그런 다음 피제수에서 다음 용어를 "내려오라"고 표시한다.

   $\begin{array}{c}x-3)x^3-2x^2\\ x-3\overline{)x^3-2x^2+0x-4}\\ x-3)\underset{\_}{x^3-3x^2}\\ x-3)0x^3+x^2+0x\end{array}$

4. 앞에서 언급한 3차례의 과정을 반복하되 이번에는 방금 피제수로 작성된 2가지 용어를 사용한다.

   $\begin{array}{c}{x}^2+1x+3\\ x-3\overline{)x^3-2x^2+0x-4}\\ \underset{\_}{x^3-3x^2+0x-4}\\ +x^2+0x-4\\ \underset{\_}{+x^2-3x-4}\\ +3x-4\end{array}$

5. 4단계 과정을 반한다. 이번에는 "끌어내릴" 공간이 없다.

   $\begin{array}{c}{x}^2+1x+3\\ x-3\overline{)x^3-2x^2+0x-4}\\ \underset{\_}{x^3-3x^2+0x-4}\\ +x^2+0x-4\\ \underset{\_}{+x^2-3x-4}\\ +3x-4\\ \underset{\_}{+3x-9}\\ +5\end{array}$

막대 위의 다항식은 q(x)이고 남은 수(5)는 나머지 r(x)이다.

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

산술에 대한 장제법 알고리즘은 변수 x가 특정 숫자 10으로 대체되는 위의 알고리즘과 매우 유사하다.

다항식 단제법

블롬크비스트의 방법(Blomqvist's method)은 위에서 언급한 장제법의 축소판이다. 이러한 연필-종이 방법은 다항식 장제법과 동일한 알고리듬을 사용하지만 나머지 부분을 결정하기 위해 정신적 계산이 사용된다. 이것은 적은 양의 쓰기를 요구하기 때문에 일단 숙달되면 더 빠른 방법이 될 수 있다.

이 과정은 처음에 피제수를 맨 위에 두고 그 아래에 있는 제수와 긴 곱셈과 비슷한 방식으로 작성된다. 몫은 왼쪽에서 오른쪽으로 막대 아래쪽에 쓰여져야 한다.

$\begin{array}{c}{x}^3-2x^2+0x-4\\ \underset{\_}{÷x-3}\end{array}$

피제수의 1번째 항을 제수의 가장 높은 항(x³ ÷ x = x²)에 둔다. 그런 다음에 막대 아래에 결과를 표시한다. x³는 나머지를 남기지 않고 분할되었으므로 역슬래시와 함께 사용된 것으로 표시할 수 있다. 그런 다음에 x²에 −3 = −3x²의 2번째 항을 곱한다. −2x² − (−3x²) = x²를 빼서 나머지 부분을 확인한다. −2x²를 사용된 것으로 표시한 다음에 나머지 x² 위에 표시한다.

$\begin{array}{c}{x}^2\\ {\bcancel{x}}^3+\bcancel{-2}{x}^2+0x-4\\ \underset{\_}{÷x-3}\\ x^2\end{array}$

나머지 가운데 가장 높은 항을 제수의 가장 높은 항(x² ÷ x = x)으로 나눈다. 그런 다음에 막대 아래에 결과(+x)를 배치한다. x²가 분할되어 나머지가 없으므로 사용된 것으로 표시할 수 있다. 그런 다음에 결과 x에 −3 = −3x의 2번째 항을 곱한다. 그런 다음에 0x − (−3x) = 3x를 빼서 나머지 부분을 결정한다. 0x를 사용된 것으로 표시하고 새로운 나머지 부분을 3x 위에 표시한다.

$\begin{array}{c}{\bcancel{x}}^{2}3x\\ {\bcancel{x}}^3+\bcancel{-2}{x}^2+\bcancel{0x}-4\\ \underset{\_}{÷x-3}\\ x^2+x\end{array}$

나머지 가운데 가장 높은 항을 제수의 가장 높은 항(3x ÷ x = 3)으로 나눈다. 그런 다음에 막대 아래에 결과(+3)를 표시한다. 3x는 나머지를 남기지 않고 분할되었으므로 사용된 것으로 표시할 수 있다. 그런 다음에 결과 3에 −3 = −9의 2번째 항을 곱한다. -4 -(-9) = 5를 빼서 나머지 부분을 결정한다. -4를 사용된 것으로 표시하고 나머지 부분 5를 위에 표시한다.

$\begin{array}{c}{\bcancel{x}}^2\bcancel{3x}5\\ {\bcancel{x}}^3+\bcancel{-2}{x}^2+\bcancel{0x}\bcancel{-4}\\ \underset{\_}{÷x-3}\\ x^2+x+3\end{array}$

막대 아래의 다항식은 q(x)이고 왼쪽 부분(5)에 남은 숫자는 나머지 r(x)이다.

의사코드

알고리즘은 다음과 같이 의사코드로 표현될 수 있다. 여기서 +, -, ×는 다항식 산수를 나타내고 /는 2개 항으로 이루어진 간단한 나눗셈을 나타낸다.

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의 값이 되는 마지막 항을 t의 값인 t의 위에 t의 연속적인 값을 계산하고 기록하는 데 사용된다. 수평선 아래의 영역은 r의 연속 값을 계산하고 기록하는 데 사용됩니다.

유클리드 나눗셈

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

$A=BQ+R,$

또한 R = 0 또는 도 (R) < 도(B) 가운데 하나를 선택한다. 더욱이 (Q, R)은 이러한 속성을 가진 고유한 다항식 쌍이다.

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

적용

인수화 다항식

때때로 하나 이상의 다항식의 근이 알려져 있는데 아마도 유리근 정리를 사용하여 발견되었을 것이다. 만약 다항식 P(x)의 한 루트 r이 n의 다항식 P(x)를 (x − r)(Q(x))로 인수하기 위해 다항식 긴 나눗셈을 사용할 수 있는데 여기서 Q(x)는 n − 1의 다항식이다. Q(x)는 단순히 분할 과정에서 얻은 몫이다. r는 P(x)의 루트이기 때문에 나머지가 0이어야 한다고 알려져 있다.

마찬가지로 2개 이상의 근이 알려져 있다면 이들 가운데 하나인 선형 인수 (x − r)는 Q(x)를 얻기 위해 분할될 수 있고 다른 루트의 선형 항인 s는 Q(x)에서 분할될 수 있다. 대신 이들은 모두 한 번에 나누어질 수 있다. 예를 들어 선형 인수 x − r과 x − s를 곱하여 2차 인수 x² − (r + s)x + rs를 얻을 수 있으며 이 인수는 원래 다항식 P(x)로 나누어도 n − 2의 몫을 얻을 수 있다.

이런 식으로 때때로 사차 함수의 모든 근을 얻을 수 있지만 그것이 항상 가능한 것은 아니다. 예를 들어 만약 유리근 정리가 오차 방정식의 단일 (유리수) 근을 얻기 위해 사용될 수 있다면 사차 함수의 근에 대한 명시적 공식은 오차 방정식의 나머지 사차 함수의 근을 찾는 데 사용될 수 있다.

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

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

예제

$x=1$에서 다음 곡선에 접하는 선의 방정식을 찾는다.

$y=x^3-12x^2-42.$

다항식을 $(x-1{)}^2=x^2-2x+1$과 같이 나누는 것으로 시작한다.

$\begin{array}{c}x-10\\ x^2-2x+1\overline{)x^3-12x^2+0x-42}\\ \underset{\_}{x^3-02x^2+1x}-42\\ -10x^2-01x-42\\ \underset{\_}{-10x^2+20x-10}\\ -21x-32\end{array}$

접선은 $y=-21x-32$이다.

순환 중복 검사

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

같이 보기

• 조립제법
• 유클리드 정역
• 그뢰브너 기저