1. 개요
Euclidean domain유클리드 나눗셈[Euclidean division]이란 몫과 나머지가 있는 나눗셈이다. 가장 익숙한 예시로는 정수의 나눗셈이 있으며, 다항식의 나눗셈 또한 예시 중 하나이다. 현대대수학에서는 이를 일반화해 이런 나눗셈을 정의할 수 있는 구조를 유클리드 영역 또는 유클리드 정역이라고 한다.
2. 정의
집합 [math(R)]가 정역[integral domain]이라는 것은 [math(R)]에서 정의된 덧셈([math(+)])과 곱셈([math(\cdot)])이 다음을 만족한다는 것이다.- 임의의 [math(a, b, c (\in R))]에 대해 [math((a + b) + c = a + (b + c))]이다.
- 임의의 [math(a, b (\in R))]에 대해 [math(a + b = b + a)]이다.
- 임의의 [math(a (\in R))]에 대해 [math(a + 0_R = 0_R + a = a)]를 만족하는, [math(0_R (\in R))]이 존재한다.
- 임의의 [math(a (\in R))]에 대해, [math(a + b = b + a = 0_R)]을 만족하는 [math(b (\in R))]가 존재한다.[1]
- 임의의 [math(a, b, c (\in R))]에 대해 [math((a \cdot b) \cdot c = a \cdot (b \cdot c))]이다.
- 임의의 [math(a, b (\in R))]에 대해 [math(a \cdot b = b \cdot a)]이다.
- 임의의 [math(a (\in R))]에 대해 [math(a \cdot 1_R = 1_R \cdot a = a)]를 만족하는, [math(1_R (\in R))]이 존재한다.
- 임의의 [math(a, b, c (\in R))]에 대해 [math(a \cdot (b + c) = a \cdot b + a \cdot c, (a + b) \cdot c = a \cdot c + b \cdot c)]이다.[2]
- 임의의 [math(a, b (\in R))]에 대해 [math(a \cdot b = 0_R)]이면 [math(a = 0_R)] 또는 [math(b = 0_R)]이다.
정역 [math(R)]에 대해 함수 [math(f: R \setminus \{0_R\} \rightarrow \N)]가 유클리드 함수[Euclidean function]라는 것은 [math(f)]가 다음을 만족한다는 것이다.
- 임의의 [math(a (\in R))]와 임의의 [math(b (\in R \setminus \{0_R\}))]에 대해, [math(a = b q + r)] 이고, [math(r = 0_R)] 또는 [math(f(r) < f(b))]를 만족하는 [math(q, r (\in R))]가 존재한다.
유클리드 함수가 존재하는 정역을 유클리드 영역[Euclidean domain]이라고 한다.
3. 예시
3.1. 정수
자연수의 집합 [math(\N)]은 유클리드 영역이다. 이 경우 유클리드 함수는 항등함수이고, 나눗셈 정리에 의해 임의의 [math(a (\in \N))]와 임의의 [math(b (\in \N \setminus \{0\}))]에 대해 [math(a = b q + r, 0 \le r < b)]를 만족하는 [math(q, r (\in \N))]가 유일함까지도 알려져 있다.정수환 [math(\Z)]의 경우에도 비슷하게 할 수 있는데, 이때의 유클리드 함수는 절댓값 함수이다. 정수환에서는 유일성이 성립하지 않는데, 그래서 프로그래밍 언어에서의 유클리드 나눗셈과 나머지 연산은 언어마다 다르게 정의돼 있다.
- 몫의 소수부분을 버리는 방식: 버림 나눗셈[truncated division]이라고 하며, 몫을 [math(0)] 방향에서 가장 가까운 정수로 한다. 나머지의 부호가 피제수와 같다는 특징이 있다. C, Java 등 많은 언어에서 쓰이는 방식이다.
- 몫에 바닥함수를 씌우는 방식: 바닥 나눗셈[floored division]이라고 하며, 몫을 음의 방향에서 가장 가까운 정수로 한다. 나머지의 부호가 제수와 같다는 특징이 있다. Python, Rust 등의 언어에서 쓰인다.
- 나머지가 [math(0)] 이상이도록 하는 방식: 유클리드 나눗셈[Euclidean division]이라고 하며, 나머지가 [math(0)] 이상이도록 한다. 거의 쓰이지 않는다.
3.2. 다항식
계수가 환의 원소인 다항식의 집합도 유클리드 영역이며, 이 때의 유클리드 함수는 차수 함수이다. 다항식의 나눗셈 정리에 의해 임의의 [math(m)]차 다항식 [math(f)]와 임의의 [math(n (\ge 0))]차 다항식[3] [math(g)]에 대해 [math(f = g q + r, \deg r < \deg g)]를 만족하는 다항식 [math(q, r)]가 유일함까지도 알려져 있다.3.3. 임의의 체
임의의 체 [math(F)]는 유클리드 영역인데, 이 때의 유클리드 함수는 상수함수[4]이다. 사실 이 경우 유클리드 함수는 중요치 않은데, 나머지가 항상 [math(0_F)]이 되도록 나눗셈을 정의하면 되기 때문이다. 여기서 유클리드 나눗셈과 일반적인 체의 나눗셈 사이의 관계를 알 수 있다.[1] 여기까지 만족하는 구조를 아벨 군[Abelian group]이라고 한다.[2] 여기까지 만족하는 구조를 가환환[commutative ring]이라고 한다. 곱셈의 항등원의 존재성을 환의 조건으로 보지 않는 경우에는 ‘[math(1)]을 가지는 가환환’이라고 표현하기도 한다.[3] 여기서 영다항식의 차수는 [math(-1)]로 정의한다.[4] 보통 유클리드 함수가 곱셈적이도록 [math(f(x) = 1)]로 정의한다.