다항식 장제법

다항식 장제법(多項式 長除法, )은 대수학에서 다항식을 동일하거나 낮은 수준의 다른 다항식으로 나누는 알고리즘으로 장제법이라고 불리는 친숙한 산술 기법의 일반화된 버전이다. 이것은 다른 복잡한 나눗셈 문제를 작은 나눗셈 문제로 분리하기 때문에 손으로 쉽게 수행할 수 있다. 때때로 조립제법이라고 불리는 속기 버전을 사용하는 것이 더 빠르고 적은 쓰기와 적은 계산을 확용하기 때문에 더 빠르다. 또다른 약칭 방법은 다항식 단제법(블롬크비스트(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) formula_1 나누기 "제수"(divisor) formula_2의 몫과 나머지를 구하시오.
피제수는 먼저 다음과 같이 다시 작성된다.
그 후 다음과 같이 몫과 나머지를 결정할 수 있다.
막대 위의 다항식은 "q"("x")이고 남은 수(5)는 나머지 "r"("x")이다.
산술에 대한 장제법 알고리즘은 변수 "x"가 특정 숫자 10으로 대체되는 위의 알고리즘과 매우 유사하다.
다항식 단제법.
블롬크비스트의 방법(Blomqvist's method)은 위에서 언급한 장제법의 축소판이다. 이러한 연필-종이 방법은 다항식 장제법과 동일한 알고리듬을 사용하지만 나머지 부분을 결정하기 위해 정신적 계산이 사용된다. 이것은 적은 양의 쓰기를 요구하기 때문에 일단 숙달되면 더 빠른 방법이 될 수 있다.
이 과정은 처음에 피제수를 맨 위에 두고 그 아래에 있는 제수와 긴 곱셈과 비슷한 방식으로 작성된다. 몫은 왼쪽에서 오른쪽으로 막대 아래쪽에 쓰여져야 한다.
formula_5
피제수의 1번째 항을 제수의 가장 높은 항("x"3 ÷ "x" = "x"2)에 둔다. 그런 다음에 막대 아래에 결과를 표시한다. "x"3는 나머지를 남기지 않고 분할되었으므로 역슬래시와 함께 사용된 것으로 표시할 수 있다. 그런 다음에 "x"2에 −3 = −3"x"2의 2번째 항을 곱한다. −2"x"2 − (−3"x"2) = "x"2를 빼서 나머지 부분을 확인한다. −2"x"2를 사용된 것으로 표시한 다음에 나머지 "x"2 위에 표시한다.
formula_6
나머지 가운데 가장 높은 항을 제수의 가장 높은 항("x"2 ÷ "x" = "x")으로 나눈다. 그런 다음에 막대 아래에 결과(+x)를 배치한다. "x"2가 분할되어 나머지가 없으므로 사용된 것으로 표시할 수 있다. 그런 다음에 결과 "x"에 −3 = −3"x"의 2번째 항을 곱한다. 그런 다음에 0"x" − (−3"x") = 3"x"를 빼서 나머지 부분을 결정한다. 0x를 사용된 것으로 표시하고 새로운 나머지 부분을 3"x" 위에 표시한다.
formula_7
나머지 가운데 가장 높은 항을 제수의 가장 높은 항(3x ÷ "x" = 3)으로 나눈다. 그런 다음에 막대 아래에 결과(+3)를 표시한다. 3x는 나머지를 남기지 않고 분할되었으므로 사용된 것으로 표시할 수 있다. 그런 다음에 결과 3에 −3 = −9의 2번째 항을 곱한다. -4 -(-9) = 5를 빼서 나머지 부분을 결정한다. -4를 사용된 것으로 표시하고 나머지 부분 5를 위에 표시한다.
formula_8
막대 아래의 다항식은 "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") &gt; 도("d")일 때도 동일하게 잘 작동하며 이 경우 결과는 사소함(0, n)에 불과하다. 이러한 알고리즘은 위의 종이와 연필 방법을 정확히 기술한다. ")"의 왼쪽에 이 쓰여진다. 는 의 값이 되는 마지막 항을 의 값인 의 위에 의 연속적인 값을 계산하고 기록하는 데 사용된다. 수평선 아래의 영역은 의 연속 값을 계산하고 기록하는 데 사용됩니다.
유클리드 나눗셈.
"B" ≠ 0과 같은 모든 다항식 쌍("A", "B")에 대해, 다항식 나눗셈은 다음과 같은 몫 "Q"와 나머지 "R"을 제공한다.
또한 "R" = 0 또는 도 ("R") &lt; 도("B") 가운데 하나를 선택한다. 더욱이 ("Q", "R")은 이러한 속성을 가진 고유한 다항식 쌍이다.
"A"와 "B"에서 고유하게 정의된 다항식 "Q"와 "R"을 얻는 과정을 유클리드 나눗셈(때로는 나눗셈 변환)이라고 한다. 따라서 다항식 장제법은 유클리드 나눗셈을 위한 알고리즘이다.
적용.
인수화 다항식.
때때로 하나 이상의 다항식의 근이 알려져 있는데 아마도 유리근 정리를 사용하여 발견되었을 것이다. 만약 다항식 "P"("x")의 한 루트 "r"이 "n"의 다항식 "P"("x")를 로 인수하기 위해 다항식 긴 나눗셈을 사용할 수 있는데 여기서 "Q"("x")는 "n" − 1의 다항식이다. "Q"("x")는 단순히 분할 과정에서 얻은 몫이다. "r"는 "P"("x")의 루트이기 때문에 나머지가 0이어야 한다고 알려져 있다.
마찬가지로 2개 이상의 근이 알려져 있다면 이들 가운데 하나인 선형 인수 는 "Q"("x")를 얻기 위해 분할될 수 있고 다른 루트의 선형 항인 "s"는 "Q"("x")에서 분할될 수 있다. 대신 이들은 모두 한 번에 나누어질 수 있다. 예를 들어 선형 인수 과 를 곱하여 2차 인수 를 얻을 수 있으며 이 인수는 원래 다항식 "P"("x")로 나누어도 의 몫을 얻을 수 있다.
이런 식으로 때때로 사차 함수의 모든 근을 얻을 수 있지만 그것이 항상 가능한 것은 아니다. 예를 들어 만약 유리근 정리가 오차 방정식의 단일 (유리수) 근을 얻기 위해 사용될 수 있다면 사차 함수의 근에 대한 명시적 공식은 오차 방정식의 나머지 사차 함수의 근을 찾는 데 사용될 수 있다.
다항식 함수에 대한 접점 찾기.
다항식 장제법은 특정 지점 에서 다항식 "P"("x")에 의해 정의된 함수의 그래프에 표시된 접선의 방정식을 찾는 데에 사용될 수 있다. 만약 "R"("x")가 에 의한 "P"("x")의 나머지 부분이라면 "r"이 다항식의 루트인 지의 여부에 관계 없이 함수 의 그래프에 대한 의 접선 방정식은 이다.
순환 중복 검사.
순환 중복 검사는 다항식의 나눗셈 과정에서 나온 나머지를 사용하여 전송된 메시지의 오류를 감지한다.