Euclidean division

Original article: w:Euclidean division

This article is about division of integers. For polynomials, see Euclidean division of polynomials. For other domains, see Euclidean domain.

17 is divided into 3 groups of 5, with 2 as leftover. Here, the dividend is 17, the divisor is 5, the quotient is 3, and the remainder is 2 (which is strictly smaller than the divisor 5), or more symbolically, 17 = (5 × 3) + 2.

산술(arithmetic)에서, 유클리드 나눗셈(Euclidean division) – 또는 나머지를 갖는 나눗셈 – 은 한 정수 (피제수) 또 다른 정수 (제수)로 나누는 나눗셈(division)의 과정으로, 몫(quotient)과 제수보다 작은 나머지(remainder)를 생성합니다. 기본 속성은 일부 조건 아래에서 몫과 나머지가 존재하고 고유하다는 것입니다. 이 고유성 때문에, 유클리드 나눗셈(Euclidean division)은 종종 임의의 계산 방법에 대한 언급하지 않고 몫과 나머지를 명시적으로 계산하지 않고, 고려됩니다. 계산의 방법은 정수 나눗셈 알고리듬(integer division algorithms)이라고 불리며, 그것 중 가장 잘 알려진 것은 긴 나눗셈(long division)입니다.

유클리드 나눗셈, 및 그것을 계산하기 위한 알고리듬은 두 정수의 최대 공통 약수(greatest common divisor)를 찾는 유클리드 알고리듬(Euclidean algorithm), 및 오직 나머지를 고려하는 모듈러 산술(modular arithmetic)과 같은, 정수 관련 많은 질문에 대해 기본입니다. 오직 나머지를 계산하는 것으로 구성되는 연산은 모듈로 연산(modulo operation)이라고 불리고, 종종 수학과 컴퓨터 과학에서 모두 사용됩니다.

The pie has 9 slices, so each of the 4 people receive 2 slices and 1 is left over.

Division theorem

유클리드 나눗셈은 다음 결과의 기초이며, 이것은 때때로 유클리드의 나눗셈 보조정리라고 불립니다.

두 정수 a와 b가 b ≠ 0와 함께 주어지면, 다음을 만족하는 고유한 정수 q와 r이 존재합니다:

a = bq + r

이때,

0 ≤ r < |b|,

여기서 |b|는 b의 절댓값(absolute value)을 나타냅니다.

위의 정리에서, 각각의 넷의 정수는 그 자신의 이름을 가집니다: a는 피제수(dividend), b는 제수(divisor), q는 몫(quotient), 및 r은 나머지(remainder)라고 불립니다.

피제수와 제수로부터 몫과 나머지의 계산은 나눗셈(division) 또는 – 모호한 경우에서 – 유클리드 나눗셈(Euclidean division)이라고 불립니다. 그 정리는 자주 나눗셈 알고리듬(division algorithm)으로 참조되는데 (비록 그것이 정리이고 알고리듬이 아니지만), 왜냐하면 아래에 주어진 것처럼 그것의 증명은 자체를 q와 r을 계산하는 단순히 나눗셈 알고리듬으로 보내기 때문입니다 (자세한 것에 대해 증명 섹션을 참조하십시오).

나눗셈은 b = 0인 경우에 정의되지 않습니다; 영에 의한 나눗셈(division by zero)을 참조하십시오.

나머지와 모듈로 연산(modulo operation)에 대해, 0 ≤ r < |b|가 아닌 관례가 있으며, § Other intervals for the remainder를 참조하십시오.

History

"유클리드 나눗셈"은 유클리드(Euclid)의 이름을 따서 지어졌지만, 그는 그 존재와 유일성 정리를 알지 못했고, 그가 알고 있는 유일한 계산 방법은 반복된 뺄셈에 의한 나눗셈뿐이었던 것으로 보입니다.

13세기에 피보나치(Fibonacci)에 의해 유럽에 소개되었던 힌두–아라비아 숫자 표시 시스템(Hindu–Arabic numeral system)의 발견 전에, 나눗셈은 극단적으로 어려웠고, 오직 최고의 수학자들이 그것을 하기 위한 능력이 있었습니다. 현재, 긴 나눗셈(long division)을 포함한 대부분의 나눗셈 알고리듬(division algorithm)은 이 표기법 또는 이진 숫자-표시(binary numeral)와 같은 변형을 기반으로 합니다. 주목할만한 예외는 임의의 숫자-표시 시스템(numeral system)과도 독립적인 뉴턴–랍선 나눗셈(Newton–Raphson division)입니다.

용어 "유클리드 나눗셈"은 20세기 동안 "유클리드 링(Euclidean ring)의 나눗셈"에 대한 줄임말로 도입되었습니다. 그것은 이 나눗셈(division)을 다른 종류의 숫자의 나눗셈과 구별하기 위해 수학자들에 의해 빠르게 채택되어 왔습니다.

Intuitive example

하나의 파이가 9개의 조각을 갖고 4명에게 균등하게 나누어져야 한다고 가정해 보십시오. 유클리드 나눗셈을 사용하여, 9를 4로 나누면 나머지 1을 갖는 2입니다. 다시 말해서, 각 사람은 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을 받고 조각은 남겨지지 않으며, 이것은 나머지가 영임을 의미하며, 3은 9를 균등하게 나눈다, 또는 3은 9를 나눈다(divides)는 결론으로 이어집니다.

유클리드 나눗셈은 역시 같은 공식을 사용하여 음의 피제수 (또는 음의 제수)로 확장될 수 있습니다; 예를 들어 −9 = 4 × (−3) + 3이며, 이것은 −9를 4로 나눈 값은 −3과 나머지는 3임을 의미합니다.

Examples

• 만약 a = 7이고 b = 3이면, q = 2이고 r = 1인데, 왜냐하면 7 = 3 × 2 + 1.
• 만약 a = 7이고 b = −3이면, q = −2이고 r = 1인데, 왜냐하면 7 = −3 × (−2) + 1.
• 만약 a = −7이고 b = 3이면, q = −3이고 r = 2인데, 왜냐하면 −7 = 3 × (−3) + 2.
• 만약 a = −7이고 b = −3이면, q = 3이고 r = 2인데, 왜냐하면 −7 = −3 × 3 + 2.

Proof

나눗셈 정리의 다음 증명은 비-음의 정수의 감소 수열이 결국 중지된다는 사실에 의존합니다. 그것은 두 부분으로 분리됩니다: 하나는 존재를 위한 것이고 다른 하나는 $q$와 $r$의 고유성을 위한 것입니다. 다른 증명은 바른-순서 원칙(well-ordering principle) (즉, 비-음의 정수(non-negative integers)의 모든 각 비-빈 집합(non-empty set)이 가장 작은 요소를 갖는다는 주장)을 사용하여 추론을 더 간단하게 만들지만, 나눗셈을 풀기 위한 알고리듬을 직접 제공하지 않는다는 단점이 있습니다 (자세한 내용에 대해 § Effectiveness를 참조하십시오).

Existence

먼저 경우 b < 0를 생각해 보십시오. b' = –b 및 q' = –q를 놓으면, 방정식 a = bq + r은 a = b'q' + r로 다시 쓸 수 있고 부등식 0 ≤ r < |b|은 0 ≤ r < |b′|으로 다시 쓸 수 있습니다. 이것은 경우 b < 0에 대한 존재를 경우 b > 0의 그것으로 줄입니다.

유사하게, 만약 a < 0이고 b > 0이면, a' = –a, q' = –q – 1, 및 r' = b – r을 놓으면, 방정식 a = bq + r은 a' = bq' + r′으로 다시 쓸 수 있고, 부등식 0 ≤ r < |b|은 0 ≤ r' < |b|으로 다시 쓸 수 있습니다. 따라서 존재의 증명은 경우 a ≥ 0이고 b > 0로 줄어듭니다 – 이것은 증명의 나머지에서 고려될 것입니다.

q₁ = 0 및 r₁ = a을 놓으면, 이것들은 a = bq₁ + r₁를 만족하는 비-음수입니다. 만약 r₁ < b이면 나눗셈이 완성되므로, r₁ ≥ b를 가정합니다. 그런-다음 q₂ = q₁ + 1 및 r₂ = r₁ – b을 정의하면, 우리는 a = bq₂ + r₂와 함께 0 ≤ r₂ < r₁를 가집니다. r₁보다 작은 비-음의 정수 r₁뿐이므로, 우리는 최종 몫과 나머지에 도달하기 위해 오직 이 과정을 많아야 r₁번 반복하는 것이 필요합니다. 즉, a = bq_k + r_k과 0 ≤ r_k < |b|을 만족하는 자연수 k ≤ r₁가 존재합니다.

이것은 존재를 증명하고 몫과 나머지를 계산하기 위한 간단한 나눗셈 알고리듬(division algorithm)을 제공합니다. 어쨌든, 이 알고리듬은 단계 수가 a/b 정도이므로 효율적이지 않습니다.

Uniqueness

a = bq + r를 만족하는 정수 r과 q의 쌍은, 유클리드 나눗셈 정리에서 같은 조건을 만족시키는 다른 정수 쌍이 있을 수 없다는 의미에서 고유합니다. 다시 말해서, 만약 우리가 b에 의한 a의 또 다른 나눗셈이 있다면, 말하자면 a = bq' + r'와 함께 0 ≤ r' < |b|이면, 우리는 다음임을 가져야 합니다:

q' = q and r' = r.

이 명제를 입증하기 위해, 우리는 먼저 다음임을 가정하여 시작합니다:

0 ≤ r < |b|

0 ≤ r' < |b|

a = bq + r

a = bq' + r'

두 방정식을 빼면 다음을 산출합니다:

b(q – q′) = r′ – r.

따라서 b는 r′ – r의 제수입니다. 위의 부등식에 의해 다음이기 때문에,

|r′ – r| < |b|

우리는 다음을 얻습니다:

r′ – r = 0,

및

b(q – q′) = 0.

b ≠ 0이므로, 우리는 r = r′과 q = q′임을 얻으며, 이것은 유클리드 나눗셈 정리의 고유성 부분을 입증합니다.

Effectiveness

일반적으로, 존재 증명은 기존 몫과 나머지를 계산하는 알고리듬을 제공하지 않지만, 비록 몫의 크기만큼 많은 단계를 필요로 하기 때문에 매우 효율적인 것은 아닐지라도, 위의 증명은 즉시 알고리듬을 제공합니다 (Division algorithm#Division by repeated subtraction를 참조하십시오). 이것은 곱셈을 포함하지 않고, 십진 표기법과 같은 임의의 정수의 특정 표현을 포함하지 않고, 오직 정수의 덧셈, 뺄셈, 및 비교를 사용한다는 사실과 관련이 있습니다.

십진 표기법의 관점에서, 긴 나눗셈(long division)은 유클리드 나눗셈을 풀기 위한 훨씬 더 효율적인 알고리듬을 제공합니다. 이진법(binary)과 십육진법(hexadecimal) 표기법으로의 일반화는 컴퓨터 구현을 위한 추가 유연성과 가능성을 제공합니다. 어쨌든, 큰 입력에 대해, 뉴턴–랍선(Newton–Raphson)과 같이 나눗셈을 곱셈으로 줄이는 알고리듬이 보통 선호되는데, 왜냐하면 그것들은 결과를 확인하는 데 필요한 곱셈 시간에 비례하는 시간만 필요하기 때문입니다–사용된 곱셈 알고리듬에 독립적입니다 (자세한 내용에 대해 Division algorithm#Fast division methods을 참조하십시오).

Variants

유클리드 나눗셈은 여러 변형을 허용하며, 그 중 일부는 아래에 나열되어 있습니다.

Other intervals for the remainder

See also: Modulo operation § Variants of the definition

d를 제수로 하는 유클리드 나눗셈에서, 나머지는 길이 |d|의 구간(interval) [0, d)에 속한다고 가정됩니다. 같은 길이의 임의의 다른 구간이 사용될 수 있습니다. 보다 정확하게, 정수 $m$, $a$, $d$와 함께 $m>0$이 주어지면, $a=mq+r$를 만족하는 고유한 정수 $q$와 $r$이 존재하고 함께 $d\leq r<m+d$입니다.

특히, 만약 $d=-\left\lfloor {\frac {m}{2}}\right\rfloor$이면 $-\left\lfloor {\frac {m}{2}}\right\rfloor \leq r<m-\left\lfloor {\frac {m}{2}}\right\rfloor$입니다. 이 나눗셈은 중심 나눗셈(centered division)이라고 불리고, 그것의 나머지 $r$은 중심 나눗셈(centered division) 또는 최소 절대 나머지라고 불립니다.

이것은 실수(real number)를 근사화하는 데 사용됩니다: 유클리드 나눗셈은 잘림(truncation)을 정의하고, 중심 나눗셈은 반올림(rounding)을 정의합니다.

Montgomery division

Main article: Montgomery modular multiplication

정수 $a$, $m$, 및 $R$과 함께 $m>0$와 $\gcd(R,m)=1$가 주어지면, $R^{-1}$을 $R$의 모듈러 곱셈 역(modular multiplicative inverse)으로 놓으면 (즉, $R^{-1}R-1$을 갖는 $0<R^{-1}<m$이 $m$의 배수임), $a=mq+R^{-1}\cdot r$을 만족하는 $0\leq r<m$을 갖는 고유한 정수 $q$와 $r$가 존재합니다. 이 결과는 헨젤의 홀수 나눗셈 (1900)을 일반화합니다.

값 $r$은 몽고메리 축소(Montgomery reduction)에서 정의된 N-잔여입니다.

In Euclidean domains

See also: Polynomial long division, Polynomial greatest common divisor § Euclidean division, and Polynomial greatest common divisor § Pseudo-remainder sequences

유클리드 도메인 (역시 유클리드 링으로 알려져 있음)은 다음과 같은 유클리드 나눗셈의 일반화를 지원하는 정수 도메인(integral domain)으로 정의됩니다:

유클리드 함수 d (역시 Euclidean valuation 또는 degree function라고 알려져 있음)를 구비된 유클리드 도메인 R에서 원소 a와 비-영 원소 b가 주어지면, a = bq + r와 r = 0 또는 d(r) < d(b) 중 하나를 만족하는 R에서 q와 r이 존재합니다.

q와 r의 고유성은 요구되지 않습니다. 그것은 오직 예외적인 경우, 전형적으로 일변수 다항식(univariate polynomial), 및 정수에 대해, 추가 조건 r ≥ 0이 추가되는 경우에서 발생합니다.

유클리드 도메인의 예제는 필드(field), 필드에 걸쳐 한 변수에서 다항식 링(polynomial ring), 및 가우스 정수(Gaussian integers)를 포함합니다. 다항식의 유클리드 나눗셈은 특정 개발의 대상이었습니다.

See also

• Euclid's lemma
• Euclidean algorithm

References

• Fraleigh, John B. (1993), A First Course in Abstract Algebra (5th ed.), Addison-Wesley, ISBN 978-0-201-53467-2
• Rotman, Joseph J. (2006), A First Course in Abstract Algebra with Applications (3rd ed.), Prentice-Hall, ISBN 978-0-13-186267-8