[이산수학] Polynomial Ring, Factor Theorem, Monic, GCD

Polynomial

ring R에서 다항식은 다음과 같은 형태로 나타난다.
$f(x) = a_n x^n + a_{n -1} x^{n - 1}  + ... + a_1 x^1 + a_0 x^0$
모든 $0 \leq i \leq n$ 에 대해 $a_i \in R $의 계수를 가지며 polynomial in the indeterminate x with coefficient from R (미정변수 x에 대한 다항식) 이라고 불린다.

• R[x] 는 R위의 모든 다항식의 집합
• leading coefficient : 다항식의 가장 높은 차수항의 계수 ($a \neq z$ 일 때)
• degree of polynomial : 다항식의 가장 높은 차수 (n)
• constant term : 상수항 $x^0$의 계수
• n는 음이 아닌 정수이며 각 $a_i$는 R에 속한다.
  • $a_0$은 상수항이라고 부르며 $a_i$는 $x_i$의 계수이다.
  • n보다 큰 정수 N이 있을 때 $x^N$의 계수는 0으로 정의한다.
  • 두 다항식의 등식 $f = g$는 각 차수의 계수가 같을 때만 정의한다.
  • zero polynomial는 모든 계수가 0인 다항식이다.
  • 차수 n은 계수가 0이 아닌 가장 높은 항의 지수
  • zero polynomial 의 차수는 $-\infty$ 
  • constant polynomial은 상수로만 이루어져있으며 변수가 포함되어 있지 않다.
• ex) $ R = (Z_6, +, \cdot) $에서 $5x^2 + 3x^1 -2x^0$ 과 $5x^2 + 3x^1 +4x^0$ 는 같다.
• $Z_6$에서 [4]는 [-2]와 같기 때문에

 

Closed Operations of Poly's (다항식의 닫힌 연산)

$f(x) = a_n x^n + a_{n-1} x^{n-1} + \dots + a_1 x^1 + a_0 x^0$

$g(x) = b_m x^m + b_{m-1} x^{m-1} + \dots + b_1 x^1 + b_0 x^0 \quad (n \geq m)$ 일 때,

• Addition
  • $f(x) + g(x) = \sum_{i=0}^{n} (a_i + b_i) x^i, \quad b_i = z \text{ for } i > m$ : 같은 차수에 있는 계수끼리 더한다.
• Multiplication 
  • $f(x)g(x) = \sum_{t=0}^{n+m} \left( \sum_{k=0}^{t} a_{t-k} b_k \right) x^t$ : 각 항의 곱을 계산한 후 차수에 따라 정리한다.

모든 덧셈과 곱셈 연산은 R 내에서 수행된다. (닫혀있다.)

 

 

Polynomial Ring

R이 ring이라면 R[x]의 다항식 연산(덧셈, 곱셈)에서도 ring이 된다.

• Polynomial ring R[x]에 대해
  
  • R이 commutative면 R[x]도 commutative이다 (교환법칙 성립)
  • R이 ring with unity이면, R[x]도 ring with unity이다. (곱셈 항등원)
  • R이 zero divisor가 없어 integral domain이 되면 R[x]도 integral domain이다.

Theorm about degree (다항식의 차수 정리)

R[x]에 속한 모든 zero polynomial이 아닌 f(x), g(x)에 대해
degree[f(x)g(x)] = degree[f(x)] + degree[g(x)] 일 때, R은 integral domain이 된다.

 

• ex) $x^0 = u$ 라고 가정한다.
• $Z_8$ 에서 $f(x) = 4x^2 + 1$ $ g(x) = 2x + 3$이라고 할 때
• $f(x)g(x) = {\color{Red} 8}x^3 + 12x^2 + 2x + 3 = 4x^2 + 2x + 3$ 이 된다.
• $deg[f(x)g(x)]  = 2 \neq 3 = deg[f(x)] + deg[g(x)]$ 이기 때문에 integral domain이 될 수 없다. (zero divisor가 존재한다.)

Root of Polynomial (다항식의 근)

R을 unity u가 존재하는 ring with unity로 정의하자
f(x)를 R[x]의 차수가 1이상인 다항식이라고 할 때
$r \in R$ 인 $f(r) = z$ 가 되면 r을 root of the polynomial이라고 한다.

• ex) R이라는 실수 집합이 있을 때
  • $f(x) = x^2 - 2 \in R[x]$이다. 여기에는 두 $\sqrt{2}, -\sqrt{2}$ root가 존재한다. 
  • 하지만 $f(x) = x^2 + 2 \in R[x]$ 에는 root가 없다. $i\sqrt{2}, -i\sqrt{2}$ 가 실수 범위에 포함되지 않기 때문에
• ex) $f(x) = x^2 + 3x + 2 \in Z_5[x]$ 
  • $f(0) = 2$
  • $f(1) = 6 = 1$
  • $f(2) = 12 = 2$
  • $f(3) = 20 = 0$
  • $f(4) = 30 = 0$
  • 두 개의 root  3과 4가 존재한다.

Polynomial Divisor or Factor

Field F와 F[x]에 속하는 f(x), g(x), h(x) 다항식이 있다. f(x)가 zero polynomial 이 아니고
f(x)h(x) = g(x) 일 때, f(x)는 g(x)의 divisor(factor)이다.

 

우리는 f(x)가 g(x)를 나눈다. g(x)는 f(x) 배수라고 할 수 있다.

• 0 : field의 zero element 또는 integral domain
• 1 : field의 unity 또는 integral domain

Division Algorithm

$f(x), g(x) \in F[x]$ 가 zero polynomial이 아닐 때

$g(x) = q(x)f(x) + r(x)$ 를 만드는 유일한 다항식 $q(x), r(x) \in F[x]$ 가 존재한다.

• 여기서 나머지 $r(x)$ 는 0 또는 $f(x)$ 보다 차수가 낮은 다항식이다. 

 

다항식 f(x)와 F의 임의의 원소 a에 대해 f(x)를 (x - a) 로 나눈 나머지는 f(a) 와 같다.

 

• ex) $f(x) = 3x^2 + 4x + 2$ 이고 $g(x) = 6x^4 + 4x^3 + 5x^2 + 3x + 1$ 이고 $Z_7[x]$에 속할 때

이런 q(x)와 r(x)로 표현 가능하다.

• ex) $f(x) = x^7 - 6x^5 + 5x^4 - x^2 + 3x +7$ 일 때, $f(x) = q(x)(x - 2)  + 9$ 이다.
  • $f(2) = 9$이기 때문에
• ex) $g(x) = x^5 + 3x^4 + x^3 + x^2 + 2x + 2 \in Z_5[x]$ 일 때
  • g(1) = 10 = 0이다. -> (x - 1)은 g(x)의 약수이다. 

Factor Theorem (인수 정리)

F[x]에 속하는 f(x)가 있을 때 a가 f(x)의 root일 때 (x - a)는 f(x)의 factor가 된다.
n(차수)이 1이상일 때, f(x)는 F에서 최대 n개의 root를 가질 수 있다.

• f(x)가 n의 차수를 가지면 $r_1, r_2, ... , r_n$의 root를 가지게 된다.
• f(x)는 다음과 같이 유일하게 표현될 수 있다. $\mathbf{f(x) = a_n(x-r_1)(x-r_2)...(x-r_n)}$
  • 여기서 $a_n$은 최고차항의 계수이다.

Inrreducible Polynomials

field F의 F[x]에 속하는 차수가 2이상인 f(x)가 있다.
$f(x) = g(x)h(x)$ 를 만족하는 차수가 1 이상인 g(x), h(x) 가 F[x]에 존재할 경우 f(x)는 reducible 이다.
만약 더 이상 분해할 수 없다면 irreducible 혹은 prime이라고 한다. 

 

• ex) $x^2 + 1$은 Q[x], R[x]에서 irreducible이다. 하지만 C[x]에서는 reducible하다 $(x - i)(x + i)$
• 차수가 1이하인 모든 다항식은 irreducible이다.
• 차수가 2 혹은 3인 다항식은 root가 있을 경우 reducible이다.
• 차수가 4 이상인 경우는 g(x)와 h(x)의 차수는 각각 2 이상이다.
  • root는 가지지 않지만 reducible한 경우가 있다. -> 4차 다항식 부터는 root로 판명하지 않는다.

 

Monic & gcd

F[x]에 속하는 다항식 f(x)의 최고 차항의 계수가 F의 unity일 때 monic이라고 한다.

다음 조건을 만족하면 F[x]에 속하는 다항식 f(x), g(x)에 대해 h(x)는 f(x)와 g(x)의 gcd가 될 수 있다.
1. h(x)가 f(x)와 g(x)를 나눈다. 
2. f(x)와 g(x)를 나누는 k(x)가 있을 때 h(x)는 k(x)에 의해 나눠진다.

• f(x)와 g(x)의 gcd는 나눌 수 있는 다항식 중 차수가 제일 높은 것으로 정의된다.
• f(x)와 g(x)의 gcd는 유일하다.

이는 정수의 gcd 계산과도 동일한데,  0이 아닌 두 정수 a, b의 gcd c는

1. c|a , c|b
2. 공통 약수 d에 대해서 d|c
3. gcd 연산에서 음수는 무시된다.

Euclidean Algorithm

$f(x), g(x) \in F[x]$ 그리고 $ deg[f(x)] \geq deg[g(x)]$에 대해 g(x)가 zero polynomial이 아니면 gcd(f(x), g(x))는 다음과 같이 계산될 수 있다. 
$$ gcd(f(x), g(x)) = gcd(g(x), r(x)) $$
$$ gcd (b(x), 0) = monic \  poly \ of \ b(x) $$ 
b(x)가 gcd가 된다.

 

Relatively Prime

$f(x), g(x) \in F[x]$ 이고 둘의 gcd가 F의 unity라면 f(x)와 g(x)는 relative prime이다. (서로소)

• ex) $Z_2[x]$ 에서 $f(x) = x^3 + x + 1$ 과 $g(x) = x + 1$ 은 서로소이다.
  • gcd (x^3+ x + 1, x+ 1) = gcd(x+ 1, 1) = gcd(1, 0) = 1 (F의 unity)