유클리드 나눗셈

산술적으로 유클리드 나눗셈은 정수 몫과 자연수 나머지를 나눗셈의 절대값보다 엄격하게 작은 방법으로 한 정수(배당금)를 다른 정수(나 나누는 과정입니다.기본적인 속성은 어떤 조건에서는 몫과 나머지가 존재하고 고유하다는 것입니다.이러한 독특함 때문에 유클리드 분할은 종종 계산 방법을 언급하지 않고, 몫과 나머지를 명시적으로 계산하지 않고 고려됩니다.계산 방법은 정수 분할 알고리즘이라고 불리는데, 가장 잘 알려진 것은 긴 분할입니다.

유클리드 분할과 이를 계산하는 알고리즘은 두 ^[1]정수의 최대 공약수를 찾는 유클리드 알고리즘과 나머지만 ^[2]고려하는 모듈러 산술과 같이 정수와 관련된 많은 질문에 기본입니다.나머지만을 계산하는 연산을 모듈로 ^[3]연산이라고 하며, 수학과 컴퓨터 과학에서 자주 사용됩니다.

나눗셈 정리

유클리드 나눗셈은 다음 결과에 기초하며, 유클리드 나눗셈 보조정리라고 불리기도 합니다.

두 개의 정수 a와 b가 주어졌을 때, b ≥ 0이면 다음과 같은 고유한 정수 q와 r이 존재합니다.

a = bq + r

그리고.

0 ≤ r < b,

여기서 b는 ^[4]b의 절대값을 의미합니다.

위의 정리에서, 4개의 정수는 각각 고유한 이름을 갖습니다: a는 배당, b는 나눗셈, q는 몫, r은 나머지라고 불립니다.

배당과 나눗셈에서 몫과 나머지를 계산하는 것을 나눗셈, 또는 애매모호한 경우 유클리드 나눗셈이라고 합니다.이 정리는 종종 분할 알고리즘이라고 불리는데(이는 알고리즘이 아니라 정리이기는 하지만), 아래와 같은 증명은 q와 r을 계산하기 위한 간단한 분할 알고리즘을 제공하기 때문입니다(자세한 내용은 증명 부분을 참조하십시오).

나눗셈은 b = 0인 경우에는 정의되지 않습니다. 0으로 나눗셈을 참조하십시오.

나머지와 모듈로 작업의 경우 0 ≤ r < b 이외의 규칙이 있습니다. 나머지에 대한 기타 간격을 참조하십시오.

역사

이 섹션은 검증을 위해 추가적인 인용이 필요합니다. 이 섹션의 신뢰할 수 있는 자료에 인용문을 추가하여 이 기사를 개선하는 데 도움을 주시기 바랍니다. 출처가 밝혀지지 않은 자료에 이의를 제기하여 제거할 수 있습니다.출처 찾기: "유클리드 사단" – 뉴스·신문·도서·학자·JSTOR (2016년 9월) (이 템플릿 메시지를 제거하는 방법 및 시기 알아보기)

'유클리드 나눗셈'은 유클리드의 이름을 딴 것이지만, 그는 존재와 유일성 정리를 몰랐고, 그가 알고 있는 계산법은 ^{[citation needed]}뺄셈을 반복한 나눗셈뿐이었던 것으로 보입니다.

피보나치에 의해 13세기에 유럽에 도입된 힌두 아라비아 수 체계가 발견되기 전에, 분열은 극도로 어려웠고, 최고의 수학자들만이 그것을 할 수 있었습니다.현재, 긴 나눗셈을 포함한 대부분의 나눗셈 알고리즘은 이 표기법 또는 이진수와 같은 그 변형을 기반으로 합니다.주목할 만한 예외는 뉴턴-라프슨 분할로, 어떤 수 체계와도 독립적입니다.

"유클리드 분열"이라는 용어는 20세기에 "유클리드 고리의 분열"의 축약어로 도입되었습니다.수학자들은 이 구분을 다른 종류의 ^{[citation needed]}수 구분과 구별하기 위해 빠르게 채택했습니다.

직관적인

파이에 9조각이 있다고 가정하고 4명이 골고루 나누어 먹는다고 가정해보세요.유클리드 나눗셈을 사용하면 9를 4로 나눈 것은 2이고 나머지는 1입니다.다시 말해, 한 사람당 2조각의 파이를 받고, 한 조각이 남습니다.

이것은 나눗셈의 역수인 곱셈을 사용하여 확인할 수 있습니다. 만약 4명의 사람들이 각각 2개의 조각을 받았다면, 4×2 = 8개의 조각을 나누어 주었습니다.남은 1조각을 더하면 결과는 9조각이 됩니다.요약하면 9 = 4 × 2 + 1.

일반적으로 슬라이스 수를 ${\displaystyle$ a$}$로 표시하고 사람$$수를 b {\$displaystyle$b}로 $표시$하면 사람들 사이에서 파이를 균등하게 나누어 각 사람이$q$ {\$displaystyle$ q$$}개의 슬라이스(계수)를 $받도록{\displaystyle }$ 할 수 있으며 일부 수 r< b {\$displaystyle$r<$}$는 나머지(나머지)가 됩니다.이 경우 $방정식$ a = ${\displaystyle b}$q + ${\displaystyle r}${\$displaystyle$ a = $bq + r$}이(가) 성립합니다.

4명이 아닌 3명이 9조각을 나누면 각각 3조각을 받고 남은 조각이 하나도 남지 않게 되는데, 이는 나머지가 0이므로 3명이 9를 균등하게 나누거나 3명이 9를 나눈다는 결론이 됩니다.

유클리드 분할은 동일한 공식을 사용하여 음의 배당(또는 음의 나눗셈)으로 확장될 수도 있습니다. 예를 들어 -9 = 4 × (-3) + 3으로 나눈 -9는 -3이고 나머지는 3입니다.

예

• 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입니다.

증명

다음의 나눗셈 정리의 증명은 음이 아닌 정수의 감소 순서가 결국 멈춘다는 사실에 의존합니다.q ${\displaystyle q}$과 $r{\displaystyle }$ ${\displaystyle$ r$\}$의 $존재$를 위한 것과 유일성을 위한 것의 두 부분으로 나누어집니다. 다른 증명들은 잘 정렬된 원리(즉, 비어 있지 않은 음이 아닌 정수의 모든 집합이 가장 작은 원소를 가지고 있다는 주장)를 사용하여 추론을 더 단순화합니다.그러나 나눗셈을 해결하기 위한 알고리즘을 직접 제공하지 못하는 단점이 있습니다(^[5]자세한 내용은 ① 유효성 참조).

존재

먼저 b < 0인 경우를 생각해 보자. b' = –b' = –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이면 나눗셈이 완료되었으므로 ≥ b를 가정합니다.그런 다음 q = q + 1과 r = r – b를 정의하면 a = bq + r이 0이고 ≤ r < r입니다. r보다 작은 음이 아닌 정수는 오직 r개뿐이므로 이 과정을 최대 r번만 반복하면 최종 몫과 나머지에 도달할 수 있습니다.즉, a = bq + r, 0 ≤ r < b인 자연수 k ≤ r이 존재합니다.

이것은 존재를 증명하고 또한 몫과 나머지를 계산하기 위한 간단한 분할 알고리즘을 제공합니다.그러나 이 알고리즘은 단계 수가 a/b 순서이기 때문에 효율적이지 않습니다.

유니크함

유클리드 나눗셈 정리에서 동일한 조건을 만족하는 다른 정수 쌍이 있을 수 없다는 의미에서 a = bq + r이 되는 정수 r과 q의 쌍.즉, a를 b로 나눈 다른 분할이 0 ≤ r' < b로 a = bq' + r'라고 하면 다음을 가져야 합니다.

q' = q 및 r' = r.

이 진술을 증명하기 위해, 우리는 먼저 다음과 같은 가정으로부터 시작합니다.

0 ≤ r < b

0 ≤ r' < b

a = bq + r

a = bq' + r'

두 방정식을 빼면 산출량이 늘어납니다.

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

sob는 r' – r. As의 약수입니다.

r' – r < b

위의 불평등에 의해서, 사람은

r' – r = 0,

그리고.

b(q – q') = 0.

b ≥ 0이므로, r = r', q = q'를 얻으며, 이는 유클리드 분할 정리의 유일성 부분을 증명합니다.

유효성

일반적으로, 존재 증명은 기존의 몫과 나머지를 계산하는 알고리즘을 제공하지 않지만, 위 증명은 몫의 크기만큼 많은 단계를 필요로 하는 매우 효율적인 알고리즘이 아님에도 불구하고 즉시 알고리즘을 제공합니다.이것은 곱셈을 포함하지 않고 정수의 덧셈, 뺄셈, 비교만을 사용하고 십진법 표기와 같은 정수의 특정한 표현을 사용한다는 사실과 관련이 있습니다.

십진법 표기법 측면에서, 긴 나눗셈은 유클리드 나눗셈을 푸는 데 훨씬 더 효율적인 알고리즘을 제공합니다.이진법과 16진법 표기법으로 일반화된 것은 컴퓨터 구현을 위한 추가적인 유연성과 가능성을 제공합니다.그러나 대규모 입력의 경우 뉴턴-라프슨과 같이 분할을 곱셈으로 줄이는 알고리즘이 선호되는데, 이는 사용되는 곱셈 알고리즘과는 별개로 결과를 확인하는 데 필요한 곱셈 시간에 비례하는 시간만 필요하기 때문입니다.분할 알고리즘 #고속 분할 방법 참조).

변형

유클리드 분할은 아래에 나열된 몇 가지 변형을 인정합니다.

나머지 구간의 기타 구간

d 나눗셈이 있는 유클리드 분할에서, 나머지는 길이 d의 구간 [0, d]에 속하도록 되어 있습니다. 같은 길이의 다른 구간이 사용될 수 있습니다.더 정확하게 말하면 $정수$m {\$displaystyle$m},$${\$displaystyle$a},$$d {\$displaystyle$ d$}($m$>0$가 주어졌을 때, d < + {\$displaystyle$q} $및$ r ${\$$displaystyle$ d$\leq$r<$m+d}$인 고유한 $정수$q {\$displaystyle$q}이 존재하며, $이$는 a = ${\displaystyle m}$q + ${\displaystyle r}${\$displaystyle$ a = $mq + r$이 됩니다.

$특히$ d = - ⌊ ${\displaystyle m}$ ${\displaystyle \frac{2}{}}$ ⌋ {\$displaystyle$ d=-\$left\l$ floor {\$frac {m}{2}}\right\rfloor }$이면- ⌊ ⌋ ≤ <$m$ - ⌊ ⌋{\$displaystyle -\left\loor${\$frac {m}{2}}\right\rfloor }.$ 이 구분을 중심 구분이라고 하며,그리고 $나머지{\displaystyle }$ r ${\displaystyle$ r$}$을(를) 중심 나머지 또는 최소 절대 나머지라고 합니다.

이 방법은 실수의 근사치를 나타내는 데 사용됩니다.유클리드 분할은 잘라내기를 정의하고 중심 분할은 반올림을 정의합니다.

몽고메리 디비전

$정수$ a가 ${\displaystyle$a$\},$ $m$ ${\displaystyle$ m$}$이고 R이${\displaystyle$ m$>0}$이고 ${\displaystyle gcd(R,m}$) = ${\displaystyle 1,}$ ${\$$displaystyle$ $\gcd(R,$m) =$$1,}이고${\displaystyle {}^{}}$R -$$1$${\$displaystyle$R$^{-1}$인 모듈형 곱셈 역(${\displaystyle {,}^{}}$ - ${\displaystyle {}^{}\mathrm{R}}$ - 1<$m$ {\$displaystyle 0<R^{-1}<$m})이면$$R - 1 {\$displaystyle R$^{-1$}R-$$1}$은(는) m ${\displaystyle$m})의 배수이며, 0 < {\$displaystyle$q} $및$ r ${\displaystyle$ r$}$인 $정수$ q$${\$displaystyle$ q$}$이(가$)$ 존재하며, $이$는 a $=$ ${\displaystyle \mathrm{mq}}$ +${\displaystyle {}^{}}$ - ${\displaystyle 1{}^{}}$$⋅$ ${\displaystyle$ a $=$ $mq$+$R^{-1}\cdot$ r$\}$입니다.이 결과는 헨젤의 홀수분할(1900)^[6]을 일반화한 것입니다.

${\displaystyle$ r$}$ $값$은 몽고메리 축소에 정의된 N-잔차입니다.

유클리드 도메인에서

유클리드 영역(유클리드 ^[7]고리라고도 함)은 유클리드 분할의 다음과 같은 일반화를 지원하는 통합 영역으로 정의됩니다.

유클리드 함수 d(유클리드 평가 또는 정도 함수라고도 함)를 갖춘 유클리드 영역 R에 원소 a와 0이 아닌 원소 b가 주어지면, a = bq + r과 r = 0 또는 d(r) < d(b) 중 하나가 되는 q와 r이 존재합니다.

q와 r의 고유성은 필요하지 않습니다.^[1]이 값은 단변량 다항식의 경우와 정수의 경우 예외적인 경우에만 발생하며, 조건자 ≥ 0이 추가된 경우에만 발생합니다.

유클리드 도메인의 예로는 필드, 필드 위의 하나의 변수에 있는 다항식 링, 가우스 정수 등이 있습니다.다항식의 유클리드 분할은 구체적인 발전의 대상이 되어 왔습니다.

참고 항목

• 유클리드 보조정리
• 유클리드 알고리즘

메모들

참고문헌

• 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