나눗셈 정리

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요

나눗셈 정리는 주어진 수나 다항식을 다른 수나 다항식으로 나누었을 때 몫과 나머지를 얻는 수학적 개념을 설명한다. 정수 나눗셈 정리, 다항식 나눗셈 정리로 구분되며, 특히 체(field)의 경우 다항식 나눗셈 정리는 인수분해, 최대공약수, 최소공배수 계산에 중요한 도구이다. 몽고메리 나눗셈과 같은 변형된 형태도 존재하며, 합동식, 잉여 연산, n진법 전개, 유클리드 호제법, 유클리드 정역, 다변수 다항식 나눗셈 등 다양한 분야에 응용된다. 다변수 다항식 나눗셈에서는 몫과 나머지가 유일하지 않지만, 그뢰브너 기저를 사용하면 유일성을 확보할 수 있으며, 부흐베르거 알고리즘은 그뢰브너 기저를 계산하는 데 사용된다.

더 읽어볼만한 페이지

나눗셈 - 약수
약수는 정수 b=ac를 만족하는 정수 c가 존재할 때 a를 b의 약수라고 정의하며, 모든 정수는 1, -1, 자기 자신, 반수를 약수로 가지고, 이외 약수를 고유 약수, 자연수에서는 자기 자신을 제외한 양의 약수를 진약수라고 부른다.
나눗셈 - 나머지
나머지는 정수 나눗셈에서 나누어 떨어지지 않고 남는 값으로, 최소 양의 나머지 및 최소 절대 나머지로 구분되며, 모듈러 연산, 다항식 나눗셈, 프로그래밍 언어, 암호화 기술 등 다양한 분야에서 활용된다.
수론 정리 - 페르마의 마지막 정리
페르마의 마지막 정리는 3 이상의 정수 n에 대해 xⁿ + yⁿ = zⁿ을 만족하는 양의 정수 x, y, z는 존재하지 않는다는 정리이며, 앤드루 와일스가 모듈러성 정리를 이용하여 1995년에 증명했다.
수론 정리 - 라그랑주 네 제곱수 정리
라그랑주 네 제곱수 정리는 모든 양의 정수를 네 개의 정수 제곱수의 합으로 나타낼 수 있다는 정리이다.
환론 - 뇌터 환
뇌터 환은 환론에서 아이디얼의 특정 조건을 만족하는 환을 지칭하며, 가환환의 경우 왼쪽, 오른쪽, 양쪽 뇌터 환의 개념이 일치하지만 비가환환의 경우 구별해야 하고, 힐베르트 기저 정리에 따라 뇌터 환 $R$ 에 대해 다항식환 $R[X]$ 역시 뇌터 환이 된다.
환론 - 다항식환
다항식환은 환을 계수로 하는 다항식들의 집합으로, 덧셈과 곱셈 연산에 대해 환을 이루며, 계수환이 체일 경우 유클리드 정역이 되고 대수기하학 등 다양한 분야에서 중요한 역할을 한다.

2. 정의

유클리드 나눗셈은 때때로 '유클리드의 나눗셈 보조정리'라고 불리는 다음 결과에 기초한다.

두 정수 와 가 주어지고, 일 때, 다음을 만족하는 유일한 정수 와 이 존재한다.^[4]

:

:

여기서 는 의 절댓값을 나타낸다.

위 정리에서, 네 정수는 각각 고유한 이름을 갖는다. 는 피제수, 는 제수, 는 몫, 은 나머지라고 불린다. 피제수와 제수로부터 몫과 나머지를 계산하는 것을 나눗셈, 또는 모호한 경우 유클리드 나눗셈이라고 한다.

인 경우 나눗셈은 정의되지 않는다. 0으로 나누기를 참조.

나눗셈 정리는 정수뿐만 아니라, 일변수 다항식에 대한 체 및 유클리드 정역으로 일반화될 수 있다.

2. 1. 정수 나눗셈 정리

두 정수 m, n (n ≠ 0)이 주어졌을 때, 다음 두 조건을 만족하는 정수 q(몫)와 r(나머지)이 유일하게 존재한다.^[4]

m = nq + r
0 ≤ r < |n|

여기서 |n|은 n의 절댓값이다. 이때 q를 m을 n으로 나눈 몫, r을 나머지라고 한다. m, n으로부터 몫 q와 나머지 r을 얻는 연산을 '''나머지 있는 나눗셈'''이라고 한다. 추상대수학의 관점에서, 나눗셈 정리는 정수환이 유클리드 정역임을 나타낸다.

2. 2. 다항식 나눗셈 정리

원래는 정수로 제한되었지만, 유클리드 나눗셈과 나눗셈 정리는 일변수 다항식에 대해 체와 유클리드 정역으로 일반화될 수 있다.

일변수 다항식의 경우, 주요 차이점은

0\le r<|b|

의 부등식이 다음으로 대체된다는 것이다.

:

r = 0

또는

\deg r < \deg b,

여기서

\deg

는 다항식 차수를 나타낸다.

유클리드 정역으로의 일반화에서, 부등식은 다음과 같다.

:

r = 0

또는

f(r) < f(b),

여기서

f

는 정역에서 자연수로의 특정 함수를 나타내며, "유클리드 함수"라고 불린다.

몫과 나머지의 유일성은 다항식에 대해서는 여전히 유지되지만, 일반적으로는 성립하지 않는다.
주장: 주어진 두 다항식 ''P''(''x'') 및 ''M''(''x'') ≠ 0에 대해, ''P''(''x'') = ''Q''(''x'')''M''(''x'') + ''R''(''x'') (deg ''R'' < deg ''M''(''x''))가 성립하는 다항식 ''Q''(''x'') 및 ''R''(''x'')가 유일하게 존재한다.

3. 역사

피보나치가 13세기에 인도-아라비아 숫자를 유럽에 소개하기 전까지 나눗셈은 매우 어려운 작업이었고, 최고의 수학자들만이 이를 수행할 수 있었다. 현재 필산을 포함한 대부분의 나눗셈 알고리즘은 인도-아라비아 숫자 표기법이나 이진법과 같은 변형에 기반한다. 뉴턴-랩슨 나눗셈은 어떤 기수법에도 독립적이라는 점에서 주목할 만한 예외이다.

"유클리드 나눗셈"이라는 용어는 20세기에 "유클리드 환의 나눗셈"을 줄여 부르는 말로 도입되었다. 수학자들은 이 용어를 숫자의 다른 종류의 나눗셈과 구별하기 위해 빠르게 채택하였다.^[1]

유클리드의 이름을 따서 "유클리드 나눗셈"이라고 명명되었지만, 유클리드가 존재와 유일성 정리를 알지 못했고, 그가 아는 유일한 계산 방법은 반복 뺄셈에 의한 나눗셈뿐이었던 것으로 보인다.^[2]

4. 직관적인 예시

파이가 9조각이고 4명에게 똑같이 나누어 준다고 가정해 보자. 나눗셈 정리를 사용하면 9를 4로 나눈 몫은 2이고 나머지는 1이다. 즉, 각 사람은 파이 2조각을 받고 1조각이 남는다.

이것은 곱셈을 사용하여 확인할 수 있다. 4명이 각자 2조각씩 받으면 총 4 × 2 = 8조각이 분배된다. 남은 1조각을 더하면 결과는 9조각이 된다. 요약하면, 9 = 4 × 2 + 1이다.

일반적으로, 조각의 수를 ''a''라고 하고 사람의 수를 ''b''라고 하면, 각 사람이 ''q''조각(몫)을 받고, r < b 조각의 남는 조각(나머지)이 생기도록 파이를 사람들에게 균등하게 나눌 수 있다. 이 경우, 방정식 a = bq + r이 성립한다.

만약 9조각을 4명이 아닌 3명에게 나누어 준다면, 각 사람은 3조각을 받게 되고 남는 조각은 없으므로, 나머지는 0이 된다. 이는 3이 9를 나누어 떨어뜨린다는 결론, 즉 3이 9를 나눈다는 결론으로 이어진다.

나눗셈 정리는 동일한 공식을 사용하여 음의 피제수(또는 음의 제수)로도 확장할 수 있다. 예를 들어, −9 = 4 × (−3) + 3인데, 이는 −9를 4로 나누면 몫은 −3이고 나머지는 3임을 의미한다.

5. 예시

$a=7$ 을 $b=3$ 으로 나눈 몫은 $q=2$ , 나머지는 $r=1$ 이다 ( $7=3\times 2+1$ ).^[9]
파이가 9조각이고 4명에게 똑같이 나누어 준다고 가정하면, 각 사람은 파이 2조각을 받고 1조각이 남는다. 4명이 각자 2조각씩 받으면 총 4 × 2 = 8조각이 분배된다. 남은 1조각을 더하면 결과는 9조각이 된다. 즉, 9 = 4 × 2 + 1이다.
만약 9조각을 3명에게 나누어 준다면, 각 사람은 3조각을 받게 되고 남는 조각은 없으므로, 나머지는 0이 된다.
유클리드 나눗셈은 음의 피제수(또는 음의 제수)로도 확장할 수 있다. 예를 들어, −9 = 4 × (−3) + 3인데, 이는 −9를 4로 나누면 몫은 −3이고 나머지는 3임을 의미한다.

다음은

a

와

b

값에 따른 몫(

q

)과 나머지(

r

)를 계산한 예시이다.

''a'' = 7, ''b'' = 3 이면, 7 = 3 × 2 + 1 이므로 ''q'' = 2, ''r'' = 1 이다.
''a'' = 7, ''b'' = −3 이면, 7 = −3 × (−2) + 1 이므로 ''q'' = −2, ''r'' = 1 이다.
''a'' = −7, ''b'' = 3 이면, −7 = 3 × (−3) + 2 이므로 ''q'' = −3, ''r'' = 2 이다.
''a'' = −7, ''b'' = −3 이면, −7 = −3 × 3 + 2 이므로 ''q'' = 3, ''r'' = 2 이다.

6. 증명

나눗셈 정리의 증명은 몫과 나머지의 존재성과 유일성을 모두 보이는 것이다. 이 증명은 감소하는 음이 아닌 정수 수열이 결국 멈춘다는 사실에 기반한다.^[5] 다른 증명들은 잘 정렬 원리를 사용하여 추론을 단순화하지만, 나눗셈을 풀기 위한 알고리즘을 직접 제공하지는 않는다.^[5]

6. 1. 존재성

체

K

에서 계수를 취하는 다항식

f, g \in K[x]

가 주어졌고,

g(x) \ne 0

일 때, 다음 두 조건을 만족시키는 다항식

q, r \in K[x]

가 존재한다.^[5]

$f(x) = g(x)q(x) + r(x)$
$\deg r < \deg g$

이를 증명하기 위해, 감소하는 음이 아닌 정수의 수열이 결국 멈춘다는 사실을 이용한다.

b > 0

이라고 가정할 수 있는데, 만약

b < 0

이면

a = bq + r

는

a = (-b)(-q) + r

로 다시 쓸 수 있기 때문이다. 따라서

-b > 0

인 경우의 유클리드 나눗셈이 존재하면, 원래 경우도 유클리드 나눗셈이 존재한다.

주어진

b > 0

과

a

에 대해,

a = bq_1 + r_1

을 만족하는 정수

q_1

과

r_1 \ge 0

이 존재한다. 예를 들어

a \ge 0

이면

q_1 = 0

이고

r_1 = a

이며, 그렇지 않으면

q_1 = a

이고

r_1 = a - ab

이다.

r

이 음이 아니고 최소인 그러한 수의 쌍을

q

와

r

이라고 하자. 만약

r < b

이면, 유클리드 나눗셈을 갖는다. 따라서

r \ge b

이면

r

이 최소가 아님을 증명해야 한다. 실제로, 만약

r \ge b

이면,

a = b(q+1) + (r-b)

를 가지며, 여기서

0 \le r-b < r

이고,

r

은 최소가 아니다.

이것은 모든 경우에 몫

q

와 나머지

r

의 존재성을 증명한다.

q = 0

에서 시작하여 (

a \ge 0

인 경우)

a-bq < b

가 될 때까지

1

을 더하여 몫과 나머지를 계산하는 알고리즘을 생각할 수 있지만, 이 알고리즘은 단계 수가

a/b

의 크기를 가지므로 효율적이지 않다.^[5]

6. 2. 유일성

Euclidean division|유클리드 나눗셈^영어 정리에서 몫과 나머지가 유일함을 증명하는 방법은 다음과 같다.

먼저, 다음 조건을 만족하는 두 가지 나눗셈 표현이 있다고 가정한다.

여기서 은 0이 아닌 정수이고, 과 은 각각 와 로 나누었을 때의 나머지이다.

위 두 식을 빼면 다음 식을 얻는다.

:

이 식은 가 의 약수임을 의미한다. 또한, 과 에 대한 부등식에 의해 다음이 성립한다.

:

따라서 이고, 이다.

이므로, 결국 이고 가 된다. 이는 처음에 가정한 두 나눗셈 표현이 동일함을 의미하며, 따라서 몫과 나머지는 유일하다.^[5]

7. 효과성

나눗셈 정리의 몫과 나머지를 구하는 실제적인 방법으로 장제법이 있다. 1차 다항식으로 나눌 경우 조립제법을 사용할 수 있다. 다항식 나머지 정리에 따라, 다항식의 정의역 속 원소에 대한 값은 조립제법을 통해 구할 수 있으며, 이는 다항식의 통상적인 전개를 통한 계산보다 덜 복잡하다.

반복 뺄셈에 의한 나눗셈은 몫의 크기만큼 많은 단계가 필요하기 때문에 효율적인 알고리즘은 아니지만, 곱셈을 포함하지 않고 정수의 덧셈, 뺄셈, 비교만 사용한다는 특징이 있다.

십진법으로 보면, 필산 나눗셈은 유클리드 나눗셈을 위한 훨씬 더 효율적인 알고리즘이다. 이를 이진법 및 16진법으로 일반화하면 컴퓨터 구현에 대한 더 많은 유연성과 가능성을 제공한다. 대규모 입력의 경우, 뉴턴-랩슨 나눗셈과 같이 나눗셈을 곱셈으로 줄이는 알고리즘이 일반적으로 선호된다. 이러한 알고리즘은 사용되는 곱셈 알고리즘과 관계없이 결과를 확인하는 데 필요한 곱셈 시간에 비례하는 시간만 필요하기 때문이다(나눗셈 알고리즘#고속 나눗셈 방법 참조).

8. 변형

환 $R$ 에서 계수를 취하는 다항식 $f\in R[x]$ 가 주어졌고, $R$ 를 부분환으로 갖는 환 $S$ 의 원소 $a\in S$ 가 $R$ 의 모든 원소와 가환한다고 하자(임의의 $b\in R$ 에 대하여, $ab=ba$ ). '''나머지 정리'''(-定理, remainder theorem^영어)에 따르면, $f(x)$ 를 $x-a$ 로 나눈 나머지는 $f(a)$ 이다.^[1]

특히, 만약 $S$ 가 가환환일 경우, 임의의 $a\in S$ 에 대하여 나머지 정리가 성립한다.^[1]

유클리드 나눗셈은 여러 변형을 허용한다. 예를 들어 나머지를 항상 0과 제수의 절대값 구간에 두는 대신, 다른 구간을 선택할 수도 있다.

8. 1. 나머지에 대한 다른 구간

나머지를 항상 \[0, |''d''|) 구간에 있도록 하는 대신, 다른 구간을 선택할 수도 있다. 예를 들어, 중심 나눗셈에서는 나머지를 \[−|''d''|/2, |''d''|/2) 구간에 있도록 한다.

또 다른 방법은 최소 절대 나머지를 사용하는 것이다. 이 경우, ''n'' = ''am'' + ''b'' (|''b''| < |''m''|)를 만족하는 정수 ''a''와 ''b''를 찾는다. 하지만 이 경우 나머지가 유일하지 않을 수 있다. 예를 들어, ''a'' = 7, ''b'' = −3일 때 다음과 같이 두 가지 분해가 가능하다.

7 = (−2)(−3) + 1
7 = (−3)(−3) − 2

위의 두 경우 모두 |1| < |−3| 과 |−2| < |−3| 이 성립한다.

나머지의 유일성을 보장하려면 추가적인 조건이 필요하다. 예를 들어, "피제수가 음수일 때는, 피제수와 절대값이 같은 자연수를 취하고, 그것을 나눗셈한 다음 다시 부호를 바꾼다"는 방식을 사용할 수 있다. 하지만 이 또한 널리 사용되는 방법 중 하나일 뿐이며, 계산기나 프로그래밍 언어에 따라 나머지를 계산하는 방식이 다를 수 있으므로 주의해야 한다.

8. 2. 몽고메리 나눗셈

주어진 원문에 몽고메리 나눗셈에 대한 내용이 없으므로, 해당 섹션은 작성할 수 없습니다. 이전 답변과 동일합니다.

9. 응용

환 $R$ 에서 계수를 취하는 다항식 $f\in R[x]$ 가 주어졌고, $R$ 를 부분환으로 갖는 환 $S$ 의 원소 $a\in S$ 가 $R$ 의 모든 원소와 가환한다고 하자. (임의의 $b\in R$ 에 대하여, $ab=ba$ ). '''나머지 정리'''(remainder theorem^영어)에 따르면, $f(x)$ 를 $x-a$ 로 나눈 나머지는 $f(a)$ 이다.^[9]^[10]

특히, 만약 $S$ 가 가환환일 경우, 임의의 $a\in S$ 에 대하여 나머지 정리가 성립한다.

환 $R$ 에서 계수를 취하는 두 다항식 $f,g\in R[x]$ 가 주어졌고, $\deg f\ge 0$ , $\deg g\ge 1$ 이며, $g(x)$ 의 최고차항의 계수가 $R$ 의 가역원이라고 할 때, 다음 두 조건을 만족시키는 다항식 $q_0,\dots q_{\lfloor\deg f/{\deg g}\rfloor}\in R[x]$ 가 유일하게 존재한다.

$f(x)=q_0(x)+g(x)q_1(x)+\cdots+g(x)^{\lfloor\deg f/{\deg g}\rfloor}q_{\lfloor\deg f/{\deg g}\rfloor}(x)$
$\deg q_i<\deg g\qquad(0\le i\le\lfloor\deg f/{\deg g}\rfloor)$

마찬가지로, 다음 두 조건을 만족시키는 다항식

\tilde q_0,\dots,\tilde q_{\lfloor\deg f/{\deg g}\rfloor}\in R[x]

가 유일하게 존재한다.

$f(x)=\tilde q_0(x)+\tilde q_1(x)g(x)+\cdots+\tilde q_{\lfloor\deg f/{\deg g}\rfloor}(x)g(x)^{\lfloor\deg f/{\deg g}\rfloor}$
$\deg\tilde q_i<\deg g\qquad(0\le i\le\lfloor\deg f/{\deg g}\rfloor)$

여기서

\lfloor\cdot\rfloor

는 바닥 함수이다. 특히,

g(x)=x

일 경우 이는 다항식

f(x)

의 통상적인 전개와 같다.

9. 1. 유클리드 호제법

나머지의 유일성에 주의해야 하는 경우가 있다. 예를 들어 ''a'' = 7, ''b'' = -3 이라면,

7 = (-2) × (-3) + 1
7 = (-3) × (-3) - 2

와 같이 두 가지 방식으로 나눗셈을 표현할 수 있다. 이때 |1| < |-3| 과 |-2| < |-3| 이 모두 성립한다.

나머지가 유일하게 나오도록 하는 방법은 여러 가지가 있을 수 있다. 예를 들어, "피제수가 음수일 때는, 피제수와 절댓값이 같은 자연수를 취하고, 그것을 나눗셈한 다음 다시 부호를 바꾼다"는 방법도 널리 사용된다. 계산기에서는 음수를 어떻게 표현하는지에 따라 결과가 달라질 수 있으므로, 프로그램에서 나머지 계산을 할 때는 주의해야 한다. 자연수에서는 이러한 문제가 발생하지 않는다.

9. 2. 합동식

두 정수 ''a'', ''b''에 대해 ''a'' - ''b''가 자연수 ''n''의 배수일 때, "''a''와 ''b''는 '''''n''을 법으로 합동이다'''"라고 하며, 이러한 정수의 관계를 합동 관계라고 한다. 합동 관계는 정수 전체의 집합 '''Z'''에서의 동치 관계이다.

''a''와 ''b''가 ''n''을 법으로 합동임을, "법(modulus)에 의해"라는 의미의 라틴어 "modulo"를 사용하여 다음 합동식으로 나타낸다.

: ''a'' ≡ ''b'' (modulo ''n'')

더 나아가, 단어를 "mod"로 줄여서, 다음 식으로 자주 나타낸다.

: ''a'' ≡ ''b'' (mod ''n'')

예를 들어 21 ≡ 11 (mod 5)이다.

합동식은 나머지에 주목하여 계산하는 경우에 편리하다. 실제로, 정수 ''a''에 대해, 0 ≤ ''m'' < ''n''이 되는 정수 ''m''으로 ''a'' ≡ ''m'' (mod ''n'')이 되는 것은 ''a''를 ''n''으로 나눈 나머지 그 자체이며, '''Z'''를 합동 관계로 분류한 동치류는, 나머지로 종종 동일시된다.

9. 3. 잉여 연산

이항 연산의 일종으로 잉여를 구하는 연산이 있다. 잉여 연산은 "mod"를 연산자로 사용하며, 다음과 같이 쓴다.

''m'' mod ''n''
mod(''m'', ''n'')

일부 프로그래밍 언어 (C 언어 등)에서는 "%"를 사용하여, ''m'' % ''n''으로 쓴다. ''n''이 양의 정수일 때, 잉여 연산의 결과는 0 이상 ''n'' 미만이다. 예를 들어, 7 mod 5 = 2이고, -7 mod 5 = 3이다.

나머지가 같음을 의미하는 등식

''a'' mod ''n'' = ''b'' mod ''n''

는, 합동식 ''a'' ≡ ''b'' (mod ''n'')으로 해석할 수도 있다.

잉여 연산은 일상생활 수준부터 RSA 암호 등의 컴퓨터 과학에 이르기까지 폭넓은 분야에서 활용된다.

9. 4. 전개

정수 n > 1을 하나 골라 고정할 때, 임의의 정수 m은 n의 거듭제곱 n^k (k ≥ 0)에 관한 나머지 수열 (m mod n^k)_k=0,1,2,...에 의해 유일하게 특정할 수 있다. 구체적으로, m에 대해 n^k+1을 법으로 하는 나머지에서 n^k을 법으로 하는 나머지를 뺀 것은 n^k으로 나누어 떨어지므로, 이것을 a_kn^k라고 하면, 0 ≤ a_k < n이며, 충분히 큰 k에 대해 모두 a_k = 0이 된다. 즉 적당한 자연수 M이 존재하여

:m = a₀ + a₁n + a₂n² + ⋯ + a_Mn^M

로 쓸 수 있으며, 게다가 이러한 표시는 유일하다. 이것을 정수 m의 n을 법으로 하는 전개, 또는 n-'''진 전개'''라고 부르며, 처음에 고정한 n을 전개의 기수라고 부른다. 이 전개는 자리값 표기법 등의 표기법의 원리적인 근거가 된다.

충분히 큰 k에 대해 모두 a_k = 0이 된다는 제한은, 기수가 소수 p일 때 p-진 거리에 관한 수렴의 개념을 사용하여 제거할 수 있으며, p-진 정수의 p-진 전개를 제공한다. 또한, 절댓값이 이끄는 거리를 넣고, 기수 n의 음의 거듭제곱도 동시에 고려하면 유리수나 실수의 n-진 전개(소수 전개)를 생각할 수 있다.

10. 유클리드 정역

원래 정수로 제한되었던 유클리드 나눗셈과 나눗셈 정리는 일변수 다항식에 대해 체와 유클리드 정역으로 일반화될 수 있다. 일변수 다항식의 경우, $0\le r<|b|$의 부등식은 $r = 0$ 또는 $\deg r < \deg b$로 대체된다. 여기서 $\deg$는 다항식 차수를 나타낸다.^[1]

유클리드 정역으로 일반화할 때, 이 부등식은 $r = 0$ 또는 $f(r) < f(b)$와 같이 표현된다. 여기서 $f$는 정역에서 자연수로의 특정 함수를 나타내며, "유클리드 함수"라고 불린다.^[1]

정수 전체가 이루는 환 '''Z''', 체 ''K'' 위의 일변수 다항식환 ''K''[''x'']나 가우스 정수환 '''Z'''[√−1] 등에서 나눗셈 정리가 성립한다.^[1]

10. 1. 정의

정수환

\mathbb Z

또는 체

K

위의 다항식환

K[x]

와 같이, 나머지 있는 나눗셈을 할 수 있고 정역을 이루는 환을 유클리드 정역이라고 한다. 구체적으로, 유클리드 정역은 다음을 만족시키는 함수

\operatorname N\colon R\setminus\{0\}\to\mathbb N

가 존재하는 정역

R

이다.

임의의 $a,b\in R$ ( $b\ne 0$ )에 대하여, $a=bq+r$ 이며, $r=0$ 이거나 $\operatorname N(r)<\operatorname N(b)$ 인 $q,r\in R$ 이 존재한다.

이 경우

q,r

는 정수환이나 다항식환에서와 달리 유일하지 않을 수 있다.

유클리드 정역으로 일반화할 때, 부등식은 다음과 같다.

:

r = 0

또는

f(r) < f(b)

여기서

f

는 정역에서 자연수로의 특정 함수를 나타내며, "유클리드 함수"라고 불린다.

정수 전체가 이루는 환 '''Z''', 체 ''K'' 위의 일변수 다항식환 ''K''[''x'']나 가우스 정수환 '''Z'''[√−1] 등에서 다음의 '''나눗셈 정리'''가 성립한다.

: 정역 ''R''에서, 어떤 정렬 집합 ''W''와 사상 ''N'': ''R'' → ''W''가 존재하여 다음의 성질을 만족한다.

:# ''W''의 최소원 ''m''에 대해, ''N''(''a'') = ''m'' ⇔ ''a'' = 0.

:# ''a'', ''b'' ∈ ''R'', ''b'' ≠ 0이면 ''a'' = ''qb'' + ''r''이며, ''N''(''r'') < ''N''(''b'')를 만족하는 ''q'', ''r'' ∈ ''R''가 존재한다.

예를 들어, 정수환 '''Z'''의 경우, ''W'' = '''N''' (0을 포함하는 자연수 전체의 집합), ''N''(''a'') = |''a''| (절댓값)로 두면 유클리드 정역의 조건을 만족한다. 이러한 성질을 갖는 정역 ''R''을 일반적으로 유클리드 정역이라고 한다. 나머지는 유클리드 정역에서 정의되는 개념이다.

10. 2. 예시

정수환 $\mathbb Z$은 절댓값 함수 $n\mapsto|n|$에 대하여 유클리드 정역을 이룬다. 체 $K$ 위의 다항식환 $K[x]$는 차수 함수 $f\mapsto \deg f$에 대하여 유클리드 정역을 이룬다.^[1]

유클리드 나눗셈과 나눗셈 정리는 일변수 다항식에 대해 체와 유클리드 정역으로 일반화될 수 있는데, 일변수 다항식의 경우 $0\le r<|b|$ 대신 $r = 0$ 또는 $\deg r < \deg b$가 된다. ($\deg$는 다항식 차수)^[1]

정수 전체가 이루는 환 '''Z''', 체 ''K'' 위의 일변수 다항식환 ''K''[''x'']나 가우스 정수환 '''Z'''[√−1] 등에서 나눗셈 정리가 성립한다.^[1]

10. 2. 1. 가우스 정수환

허수 이차 수체

\mathbb Q(i)

의 대수적 정수환

:

\mathbb Z[i]=\{a+bi\colon a,b\in\mathbb Z\}

를 가우스 정수환이라고 한다.

\mathbb Q(i)

위의 체 노름은

:

\operatorname N(a+bi)=a^2+b^2\qquad(a,b\in\mathbb Z)

이며, 가우스 정수환은 체 노름에 대하여 유클리드 정역을 이룬다.

임의의

a+bi,c+di\in\mathbb Z[i]

(

a,b,c,d\in\mathbb Z

,

c+di\ne 0

)에 대하여,

:

\frac{a+bi}{c+di}=e+fi

:

e,f\in\mathbb Q

라고 하자. 이제,

:

|e-p|\le\frac 12

:

|f-q|\le\frac 12

인

p,q\in\mathbb Z

를 취하고

:

r+si=(c+di)((e-p)+(f-q)i)=(a+bi)-(c+di)(p+qi)\in\mathbb Z[i]

라고 하자. 그렇다면,

:

a+bi=(c+di)(p+qi)+(r+si)

:

\operatorname N(r+si)=\operatorname N(c+di)\operatorname N((e-p)+(f-q)i)\le\frac 12\operatorname N(c+di)<\operatorname N(c+di)

이다. 이에 따라

\mathbb Z[i]

는 체 노름

\operatorname N

에 대하여 유클리드 정역을 이룬다.

가우스 정수환의 원소는 데카르트 좌표 평면 위의 격자점, 또는 원점에서 격자점을 향하는 벡터와 일대일 대응하며, 체 노름은 원점과의 거리의 제곱과 같다.

c+di

의

i

배

i(c+di)

에 대응하는 벡터는

c+di

에 대응하는 벡터와 직교한다. 따라서,

c+di

의 배수는

c+di

와

i(c+di)

의 정수 계수 선형 결합이므로,

c+di

와

i(c+di)

를 기저로 하는 새로운 데카르트 좌표계의 격자점에 대응한다. 주어진

a+bi

에 대하여, 새로운 격자점들 가운데

a+bi

와 가장 가까운 하나를

(c+di)(p+qi)

라고 하자. 그렇다면

p+qi

를

a+bi

에서

c+di

로 나눈 몫으로 취할 수 있다. 이 경우 나머지

r+si

는

(c+di)(p+qi)

에서

a+bi

를 향하는 벡터와 같다.

10. 2. 2. −3에 대한 이차 수체의 대수적 정수환

허수 이차 수체 $\mathbb Q(\sqrt{-3})$의 대수적 정수환은 다음과 같다.

:$\mathbb Z[\sqrt{-3}]=\left\{\frac{a+b\sqrt{-3}}2\colon a,b\in\mathbb Z,\;a\equiv b\pmod 2\right\}$

이는 체 노름

:$\operatorname N(a+b\sqrt{-3})=a^2+3b^2\qquad(a,b\in\mathbb Q)$

에 대하여 유클리드 정역을 이룬다.

11. 다변수 다항식

체 $K$에서 계수를 취하는 다변수 다항식환 $K[x_1,\dots,x_n]$은 여러 개의 변수를 가지는 다항식들로 이루어진 환이다. 다변수 다항식에 대한 나눗셈은 단항식 순서, 최고차항, 최고차 계수, 최고차 단항식 등의 개념을 사용하여 정의되며, 그뢰브너 기저를 통해 나머지의 유일성을 보장할 수 있다.

11. 1. 정의

체 $K$에서 계수를 취하는 다변수 다항식환 $K[x_1,\dots,x_n]$은 여러 개의 변수를 가지는 다항식들로 이루어진 환이다.

11. 1. 1. 단항식 순서

체

K

에서 계수를 취하는 다변수 다항식환

K[x_1,\dots,x_n]

위의 '''단항식 순서'''는 다음 세 조건을 만족시키는, 단항식의 집합 위의 전순서

\le

이다.

만약 $x_1^{i_1}\cdots x_n^{i_n} 이라면, (x_1^{i_1}\cdots x_n^{i_n})(x_1^{k_1}\cdots x_n^{k_n})<(x_1^{j_1}\cdots x_n^{j_n})(x_1^{k_1}\cdots x_n^{k_n}) 이다.$
항상 $1\le x_1^{i_1}\cdots x_n^{i_n}$ 이다.
$\le$ 는 정렬 전순서이다.

두 번째와 세 번째 조건은 하나만 취하여도 좋다. 첫 번째와 두 번째 조건은 세 번째 조건을 함의하며, 반대로 첫 번째와 세 번째 조건도 두 번째 조건을 함의하기 때문이다. 정의에 따라, 만약

x_1^{i_1}\cdots x_n^{i_n}\mid x_1^{j_1}\cdots x_n^{j_n}

이라면,

x_1^{i_1}\cdots x_n^{i_n}\le x_1^{j_1}\cdots x_n^{j_n}

이다.

체

K

에서 계수를 취하는 다변수 다항식환

K[x_1,\dots,x_n]

위의 단항식 순서

\le

가 주어졌다고 하자. 그렇다면, 임의의 다변수 다항식

f\in K[x_1,\dots,x_n]

은 그 (0이 아닌) 항들을

\le

에 대하여 큰 항부터 작은 항까지의 순서대로 정렬하여 다음과 같은 꼴로 나타낼 수 있다.

:

f(x_1,\dots,x_n)=a_{m_1,\dots,m_n}x_1^{m_1}\cdots x_n^{m_n}+\cdots

이 경우, 단항식 순서

\le

에 대한

f

의 '''최고차항''', '''최고차 계수''', '''최고차 단항식'''은 각각 다음과 같다.

:

\operatorname{lt}f=a_{m_1,\dots,m_n}x_1^{m_1}\cdots x_n^{m_n}

:

\operatorname{lc}f=a_{m_1,\dots,m_n}

:

\operatorname{lm}f=x_1^{m_1}\cdots x_n^{m_n}

(다항식 0의 최고차항, 최고차 계수, 최고차 단항식은 보통 모두 0으로 정의하며, 항상

\operatorname{lm}0\le\operatorname{lm}f

이라고 생각한다.)

11. 1. 2. 다변수 나눗셈

체

K

에서 계수를 취하는 다변수 다항식

f,g_1,\dots,g_k\in K[x_1,\dots,x_n]

및 단항식 순서

\le

가 주어졌고,

g_1,\dots,g_k\ne 0

이라고 하자. 그렇다면, 다음을 만족시키는 다변수 다항식

q_1,\dots,q_k,r\in K[x_1,\dots,x_n]

이 존재한다.

$f=g_1q_1+\cdots+g_kq_k+r$
$\operatorname{lm}g_iq_i\le\operatorname{lm}f\qquad(1\le i\le k)$
$\operatorname{lm}r\le\operatorname{lm}f$
$r$ 에 등장하는 모든 (0이 아닌 계수의) 단항식은 $\operatorname{lm}g_1,\dots,\operatorname{lm}g_k$ 의 배수가 아니다.

이 경우 몫과 나머지

q_1,\dots,q_k,r

는 유일할 필요가 없다. 만약

\{g_1,\dots,g_k\}

가

(g_1,\dots,g_k)

의 그뢰브너 기저를 이룰 경우, 나머지

r

는 항상 유일하며, 임의의

f\in K[x_1,\dots,x_n]

에 대하여, 다음 두 조건이 서로 동치이다.

$f\in(g_1,\dots,g_k)$
$f$ 를 $g_1,\dots,g_k$ 로 나눈 나머지는 0이다.

11. 1. 3. 그뢰브너 기저

체

K

에서 계수를 취하는 다변수 다항식환

K[x_1,\dots,x_n]

의 아이디얼

\mathfrak a\subseteq K[x_1,\dots,x_n]

및 단항식 순서

\le

가 주어졌다고 하자. 유한 집합

\{g_1,\dots,g_k\}\subseteq\mathfrak a\setminus\{0\}

에 대하여, 다음 조건들이 서로 동치이며, 이를 만족시키는

\{g_1,\dots,g_k\}

를

\mathfrak a

의 '''그뢰브너 기저'''라고 한다.

$(\operatorname{lm}\mathfrak a)=(\operatorname{lm}g_1,\dots,\operatorname{lm}g_k)$
임의의 $f\in\mathfrak a$ 에 대하여, $\operatorname{lm}g_i\mid\operatorname{lm}f$ 인 $1\le i\le k$ 가 존재한다.
임의의 $f\in\mathfrak a$ 에 대하여, $f$ 를 $g_1,\dots,g_k$ 로 나눈 모든 나머지는 0이다.
임의의 $f\in\mathfrak a$ 에 대하여, $f$ 를 $g_1,\dots,g_k$ 로 나눈 나머지 가운데 적어도 하나는 0이다.
(부흐베르거 알고리즘) $\mathfrak a=(g_1,\dots,g_k)$ 이며, 임의의 $1\le i 에 대하여, \operatorname{lcm}\{\operatorname{lm}g_i,\operatorname{lm}g_j\}(g_i/\operatorname{lt}g_i-g_j/\operatorname{lt}g_j) 를 g_1,\dots,g_k 로 나눈 모든 나머지는 0이다.$
(부흐베르거 알고리즘) $\mathfrak a=(g_1,\dots,g_k)$ 이며, 임의의 $1\le i 에 대하여, \operatorname{lcm}\{\operatorname{lm}g_i,\operatorname{lm}g_j\}(g_i/\operatorname{lt}g_i-g_j/\operatorname{lt}g_j) 를 g_1,\dots,g_k 로 나눈 나머지 가운데 적어도 하나는 0이다.$

여기서, 임의의 다항식 집합

S\subseteq K[x_1,\dots,x_n]

에 대하여,

(S)

는

S

로 생성된

K[x_1,\dots,x_n]

의 아이디얼이다.

S=\{s_1,\dots,s_

\}가 유한 집합일 경우

(S)

는

(s_1,\dots,s_

)로 표기할 수 있다. 또한,

:

\operatorname{lm}S=\{\operatorname{lm}s\colon s\in S\}

이다.

\operatorname{lcm}

은 최소 공배수를 뜻한다.

아이디얼

\mathfrak a\subseteq K[x_1,\dots,x_n]

의 그뢰브너 기저는 항상 존재한다. 모든 (무한 집합일 수 있는) 그뢰브너 기저는 유한 부분 그뢰브너 기저를 가지므로, 유한하지 않은 크기의 그뢰브너 기저는 다룰 필요가 없다.

11. 1. 4. 부흐베르거 알고리즘

체

K

에서 계수를 취하는 유한 개의 다변수 다항식

\{g_1,\dots,g_k\}\subseteq K[x_1,\dots,x_n]\setminus\{0\}

으로 생성된 아이디얼

(g_1,\dots,g_k)

의 그뢰브너 기저는 다음과 같은 과정을 통해 찾을 수 있으며, 이를 '''부흐베르거 알고리즘'''(Buchberger’s algorithm^영어)이라고 한다.

#

G=\{g_1,\dots,g_k\}

에서 시작한다.

# 각

1\le i 에 대하여, \operatorname{lcm}\{\operatorname{lm}g_i,\operatorname{lm}g_j\}(g_i/\operatorname{lt}g_i-g_j/\operatorname{lt}g_j) 를 g_1,\dots,g_

로 나눈 나머지

r_{ij}

를 구하되, 0이 아닌 나머지

r_{ij}\ne 0

을 발견했거나, 모든

1\le i 에 대하여 구했다면 멈춘다.

# 만약 0이 아닌 나머지

r_{i_0j_0}\ne 0

을 발견했다면,

g_{|G|+1}=r_{i_0j_0}

을

G

의 새로운 원소로 추가하여 2번째 단계를 반복한다. 만약 임의의

1\le i 에 대하여 r_{ij}=0 이라면, G 는 (g_1,\dots,g_k) 의 그뢰브너 기저 이다.

참조

_[1] 웹사이트 Division and Euclidean algorithms http://www-groups.mc[...] 2019-11-15
_[2] 웹사이트 What is modular arithmetic? https://www.khanacad[...] 2019-11-15
_[3] 웹사이트 Fun With Modular Arithmetic – BetterExplained https://betterexplai[...] 2019-11-15
_[4] 서적 Elementary Number Theory McGraw-Hill
_[5] 서적 Modern Algebra : an Introduction http://www.wiley.com[...] Wiley
_[6] 간행물 Obtaining More Karatsuba-Like Formulae over the Binary Field
_[7] 문서
_[8] 문서
_[9] 서적
_[10] 서적
_[11] 서적

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com