5.1,5.2 Congruence in F[x], Congruence class arithmetic

서론

우리는 정수에서의 합동 관계에 대해 2장에서 알아보았습니다. 정수는 ring이었는데요. 그 합동관계를 이용하여 우리는 $Z_n$이라는 ring을 구상하였습니다. $Z_n$은 n으로 나눴을 때 나머지가 같은 정수들을 모아 놓은 ring입니다. 우리는 polynomial ring이라는 것도 4장에서 열심히 정의하였는데요. 이에 더하여 어떤 polynomial p(x)로 나누었을 때 나머지가 같은 친구들은 같은 것으로 간주하는 ring F[x]/p(x)에 대해 알아봅시다.

5.1 Congruence in F[x]

definition of congruence

F를 field라고 하고 P(x)의 degree가 1이상이라고 하자. 이 때 f(x) is congruent to g(x) if $p(x)|(f(x)-g(x))$. Write $f(x)≡g(x)mod(p(x))$.

example) F 를 유리수집합이라고 합시다.
$f(x) = x^3+1, g(x) = x+1, p(x) = x^2-1$이라고 하면, $f(x)-g(x) = x^3-x$이고 이는 p(x)로 나누어지므로 $x^3+1≡x+1mod(x^2+1)$이라고 할 수 있겠습니다.

equivalent class

앞서 정수에서 본 congruence들의 집합은 equivalence relation이었습니다. equivalence relation이면 정수들을 partition할 수 있습니다. 쉽게 말해 정수들을 하나도 빠짐없이 겹침 없이 잘 나눌 수 있다는 건데요. 예를 들어 $Z_2$는 정수를 짝수와 홀수로 나누어준다고 생각할 수 있겠습니다. 우리가 새로 정의한 congreuce도 equivalence relation을 가질지 확인해봅시다.

Thm5.1 f(X),g(x),p(x)를 F[x]에서 가져왔다고 하고 $deg(p(x))\geq 1$라고 합시다.
(1) reflexive $f(x)≡f(x)$ $mod(p(x))$
(2) symmetric $f(x)≡g(x)$ $mod(p(x))$=>$g(x)≡f(x)$ $mod(p(x))$
(3) transitive $f(x)≡g(x)$ $mod(p(x))$ and $g(x)≡h(x)$ $mod(p(x))$ => $f(x)≡h(x)$ $mod(p(x))$
congruence relation is an equivalence relation

직관적으로 생각해봅시다.
(1)자기 자신과 자기 자신은 당연히 나머지가 같겠죠? 그 차를 생각해보면 0인데 어떤 수든 0을 나눌 수 있습니다.
(2) 나머지는 위치를 바꾸어도 당연히 같을겁니다. 정의에 따라 생각해보면 f(x)-g(x)를 p(x)가 나눈다는 것인데 그러면 $f(x)-g(x) = p(x)k(x)$로 쓸 수 있을테고 즉, $g(x)-f(x) = p(x)(-k(x))$로 쓸 수가 있겠네요. 즉 p(x)는 g(x)-f(x)도 나눕니다.
(3) 나머지가 2개, 2개씩이 같은 상태입니다. 물론 성립합니다.

Thm5.2

f(x)≡g(x) mod(p(x)), h(x)≡k(x) mod(p(x))
(1) f(x)+h(x) ≡ g(x)+k(x) mod(p(x))
(2) f(x)h(x) ≡ g(x)k(x) mod(p(x))

증명은 생략하겠습니다. 쉽습니다.

def F[x]/p(x)

F[x]/p(x) = (set of all congruence classes modulo p(x))

F[x]라는 field의 원소를 가지고 만든 polynomial의 집합에서 congruence class들로 묶은 집합입니다.
$Z_n$과 동일하게 생각하시면 되겠습니다.

Cor 5.5

(1)[f(x)] = [r(x)] where r(x) is remainder when f(x) is divided by p(x).
(2) S := {r(x)∊F[x] | deg(r(x))<n or r(x) = $0_F$}
Then there exist 1-1 correspondence between S and F[x]/p(x)

제가 위에서 간간히 나머지가 같다라는 표현 등을 써왔으나 아직까지 사실 congruence의 의미는 두 다항식의 차를 p(x)가 나눈다입니다. 그런데 p(x)는 division algorithm에 따라 unique하게 다항식들을 나누고 만약 두 다항식의 나머지가 같다면 그 차를 p(x)가 나누리라는 것을 쉽게 생각해볼 수 있습니다.

한 단계 더 나아가 생각한다면 결국 나머지가 같은 녀석들은 같은 equivalent class 중에서도 congruent class로 묶을 수 있겠고 결국 F[x]/p(x)의 원소에는 p(x)로 나누었을 때 나머지가 될 수 있는 다항식들이 있게 될 것입니다.

(1)이 의미하는 바는 어떤 다항식 f(x)와 그 나머지가 같은 congruence class에 속해있다는 것이고 (2)는 결국 가능한 나머지들만 모아 놓으면 그것이 F[x]/p(x)를 표현한다는 의미입니다.

proof sketch)
(1) f(x)에 division algorithm을 사용한다면 unique q(x),r(x)가 존재해서 r(x) = 0 or deg r(x)<n이고 f(x) = p(x)q(x) + r(x)로 표현됩니다. 즉 f(x)-r(x) = p(x)q(x)이므로 p(x)로 나누어지니 f(x) ≡ r(x)이고 [f(x)] = [r(x)]가 성립합니다.

1-1 correspondence가 존재한다는 것은 결론적으론 S가 F[x]\p(x)를 표현하기에 적당하다는 것을 보여줍니다.
S에서 F[x]/p(x)로 가는 함수를 ∅라고 합시다. S에는 r(x)가 속해있고 F[x]/p(x)에는 [r(x)]가 속해 있습니다. [r(x)]는 r(x)와 congruent한 모든 polynomial의 집합입니다.
이 때 ∅가 injective이고 surjective이면 1-1 correspondence가 존재한다고 할 수 있습니다.

(2) surjective : 모든 [f(x)]∈F[x]/p(x) 마다 적당한 [r(x)]가 존재해서 [f(x)] = [r(x)] 겠죠? (By division algorithm) 이 때 적당한 r(x)가 존재해서 ∅(r(x)) = [r(x)]이므로 surjective 만족입니다.

injective : $[r_1(x)] = [r_2(x)]$라고 합시다. 그러면 $[r_1(x)-r_2(x)] = [0]$ 이고 즉 $r_1(x)-r_2(x) ≡ 0$ mod(p(x))입니다. 이 때, $r_1(x)-r_2(2)$가 0이 아니라면 p(x)가 $r_1(x)-r_2(2)$를 나눠야만 하는데 그러기 위해선 p(x)의 차수가 $r_1(x)-r_2(2)$의 차수보다 작아야하는데 $r_1(x),r_2(2)$<n = deg(p(x))라고 했으므로 모순입니다. 즉 $r_1(x) = r_2(2)$입니다.

example

$Z_3[x]/(x^2+1)$ = {${[0],[1],[2],[x],[x+1],[x+2],[2x],[2x+1],[2x+2]}$}

remark)$Z_3[x]은 Z_3$을 subring으로 가진다.

Thm 5.7

F:field. deg(P(x))≥1
(1) F[x]/p(x) is a commutative ring with identity.
(2) F[x]/p(x) contains a subring $F^*$ isomorphic to F.

proof sketch)
(1)은 [r(x)] in F[x]/p(x)의 r(x)가 field에서 왔기 때문에 commutative는 자연스럽게 성립합니다. F[x]는 commutative ring with identity이기 때문입니다. 1의 존재성에 대해서는 나중에 증명해보고 다시 적겠습니다.
(2)은 바로 위의 remark에 적은 것 같이 성립합니다. $F^*$를 [a]집합으로 택한다음 a∈F -> [a]∈$F^*$인 map을 가져오고 injective surjective homomorphism을 보이면 되겠습니다.

---

아우 존댓말쓰기 어렵네요 ㅋㅋㅋ
뭔 congruence를 찾을 수 있는 곳에서는 다 찾고 싶어하네요.