4장 polynomial arithmetic
우리는 이번 장에서 polynomial ring에 대해 다룬다. polynomial ring이란? 계수가 ring의 원소인 polynomial들의 집합에 우리가 알고 있는 연산들이 적절히 들어갔다고 보면 되겠다.
요정도 생각에서 시작합시다.
4.1 Division algorithm
알고 갈 가벼운 사실 목록
-
두 polynomial이 같다는 것? 두 개의 polynomial이 존재할 때를 생각하자. 1번 n차 polynomial, 2번 m차 polynomial이라고 하자. 만약 n<m이면? 2번에서 n+1차 이상의 항의 계수들은 모두 0이다!
-
+,-,*는 우리가 알고 있는 연산으로 갑시다.
-
x는 indeterminate라고 부를게요~. 결정이 아직 안된거지!
-
R[x]는 R(ring)의 원소를 계수로 갖는 polynomial이다. 그런데? R은 R[x]의 부분집합이다. 왜냐면 상수항을 고려했을때
-
만약 R에 1(identity)가 존재한다면 R[x]에도 1이 존재한다. 만약 없다면? R[x]에는 x가 없다! 왜? x는 계수를 1로 가지니까. 그래서 왠만하면 우리는 ring with identity를 고려한다.
-
R이 commutative이면 R[x]도 마찬가지이다. 만약 아니라면? R[x]도 아니다. 뭐 당연할지도?
정의 1번 degree와 leading coefficient
혹시 몰라 이야기하면 coefficient는 계수를 의미한다.
큰 차수부터 썼을 때
0이 아닌 계수를 가장 먼저 가지는 항의 coefficient를 leading coefficient라고 한다.
또한 그 때 n차항의 degree를 polynomial의 degree라고 한다. deg(f(x)) = n
n = 0이면 아마 constant polynomial인데 잘못 쓴 듯.
polynomial 0의 차수는 정의하지 않는다. 만약 따지면 -무한대 정도?
나중에 대충 이유를 알 수 있다.
정리 1번 Thm4.2
R이 integral domain이면 0이 아닌 f(x)와 g(x)간 deg(f(x))+deg(g(x)) = deg(f(x)g(x))가 성립한다.
-intergral domain이란? 곱한게 0이면 둘 중 하나는 0인 commutative ring with identity.
Sketch)두 다항식을 곱해서 0이 아닌 항을 곱했을 때 그 결과 0이 아닌게 보장되므로 각 deg의 합이 곱한 것의 deg가 된다.
자세한 증명은 위에!
Cor 1번 Cor4.4
f(x),g(x),f(x)g(x)가 nonzero polynomial이면 deg(f(x)g(x))<=deg(f(x))+deg(g(x))
곱했다고 없던 차수가 생겨서 늘어나는 일은 없다는 뜻이지. integral domain이 아니면 심지어 줄어들 수도 있다!
Cor 2번 Cor4.5
R : integral domain, f(x)는 R에 속한다.
1)만약 f(x)가 unit이다? 그러면 constant u이고. 이 u는 원래 ring R에서도 unit이다.
2)만약 원래 ring F가 field이다. 그러면 F[x]의 unit들은 f의 0이 아닌 원소들이다.
Proof Sketch)
2)은 1)과 같은 맥락이다. Field는 정의가 0이 아니라면 모두 unit이니까 말이다.
1)은 그럼 뭘까? 다항식의 차수는 nonzero이다. 즉 서로 곱해서 차수를 줄일 수가 없다.(integral domain이니깐) 그럼 1차 이상 녀석들은 1로 만들 수가 없다. 즉 unit이 될 수가 없다. unit은 1로 만들어야 하기 때문이다. 즉, unit은 차수가 없는 constant 중에서 있고 그 unit들은 원래 ring R의 unit이다.
Division algorithm for polynomials
우리가 고등학교 때 배운 그 친구가 맞다!
중요 point는 우리를 division algorithm을 Field에서 정의할 것이라는 것이다.
그 이유는 우리가 적절한 수를 곱해 같게 만들어 subtraction할 것이기 때문이다...!
정리 2번 Thm 4.6 Division algorithm
F를 field라고 하자. f(x),g(x) 중 g(x)만 0이 아니라고 합시다.
그러면 unique한 h(x)와 r(x)가 존재해서,
f(x) = h(x)g(x)+r(x)이고 r(x)의 차수는 g(x)보다 작거나 r(x)는 0이다.
증명은 induction으로 한다.
h(x)는 몫이고 r(x)는 나머지다.
proof sketch)
1. existence
골자는 상태 A가 모든 상황에서 유지가 된다는 것을 보이고 싶은 것이다. A는 위에서 확인하시라. A는 division algorithm을 이야기한다.
mathematical induction을 사용하자.
먼저는 case1. 0을 나누거나 나누어지는 polynomial f(x)의 차수가 g(x)보다 작은 경우이다.
이런 상황에는 몫 h(x)를 0으로 잡고 r(x)를 f(x)로 잡으면 깔끔하게 성립한다.
case2. f(x)가 0이 아니고 g(x)의 차수보다 크거나 같은 상황을 가정하자.
이 때 induction을 사용할건데 우리가 사용할 induction은 strong induction으로 deg가 1부터 n-1까지 다 성립한다고 가정한다.
Basis step) deg(f(x))가 0일 때. 이 때는 deg(g(x))도 0이다.
우리는 field에서 원소를 가져오기 때문에 deg(f(x)) = 0 이고 f(x)가 0이 아니라면 f(x)는 unit이다. 고로 g(x)도 unit이다.
f(x) = a, g(x)를 b라고 하자. 그러면 a = b(b^(-1)a)이다. 즉 g(x)에 대해 h(x)가 b^(-1)*a로 존재하고 r(x) = 0으로 존재한다.
Inductive step) 자 f(x)의 degree가 n보다 작을 때 상태 A가 다 성립한다고 하자. 그러면 f(x) = g(x)h(x) + r(x) 꼴로 나올까? 그리고 그 때 deg(g(x))>deg(r(x))일까?
자 h(x)를 anbm^(-1)x^(n-m)으로 잡자. 왜냐면 g(x)의 leading one을 f(x)의 leading one과 같게 만들어주기 위해서다. g(x)h(x)의 leading one은 f(x)의 leading one과 같은 값이 된다!
이 때 f(x)-g(x)h(x)를 p(x)라고 하자. 그러면 p(x)의 degree는 f(x)의 degree보다 작거나 p(x)는 0이다.
0인 경우는 그냥 f(X) = g(x)h(x)인 것이고, p(x)의 degree가 f(x)보다 작은 상황이 중요하다.
1)(deg(p(x))>deg(g(x)) case)
p(x)의 degree가 f(x)보다 작다면 우리의 원래 가정에 따라 f(x)보다 작은 degree에서는 모두 상태 A, 즉 division algorithm이 성립하므로 p(x) = g(x)h0(x)+r0(x)로 쓸 수가 있다.
즉 f(x) = g(x)p(x) = g(x)(g(x)h0(x))+g(x)r0(x) = g(x)h(x)+r(x).
2)(deg(p(x))<deg(g(x)) case)
아까 case1에서 보임.
즉 f(x)는 g(x)h(x)+r(x)꼴로 쓸 수가 있음.
2.uniqueness
너무 쉬움. 그냥 두 개 존재한다고 하고 서로 같음을 보이자. 끝.
4.2 Divisibility
정의 2번
f(x) = g(x)h(x) 꼴로 쓰여질 때 divide한다고 한다. 이 때 ring은 field.
정리 3번 property of divisibility
- g(x)가 f(x)를 나눈다면 0이 아닌 c에 대해 c*g(x)도 나눈다.
- g(x)가 f(x)를 나누면 g(x)의 차수보다 작거나 같다.
증명은 너무 쉽고 직관적 이해가 가능해 생략.
정의 4번 monic polynomial과 gcd
- monic : 최고차항의 계수가 1인 polynomial을 monic polynomial이라고 한다.
- gcd : monic polynomial d(x)가 f(x)와 g(x)를 나누고 다른 모든 common divisor보다 차수가 크다.
(ring에서의 정의와 흡사하다.)
example 그림에서 확인할 것
정리 4번
f(x)와 g(x)의 gcd d(x)는 어떤 u(x),v(x)에 의해 f(x)u(x)+g(x)v(x)로 표현할 수 있다.(ring에서의 gcd와 동일)
proof sketch)
1. ring에서 gcd처럼 well-ordering axiom으로 최소원소를 뽑은 것처럼 최저차항의 식 d(x)를 monic으로 뽑는다.
2. division algorithm에 의해 f(x)와 g(x)를 나누는 것을 보여 common divisor임을 보인다.
3. 모든 common divisor가 d(x)를 나눔을 보임으로서 가장 차수가 큼을 보인다. 즉 gcd.
정리 5번 f(x)|g(x)h(x) and (f(x),g(x)) = 1 => f(x)|h(x)
proof sketch) f(x)와 g(x)의 gcd를 정리 4번의 형식으로 확장한 후 양변의 h(x)를 곱한 후에 이 식이 f(x)로 나누어짐을 보임.
어우 길다. 길어. ring을 polynomial로 확장한다는 생각은 참 좋은 듯하다. 하루 빨리 갈루아의 5차 이상의 방정식의 근의 공식이 존재하지 않는다는 생각에 도달했으면 좋겠다아아아. 화이팅!
