Irreducible polynomial

수학(mathematics)에서, 기약 다항식(irreducible polynomial)은, 대략적으로 말해서, 두 개의 비-상수 다항식(non-constant polynomials)의 곱으로 인수화될 수 없는 다항식입니다. 기약성의 속성은 가능한 인수, 즉, 다항식의 계수와 그의 가능한 인수가 속하는 것으로 가정되는 필드(field) 또는 링(ring)에 대해 수용되는 계수(coefficient)의 본성에 따라 달라집니다. 예를 들어, 다항식 $x 2 - 2$ 는 정수(integer) 계수를 갖는 다항식이지만, 모든 각 정수는 역시 실수(real number)이기 때문에, 그것은 역시 실수(real) 계수를 가진 다항식입니다. 만약 그것이 정수(integer) 계수를 가진 다항식으로 고려되면, 기약이지만, 만약 그것이 실수(real) 계수를 가진 다항식으로 고려되면, 그것은 $(x-{\sqrt {2}})(x+{\sqrt {2}})$ 로 인수화됩니다. 우리는 다항식 $x 2 - 2$ 는 정수에 걸쳐 기약이지만 실수에 걸쳐 기약이 아니라고 말합니다.

계수를 포함하는 임의의 필드에 걸쳐 기약인 다항식은 절대적 기약(absolutely irreducible)입니다. 대수학의 기본 정리(fundamental theorem of algebra)에 의해, 일변수 다항식(univariate polynomial)이 절대적 기약인 것과 그의 차수가 일인 것은 필요충분(iff) 조건입니다. 다른 한편으로, 여러 개의 불확정(indeterminate)과 함께, 임의의 양의 정수 $n$ 에 대해 $x^{2}+y^{n}-1$ 와 같은, 임의의 차수의 절대적 기약 다항식이 있습니다.

기약이 아닌 다항식은 때때로 비-기약(reducible)이라고 말합니다.^[1]^[2] 어쨌든, 이 용어는 반드시 주의와 함께 사용해야 하는데, 왜냐하면 그것은 감소(reduction)의 다른 개념을 참조할 수 있기 때문입니다.

기약 다항식은 다항식 인수분해(polynomial factorization)와 대수적 필드 확장(algebraic field extension)의 연구에서 자연스럽게 발생합니다.

기약 다항식과 소수(prime number)를 비교하는 것이 도움이 됩니다: (같은 크기의 대응하는 음의 숫자와 함께) 소수는 기약 정수(integer)입니다. 그것들은, 소수 또는 기약 인수들로 본질적으로 고유한 인수분해와 같은, 기약 다항식에 똑같이 적용되는 "기약성"의 개념의 많은 일반적인 속성을 나타냅니다. 계수 링이 필드 또는 다른 고유한 인수분해 도메인(unique factorization domain)일 때, 기약 다항식은 역시 소수 다항식(prime polynomial)이라고 불리는데, 왜냐하면 그것은 소수 아이디얼(prime ideal)을 생성하기 때문입니다.

Definition

만약 F가 필드이면, 비-상수 다항식은 만약 그것의 계수가 F에 속하고 그것이 F에서 계수를 갖는 두 비-상수 다항식의 곱으로 인수화되지 않으면 F에 걸쳐 기약입니다.

정수 계수를 갖는, 또는 보다 일반적으로, 고유한 인수분해 도메인(unique factorization domain) R에서 계수를 갖는 다항식은, 만약 그것이 다항식 링(polynomial ring)의 기약 원소(irreducible element)이면, 즉, 그것이 역-가능(invertible)이 아니고, 영이 아니고, R에서 계수를 갖는 두 비-역가능 다항식의 곱으로 인수화되지 않으면, 기약 (또는 R에 걸쳐 기약)이라고 때때로 말합니다. 이 정의는 필드에서 계수의 경우에 대해 주어진 정의를 일반화하는데, 왜냐하면, 필드에 걸쳐, 비-상수 다항식이 정확히 역-가능이 아니고 비-영인 다항식이기 때문입니다.

또 다른 정의는, 만약 다항식이 R의 분수의 필드(field of fractions) (만약 R이 정수이면 유리수(rational number)의 필드)에 대해 기약이면, 자주 사용되며, 그것이 R에 걸쳐 기약이라고 말합니다. 이 두 번째 정의는 이 기사에서 사용되지 않습니다.

Nature of a factor

인수에 대해 명시적 대수적 표현(algebraic expression)의 부재가 다항식이 기약이라는 것을 자체로 의미하지는 않습니다. 다항식이 인수로 기약일 때, 이들 인수는 명시적 대수적 표현 또는 암시적 표현(implicit expressions)일 수 있습니다. 예를 들어, $x^{2}+2$ 는 복소수에 걸쳐 $\left(x-{\sqrt {2}}i\right)\left(x+{\sqrt {2}}i\right)$ 로 명시적으로 인수화될 수 있습니다; 어쨌든, 아벨–루피니 정리(Abel–Ruffini theorem)는 복소 인수가 명시적 대수적 표현을 가지지 않는 것이 존재하는 4보다 더 큰 다항식이 있다고 말합니다. 그러한 인수는, 말하자면, $\left(x-x_{1}\right)$ 와 같이 간단하게 쓸 수 있으며, 여기서 $x_{1}$ 는 다항식을 0과 같게 설정하는 방정식의 특정 해로 암시적으로 정의됩니다. 게다가, 두 형식의 인수는 근-찾기 알고리듬(root-finding algorithm)에 의해 얻어질-수-있는 수치적 근사, 예를 들어 $\left(x-1.2837\ldots \right)$ 로 역시 표현될 수 있습니다.

Simple examples

다음 여섯 다항식은 비-기약과 기약 다항식의 일부 기본 속성을 시연합니다:

{\begin{aligned}p_{1}(x)&=x^{2}+4x+4\,={(x+2)(x+2)}\\p_{2}(x)&=x^{2}-4\,={(x-2)(x+2)}\\p_{3}(x)&=9x^{2}-3\,=3\left(3x^{2}-1\right)\,=3\left(x{\sqrt {3}}-1\right)\left(x{\sqrt {3}}+1\right)\\p_{4}(x)&=x^{2}-{\frac {4}{9}}\,=\left(x-{\frac {2}{3}}\right)\left(x+{\frac {2}{3}}\right)\\p_{5}(x)&=x^{2}-2\,=\left(x-{\sqrt {2}}\right)\left(x+{\sqrt {2}}\right)\\p_{6}(x)&=x^{2}+1\,={(x-i)(x+i)}\end{aligned}}

정수(integer)에 걸쳐, 처음 세 다항식은 비-기약입니다 (세 번째 것은 비-기약인데 왜냐하면 인수 3은 정수에서 역-가능이 아니기 때문입니다); 마지막 둘은 기약입니다. (네 번째는, 물론, 정수에 걸쳐 다항식이 아닙니다.)

유리수(rational number)에 걸쳐, 처음 둘과 네 번째 다항식은 비-기약이지만, 다른 세 다항식은 기약입니다 (유리수에 걸쳐 다항식이기 때문에, 3은 단위(unit)이고, 따라서, 인수로 세지 않습니다).

실수(real number)에 걸쳐, 처음 다섯 다항식은 비-기약이지만, $p_{6}(x)$ 는 기약입니다.

복소수(complex number)에 걸쳐, 모든 여섯 다항식은 비-기약입니다.

Over the complex numbers

복소 필드에 걸쳐, 및 보다 일반적으로, 대수적으로 닫힌 필드(algebraically closed field)에 걸쳐, 일변수 다항식(univariate polynomial)이 기약인 것과 그것의 차수(degree)가 일인 것은 필요충분 조건입니다. 이 사실은 복소수의 경우에서 대수학의 기본 정리(fundamental theorem of algebra)로, 및, 일반적으로 대수적으로 닫히는 조건으로 알려져 있습니다.

그것은 모든 각 비-상수 일변수 다항식이 다음으로 인수화될 수 있음을 따릅니다:

a\left(x-z_{1}\right)\cdots \left(x-z_{n}\right)

여기서 $n$ 은 차수, $a$ 는 선행 계수이고 $z_{1},\dots ,z_{n}$ 는 다항식의 영들입니다 (구별될 필요가 없고, 명시적으로 대수적 표현(algebraic expression)을 가질 필요가 없습니다).

복소수에 걸쳐 모든 각 차수의 기약 다변수 다항식(multivariate polynomial)이 있습니다. 예를 들어, 다음 다항식은,

x^{n}+y^{n}-1,

페르마 곡선(Fermat curve)을 정의하며, 모든 각 양의 n에 대해 기약입니다.

Over the reals

실수(real)의 필드에 걸쳐, 기약 일변수 다항식의 차수(degree)는 1이거나 2입니다. 보다 정확하게, 기약 다항식은 차수 일의 다항식과 음의 판별식(discriminant) $b^{2}-4ac$ 을 가지는 이차 다항식(quadratic polynomial) $ax^{2}+bx+c$ 입니다. 그것은 모든 각 비-상수 일변수 다항식이 많아야 이차의 다항식의 곱으로 인수화될 수 있음을 따릅니다. 예를 들어, $x^{4}+1$ 는 실수에 걸쳐 $\left(x^{2}+{\sqrt {2}}x+1\right)\left(x^{2}-{\sqrt {2}}x+1\right)$ 로 인수화되고, 그것은 더 이상 인수화될 수 없는데, 왜냐하면 두 인수는 음의 판별식: $\left(\pm {\sqrt {2}}\right)^{2}-4=-2<0$ 을 가지기 때문입니다.

Unique factorization property

필드 $F$ 에 걸쳐 모든 각 다항식은 비-영 상수와 유한 숫자의 ( $F$ 에 걸쳐) 기약 다항식의 곱으로 인수화될 수 있습니다. 이 분해는 인수의 순서와 그것의 곱이 1인 비-영 상수에 의한 인수의 곱셈까지(up to) 고유합니다.

고유한 인수분해 도메인(unique factorization domain)에 걸쳐, 같은 정리는 참이지만, 원시 다항식(primitive polynomial)의 개념을 사용함으로써 보다 정확하게 공식화됩니다. 원시 다항식은 1이 그것의 계수의 최대 공통 약수(greatest common divisor)를 만족하는 고유한 인수분해 도메인에 걸쳐 다항식입니다.

$F$ 를 고유한 인수분해 도메인으로 놓습니다. $F$ 에 걸쳐 비-상수 기약 다항식은 원시입니다. $F$ 에 걸쳐 원시 다항식이 $F$ 에 걸쳐 기약인 것과 그것이 $F$ 의 분수의 필드(field of fractions)에 걸쳐 기약인 것은 필요충분 조건입니다. $F$ 에 걸쳐 모든 각 다항식은 비-영 상수와 유한 숫자의 비-상수 기약 원시 다항식의 곱으로 분해될 수 있습니다. 비-영 상수는 $F$ 의 단위(unit)와 유한 숫자의 $F$ 의 기약 원소(irreducible element)의 곱으로 자체로 분해될 수 있습니다. 두 인수분해는 인수의 순서와 $F$ 의 단위에 의한 인수의 곱셈까지 고유합니다.

이것은 고유한 인수분해 도메인에 걸쳐 기약 다항식의 정의가 종종 다항식이 비-상수인 것으로 가정하도록 동기를 부여하는 그 정리입니다.

정수(integer)와 유리수(rational number)에 걸쳐 다항식을 인수화하는 것에 대해 현재 구현된(implemented) 모든 알고리듬(algorithm)은 이 결과를 사용합니다 (다항식의 인수분해(Factorization of polynomials)를 참조하십시오).

Over the integers and finite field

정수 $\mathbb {Z}$ 에 걸쳐 다항식의 기약성은 (소수 $p$ 에 대해) $p$ 원소의 필드 $\mathbb {F} _{p}$ 에 걸쳐 다항식과 관련됩니다. 특히, 만약 $\mathbb {Z}$ 에 걸쳐 일변수 다항식 f가 f의 선행 계수 (변수의 최고 거듭제곱의 계수)를 나누지 않는 어떤 소수 $p$ 에 대해 $\mathbb {F} _{p}$ 에 걸쳐 기약이면, f는 $\mathbb {Z}$ 에 걸쳐 기약입니다. 아인슈타인의 기준(Eisenstein's criterion)은 $p^{2}$ 에 걸쳐 기약성이 역시 포함되는 곳에서 이 속성의 변형입니다.

전환은, 어쨌든, 참이 아닙니다: 정수에 걸쳐 기약이고 모든 각 유한 필드에 걸쳐 비-기약인 임의적으로 큰 차수의 다항식이 있습니다.^[3] 그러한 다항식의 간단한 예제는 $x^{4}+1$ 입니다.

정수에 걸쳐 기약성과 모듈로 p에 걸쳐 기약성 사이의 관계는 이전 결과보다 더 깊습니다: 현재까지 정수에 걸쳐 및 유리수에 걸쳐 인수분해와 기약성에 대해 모든 구현된 알고리듬은 유한 필드에 걸쳐 인수분해를 서브루틴(subroutine)으로 사용합니다.

$q$ 소수 거듭제곱에 대해 필드 $\mathbb {F} _{q}$ 에 걸쳐 차수 $n$ 기약 일계수 다항식(monic polynomial)의 숫자는 다음에 의해 제공됩니다:^[4]

N(q,n)={\frac {1}{n}}\sum _{d\mid n}\mu (d)q^{\frac {n}{d}},

여기서 $μ$ 는 뫼비우스 함수(Möbius function)입니다. $q = 2$ 에 대해, 그러한 다항식은 유사확률 이항 수열(pseudorandom binary sequence)을 생성하기 위해 공통적으로 사용됩니다.

일부 의미에서, 계수 영 또는 일을 갖는 거의 모든 다항식은 정수에 걸쳐 기약입니다. 보다 정확하게, 만약 데데킨트 제타 함수(Dedekind zeta functions)에 대해 리만 가설(Riemann hypothesis)의 버전이 가정되면, ${0, 1}$ 에서 확률(random) 계수를 갖는 다항식에 대해 정수에 걸쳐 기약일 확률은 차수가 증가할 때 일로 경향입니다.^[5]^[6]

Algorithms

다항식의 고유한 인수분해 속성이 주어진 다항식의 인수분해가 항상 계산될 수 있음을 의미하지는 않습니다. 심지어 다항식의 기약성이 계산에 의해 항상 입증되는 것은 아닙니다: 알고리듬이 임의의 다항식의 기약성을 결정하기 위한 존재할 수 없는 필드가 있습니다.^[7]

다항식을 인수분해하고 기약성을 결정하는 것에 대해 알고리듬은 정수, 유리수, 유한 필드(finite field) 및 이들 필드의 유한하게 생성된 필드 확장(finitely generated field extension)에 걸쳐 다항식에 대해 컴퓨터 대수 시스템(computer algebra system)에서 알려져 있고 구현됩니다. 모든 이들 알고리듬은 유한 필드에 걸쳐 다항식의 인수분해(factorization of polynomials over finite fields)에 대해 알고리듬을 사용합니다.

Field extension

기약 다항식과 대수적 필드 확장(algebraic field extension)의 개념은 다음 방법에서 강하게 관련됩니다.

x를 필드 K의 확장(extension) L의 원소로 놓습니다. 이 원소는 만약 그것이 K에서 계수를 갖는 다항식의 근(root)이면 대수적이라고 말합니다. x가 근인 다항식 중에서, 일계수(monic)이고 최소 차수인, x의 최소 다항식(minimal polynomial)이라고 불리는 것이 정확히 하나가 있습니다. L의 대수적 원소 x의 최소 다항식은 기약이고, x가 근인 고유한 일계수 기약 다항식입니다. x의 최소 다항식은 근으로 x를 근의 가지는 모든 각 다항식을 나눕니다 (이것은 아벨의 기약성 정리(Abel's irreducibility theorem)입니다).

반대로, 만약 $P(X)\in K[X]$ 가 필드 K에 걸쳐 일변수 다항식이면, $L=K[X]/P(X)$ 를 $P$ 에 의해 생성된 아이디얼(ideal generated)에 의한 다항식 링 $K[X]$ 의 몫 링(quotient ring)으로 놓습니다. 그런-다음 $L$ 이 필드인 것과 $P$ 가 $K$ 에 걸쳐 기약인 것은 필요충분 조건입니다. 이 경우에서, 만약 $x$ 가 $L$ 에서 $X$ 의 이미지이면, $x$ 의 최소 다항식은 그것의 선행 계수(leading coefficient)에 의한 $P$ 의 몫입니다.

위의 것의 예제는 $\mathbb {C} =\mathbb {R} [X]/\left(X^{2}+1\right)$ 로 복소수(complex number)의 표준 정의입니다.

만약 다항식 $P$ 가 $K$ 에 걸쳐 일보다 더 큰 차수를 가지는 기약 인수 $Q$ 를 가지면, 우리는 $P$ 가 $K$ 에서 보다 적어도 하나 더 많은 근을 갖는 확장을 얻기 위해 대수적 확장의 이전 구성을 $Q$ 에 적용할 수 있습니다. 이 구성을 반복하면, 우리는 결국 $P$ 가 선형 인수로 인수화되는 필드를 얻게 됩니다. 이 필드는, 필드 동형까지(up to) 고유하며, $P$ 의 분할 필드(splitting field)라고 불립니다.

Over an integral domain

만약 R이 정수 도메인(integral domain)이면, 영도 아니고 단위도 아닌 R의 원소 f는 만약 f = gh를 갖는 비-단위 g와 h가 없으면 기약(irreducible)이라고 불립니다. 우리는 모든 각 소수 원소(prime element)가 기약이라는 것을 보일 수 있습니다;^[8] 그 전환은 일반적으로 참이 아니지만 고유한 인수분해 도메인(unique factorization domain)을 유지합니다. 필드 F (또는 임의의 고유한-인수분해 도메인)에 걸쳐 다항식 링(polynomial ring) F[x]는 다시 고유한 인수분해 도메인입니다. 귀납적으로, 이것은 (링 R에 걸쳐) n 불확정에서 다항식 링은 만약 같은 것이 R에 대해 참이면 고유한 인수분해 도메인이라는 것을 의미합니다.

Notes

^ Gallian 2012, p. 311.
^ Mac Lane and Birkhoff (1999) do not explicitly define "reducible", but they use it in several places. For example: "For the present, we note only that any reducible quadratic or cubic polynomial must have a linear factor." (p. 268).
^ David Dummit; Richard Foote (2004). "chapter 9, Proposition 12". Abstract Algebra. John Wiley & Sons, Inc. p. 309. ISBN 0-471-43334-9.
^ Jacobson 2009, §4.13
^ Breuillard, Emmanuel; Varjú, Péter P. (2018). "Irreducibility of random polynomials of large degree". arXiv:1810.13360 [math.NT].
^ Hartnett, Kevin. "In the Universe of Equations, Virtually All Are Prime". Quanta Magazine. Retrieved 2019-01-13.
^ Fröhlich, A.; Shepherson, J. C. (1955), "On the factorisation of polynomials in a finite number of steps", Mathematische Zeitschrift, 62 (1): 331–334, doi:10.1007/BF01180640, ISSN 0025-5874, S2CID 119955899
^ Consider p a prime that is reducible: p = ab. Then p | ab ⇒ p | a or p | b. Say p | a ⇒ a = pc, then we have: p = ab = pcb ⇒ p(1 − cb) = 0. Because R is a domain, we have cb = 1. So b is a unit, and p is irreducible.

References

Lang, Serge (2002), Algebra, Graduate Texts in Mathematics, vol. 211 (Revised third ed.), New York: Springer-Verlag, ISBN 978-0-387-95385-4, MR 1878556. This classical book covers most of the content of this article.
Gallian, Joseph (2012), Contemporary Abstract Algebra (8th ed.), Cengage Learning, ISBN 978-1285402734
Lidl, Rudolf; Niederreiter, Harald (1997), Finite fields (2nd ed.), Cambridge University Press, ISBN 978-0-521-39231-0, pp. 91.
Mac Lane, Saunders; Birkhoff, Garrett (1999), Algebra (3rd ed.), American Mathematical Society, ISBN 9780821816462
Menezes, Alfred J.; Van Oorschot, Paul C.; Vanstone, Scott A. (1997), Handbook of applied cryptography, CRC Press, ISBN 978-0-8493-8523-0, pp. 154.

External links

Weisstein, Eric W. "Irreducible Polynomial". MathWorld.
Irreducible Polynomial at PlanetMath.org.
Information on Primitive and Irreducible Polynomials, The (Combinatorial) Object Server.

[1] Gallian 2012, p. 311.

[2] Mac Lane and Birkhoff (1999) do not explicitly define "reducible", but they use it in several places. For example: "For the present, we note only that any reducible quadratic or cubic polynomial must have a linear factor." (p. 268).

[3] David Dummit; Richard Foote (2004). "chapter 9, Proposition 12". Abstract Algebra. John Wiley & Sons, Inc. p. 309. ISBN 0-471-43334-9.

[4] Jacobson 2009, §4.13

[5] Breuillard, Emmanuel; Varjú, Péter P. (2018). "Irreducibility of random polynomials of large degree". arXiv:1810.13360 [math.NT].

[6] Hartnett, Kevin. "In the Universe of Equations, Virtually All Are Prime". Quanta Magazine. Retrieved 2019-01-13.

[7] Fröhlich, A.; Shepherson, J. C. (1955), "On the factorisation of polynomials in a finite number of steps", Mathematische Zeitschrift, 62 (1): 331–334, doi:10.1007/BF01180640, ISSN 0025-5874, S2CID 119955899

[8] Consider p a prime that is reducible: p = ab. Then p | ab ⇒ p | a or p | b. Say p | a ⇒ a = pc, then we have: p = ab = pcb ⇒ p(1 − cb) = 0. Because R is a domain, we have cb = 1. So b is a unit, and p is irreducible.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]