유클리드 알고리즘

Euclidean algorithm
두 개의 시작 길이 BA와 DC의 최대공약수(GCD)를 구하는 유클리드의 방법은 둘 다 공통 "단위" 길이의 배수라고 정의된다.DC의 길이가 짧은 것은 BA의 「측정」에 사용됩니다만, 나머지 EA가 DC보다 작기 때문에, 1회 뿐입니다.이때 EA는 짧은 DC를 측정(2회), 나머지 FC는 EA보다 짧습니다.다음으로 FC는 EA 길이를 3회 측정합니다.나머지가 없기 때문에 프로세스는 FC가 GCD가 되는 것으로 종료됩니다.오른쪽의 Nicomachus의 예에서는 49와 21의 GCD가 7(히스 1908:300에서 파생).

수학에서, 유클리드 [note 1]알고리즘 또는 유클리드 알고리즘은 두 정수(숫자)의 최대공약수(GCD)를 계산하는 효율적인 방법이다.이것은 고대 그리스 수학자 유클리드의 이름을 따서 지어졌는데, 그는 그의 원소 (기원전 300년경)에 그것을 처음 기술했다.이것은 알고리즘의 예이며, 잘 정의된 규칙에 따라 계산을 수행하는 단계별 절차이며 일반적으로 사용되는 가장 오래된 알고리즘 중 하나입니다.분수를 가장 간단한 형태로 줄이는 데 사용할 수 있으며, 다른 많은 숫자 이론 및 암호 계산의 일부입니다.

유클리드 알고리즘은 두 숫자의 최대공약수가 큰 숫자와 작은 숫자의 차이로 대체될 경우 변하지 않는다는 원리에 기초한다.예를 들어, 21은 252 및 105의 GCD(252 = 21 × 12, 105 = 21 × 5)이며, 같은 숫자 21도 105 및 252 - 105 = 147의 GCD이다.이 치환으로 인해 두 숫자 중 큰 숫자가 감소하므로 이 프로세스를 반복하면 두 숫자가 같아질 때까지 더 작은 숫자의 페어가 연속적으로 생성됩니다.이 경우 원래 두 숫자의 GCD가 됩니다.단계를 역전하거나 확장된 유클리드 알고리즘을 사용함으로써 GCD는 두 원본 숫자의 선형 조합으로 표현될 수 있다. 즉, 두 숫자의 합계에 각각 정수를 곱한 것이다(예를 들어 21 = 5 × 105 + (-2) × 252).GCD가 항상 이런 식으로 표현될 수 있다는 사실은 베주의 정체성으로 알려져 있다.

위에서 설명한 (그리고 유클리드에 의해) 유클리드 알고리즘의 버전은 주어진 숫자 중 하나가 다른 숫자보다 훨씬 클 때 GCD를 찾기 위해 많은 감산 단계를 밟을 수 있다.알고리즘의 보다 효율적인 버전에서는, 이러한 스텝을 단축해, 대신에 2개의 번호 중 큰 것을 2개의 번호 중 작은 것으로 나누었을 때에 나머지로 치환합니다(이 버전에서는, 알고리즘은 0 의 나머지에 이르면 정지합니다).이 개선으로 알고리즘은 작은 정수의 자리수(기본값 10)의 5배를 넘는 스텝을 필요로 하지 않습니다.이는 1844년 가브리엘 라메에 의해 증명되었으며 계산 복잡성 이론의 시작을 알립니다.알고리즘의 효율성을 개선하기 위한 추가적인 방법들이 20세기에 개발되었다.

유클리드 알고리즘은 많은 이론적이고 실용적인 응용 분야를 가지고 있다.분수를 가장 단순한 형태로 줄이고 모듈식 산술에서 나눗셈을 수행하는 데 사용됩니다.이 알고리즘을 사용한 연산은 인터넷 통신의 보안을 확보하기 위해 사용되는 암호 프로토콜의 일부를 형성하고, 대규모 복합 숫자를 인수하여 이러한 암호 시스템을 해독하는 방법을 형성합니다.유클리드 알고리즘은 디오판토스 방정식을 풀기 위해 사용될 수 있는데, 예를 들어 중국의 나머지 정리에 따라 여러 개의 합치를 만족시키는 수를 찾고 연속 분수를 구성하며, 실수에 대한 정확한 합리적 근사치를 찾기 위해 사용될 수 있다.마지막으로, 라그랑주의 4제곱 정리나 소인수 분해의 고유성 같은 수 이론의 이론들을 증명하기 위한 기본적인 도구로 사용될 수 있다.원래 알고리즘은 자연수와 기하학적 길이(실수)에 대해서만 설명되었지만, 알고리즘은 19세기에 가우스 정수와 한 변수의 다항식같은 다른 유형의 숫자로 일반화되었습니다.이것은 유클리드 도메인과 같은 현대 추상 대수적 개념으로 이어졌다.

배경: 최대 공약수

유클리드 알고리즘은 두 자연수 a와 b의 최대공약수(GCD)를 계산합니다.최대공약수 g는 ab를 모두 나머지를 남기지 않고 나누는 가장 큰 자연수이다.GCD의 동의어에는 최대공통인자(GCF), 최대공통인자(HCF), 최대공통인자(HCD), 최대공통인자(GCM)가 있습니다.최대공약수는 종종 gcd(a, b) 또는 더 간단히 말하면 (a,[1] b)로 쓰이지만, 후자의 표기법은 애매하지만, GCD와 밀접한 관련이 있는 정수환이상과 같은 개념에도 사용된다.

gcd(a, b) = 1이면 a와 b는 공칭(또는 비교적 소수)[2]이라고 한다.이 속성은 a 또는 b 자체[3]소수라는 을 의미하지는 않습니다.예를 들어, 6과 35는 둘 다 6 = 2 × 3과 35 = 5 × 7의 두 개의 소수 인자를 가지고 있기 때문에 소수가 아니다. 그럼에도 불구하고 6과 35는 공수이다.6과 35는 공통의 소인수가 없기 때문에 1 이외의 자연수는 둘 다 나누지 않습니다.

"Tall, slender rectangle divided into a grid of squares. The rectangle is two squares wide and five squares tall."
24x60 직사각형은 12x12 정사각형 타일 10장으로 덮여 있습니다.여기서 12는 24와 60의 GCD입니다.보다 일반적으로, a-b 직사각형은 c가 a와 b의 공통 약수인 경우에만 측면 길이 c의 정사각형 타일로 덮을 수 있다.

g = gcd(a, b)로 하자.a와 b는 모두 g의 배수이므로 a = mg, b = ng표기할 수 있으며, 이것이 참인 G > g는 더 이상 존재하지 않는다.모든 공통 인자는 g를 크게 만들기 위해 mn에서 인수분해할 수 있으므로 자연수 m과 n은 공수여야 합니다.따라서 a와 b를 나누는 다른 숫자 c도 g를 나누어야 합니다.ab최대공약수 g는 ab의 고유공약수이며 다른 공약수 [4]c로 나눌 수 있다.

GCD는 다음과 같이 시각화할 수 있습니다.[5]직사각형 영역 a bab를 모두 정확히 나누는 공통 제수 c를 고려합니다.직사각형의 변은 길이 c의 세그먼트(segment)로 분할할 수 있습니다.이 세그먼트는 직사각형을 길이 c의 정사각형 그리드로 분할합니다.최대공약수 g는 이것이 가능한 c의 최대값이다.예를 들어 24x60 직사각형 영역은 1x1 정사각형, 2x2 정사각형, 3x3 정사각형, 4x4 정사각형, 6x6 정사각형 또는 12x12 정사각형 그리드로 나눌 수 있습니다.따라서 12는 24와 60의 최대 공약수이다.24x60 직사각형 영역은 한 모서리를 따라 두 개의 정사각형(24/12 = 2)이 있고 다른 모서리를 따라 다섯 개의 정사각형(60/12 = 5)이 있는 12x12 정사각형의 그리드로 나눌 수 있습니다.

두 개의 숫자 a와 b의 GCD는 두 개의 숫자가 공유하는 소수 인자의 곱이다. 여기서 동일한 소수 인자를 여러 번 사용할 수 있지만, 이러한 인자의 곱이 a[6]b를 둘 다 나누는 한에만 해당된다.예를 들어, 1386은 2 × 3 × 3 × 7 × 11로 인수분해할 수 있고, 3213은 3 × 3 × 7로 인수분해할 수 있기 때문에, 1386과 3213의 최대 공약수는 63 = 3 × 3 × 7로, 공유 소수 인수의 곱이다.두 숫자에 공통 소인수가 없는 경우, 이들의 최대공약수는 1(여기서는 빈 제품의 인스턴스로 제공됨)입니다. 즉, 이들은 공수입니다.유클리드 알고리즘의 주요 장점은 소수 [7][8]인자를 계산할 필요 없이 GCD를 효율적으로 찾을 수 있다는 것이다. 정수의 인수분해는 계산상 매우 어려운 문제로 여겨지고 있으며, 널리 사용되는 많은 암호화 프로토콜의 보안은 그 [9]실현 불가능에 기초하고 있습니다.

GCD의 또 다른 정의는 고급 수학, 특히 고리 [10]이론에서 도움이 된다.0이 아닌 두 숫자 a와 b의 최대 공약수 g는 또한 가장 작은 양의 정수 선형 조합이다. 즉, ua + vb 형식의 가장 작은 양의 숫자이다. 여기u와 v는 정수이다.a와 b의 모든 정수 선형 조합의 집합은 실제로 g의 모든 배수 집합과 동일합니다(mg, 여기서 m은 정수입니다).현대 수학 언어에서, a와 b에 의해 생성된 이상g의해서만 생성된 이상이다.GCD의 일부 특성은 실제로 이 설명으로 보기 더 쉽다. 예를 들어, ab의 공통 약수가 GCD를 나눈다는 사실(ua + vb의 두 항을 나눈다).이 GCD 정의와 다른 정의의 동등성은 다음과 같다.

3개 이상의 숫자의 GCD는 모든 [11]숫자에 공통되는 소수 인자의 곱과 동일하지만,[12] 숫자의 쌍의 GCD를 반복하여 계산할 수도 있습니다.예를들면,

gcd(a, b, c) = gcd(a, gcd(b, c)) = gcd(gcd(a, b), c) = gcd(gcd(a, c), b).

따라서, 두 정수의 GCD를 계산하는 유클리드의 알고리즘은 임의로 많은 정수의 GCD를 계산하는 것으로 충분하다.

묘사

절차.

유클리드 알고리즘은 각 단계의 출력이 다음 단계의 입력으로 사용되도록 일련의 단계로 진행됩니다.k는 알고리즘의 스텝을 카운트하는 정수로, 0부터 시작합니다.따라서, 초기 단계는 k = 0에 해당하고, 다음 단계는 k = 1에 해당하며, 이렇게 계속됩니다.

각 단계는 음이 아닌 두 개의 잔차k−1 rk−2 r로 시작합니다.알고리즘은 모든 단계에서 잔량이 꾸준히 감소하는 것을 보증하기 때문에 rk−1 이전k−2 r보다 작습니다.k번째 단계의 목표는 방정식을 만족시키는 k q와 나머지k r을 찾는 것이다.

0 µk r < rk−1 입니다.즉, 나머지 rk−2 r보다 작을k−1 때까지 큰 수 r에서 작은kk−1 수 r의 배수를 뺀다.

첫 번째 단계(k = 0)에서 나머지 r−2−1 r은 GCD를 구하는 수인 a와 b와 같다.다음 단계(k = 1)에서 나머지 부분은 b이고 나머지 r0 초기 단계와 같다.따라서 알고리즘은 일련의 방정식으로 작성될 수 있다.

a가 b보다 작을 경우 알고리즘의 첫 번째 단계는 숫자를 교환합니다.예를 들어 a < b경우 첫 번째 q0 0이고 나머지0 r은 a입니다.따라서k r은 모든 k ≤ 0에 대해 이전k−1 r보다 작습니다.

잔차는 스텝마다 감소하지만 절대 음수가 될 수 없기 때문에 나머지N r은 최종적으로 0이 되어야 합니다.이 시점에서 알고리즘은 [13]정지합니다.마지막 0이 아닌 나머지N−1 r은 a와 b의 최대 공약수이다.초기0 나머지 r과 0 사이에는 음이 아닌 정수 수가 유한하기 때문에 숫자 N은 무한할 수 없습니다.

타당성 증명

유클리드 알고리즘의 타당성은 두 단계의 [14]논거로 입증될 수 있다.첫 번째 단계에서는 0이 아닌 마지막 나머지N−1 r이 ab를 나누는 것을 보여준다.이는 공약수이므로 최대 공약수 g보다 작거나 같아야 합니다.두 번째 단계에서는 g를 포함ab의 공통수는 r을 나누어야N−1 하므로 g는 r보다 작거나 같아야N−1 한다.이 두 가지 결론은 r = g이 아니면N−1 일관성이 없다.

r이 a와 b(첫 번째 단계)를 분할하는 N−1 나타내기 위해 rN−1 이전N−2 단계r을 분할합니다.

rN−2 = qNN−1 r

마지막 남은N r은 0이기 때문이다.rN−1 또한 다음 이전 rN−3 나눈다.

rN−3 = qN−1N−2 r + rN−1

왜냐하면 방정식의 오른쪽에 있는 두 항을 나누기 때문입니다.같은 인수를 반복하면,rN−1 a와 b를 포함한 앞의 모든 나머지를 나눕니다.앞의 잔차N−2 r, rN−3 등은 나머지를 남기 때문에 a와 b를 나누지 않는다.rN−1 abN−1 공약수이므로 r µ g입니다.

두 번째 단계에서는 a와 b를 나누는 자연수 c(즉, ab의 공약수)가 나머지 rk 나눈다.정의상 a와 b는 c: a = mcb = nc배수로서 쓸 수 있다.여기m과 n은 자연수이다.따라서 r = a - qb0 = mc - qnc0 = (m - qn0)c이므로0 c는 초기 잔여0 r을 나눕니다.유사한 인수는 또한 c가 후속 잔여1 r2, r 등을 나눈다는 것을 보여준다.따라서, 최대공약수 g는 반드시 rN−1 나누어야 하며, 이는 g ≤ rN−1 의미한다. 인수의 첫 번째 부분이 역(r ), g)을N−1 나타냈기 때문에 gN−1 = r이 된다.따라서 g는 다음 쌍의 최대 [15][16]공약수이다.

g = gcd(a, b) = gcd(b, r0) = gcd(r0, r1) = … = gcd(rN−2, rN−1) = rN−1.

작업 예

Animation in which progressively smaller square tiles are added to cover a rectangle completely.
유클리드 알고리즘의 감산 기반 애니메이션.초기 직사각형의 치수는 a = 1071 b = 462이다.462×462 크기의 정사각형은 462×147개의 직사각형을 남기고 그 안에 배치됩니다.이 직사각형은 147×147 정사각형으로 타일링되어 21×147 정사각형으로 타일링되며, 그 다음 21×21 정사각형으로 타일링되어 덮이지 않은 영역이 없습니다.가장 작은 정사각형 크기인 21은 1071과 462의 GCD입니다.

예를 들어, 유클리드 알고리즘을 사용하여 a = 1071 및 b = 462의 최대 공약수를 구할 수 있다.우선, 1071에서 462의 배수를 빼서 나머지가 462보다 작을 때까지 합니다.이러한 두 배수를 빼서(q0 = 2) 나머지 147을 남길 수 있다.

1071 = 2 × 462 + 147.

그런 다음 462에서 147의 배수를 뺀 다음 나머지가 147보다 작을 때까지.세 배수를 빼서(q1 = 3) 나머지를 21로 남길 수 있습니다.

462 = 3 × 147 + 21.

그리고 나서 21의 배수는 147에서 21보다 작을 때까지 뺀다.7개의 배수를 빼서(q2 = 7), 나머지를 남기지 않습니다.

147 = 7 × 21 + 0.

마지막 나머지가 0이므로 알고리즘은 1071과 462의 최대공약수로 21로 끝납니다.이는 위의 소인수분해에서 발견된 gcd(1071, 462)와 일치합니다.표 형식의 순서는 다음과 같습니다.

스텝 k 방정식 몫과 나머지
0 1071 = q0 462 + r0 q0 = 2 및 r0 = 147
1 462 =q1 147 + r1 q1 = 3 및 r1 = 21
2 147 =q2 21 + r2 q2 = 7 및 r2 = 0, 알고리즘 종료

시각화

유클리드 알고리즘은 위에서 주어진 최대공약수에 [17]대한 타일링 유추의 관점에서 시각화할 수 있다.a-b-사각형에 정사각형 타일을 정확하게 적용한다고 가정합니다.여기서 a는 두 숫자 중 큰 숫자입니다.먼저 사각 타일을 사용하여 직사각형을 타일링하려고 합니다.단, r < b0 r-b의0 잔여 직사각형을 그대로 둡니다.그런 다음 나머지 직사각형을 r-by-r00 정사각형 타일로 타일링합니다.이렇게 하면 r-by-r11 정사각형 타일을 사용하여 타일을 만드는 등 두 번째 잔여 직사각형 r-by-r이10 남습니다.나머지 직사각형이 없는 경우(예: 정사각형 타일이 이전 남은 직사각형을 정확히 덮는 경우) 시퀀스는 종료됩니다.가장 작은 정사각형 타일의 변 길이는 원래 직사각형 치수의 GCD입니다.예를 들어, 인접한 그림에서 가장 작은 정사각형 타일은 21x21(빨간색 표시)이며, 21은 원래 직사각형(녹색 표시)의 치수인 1071과 462의 GCD입니다.

유클리드 분할

모든 k단계에서, 유클리드 알고리즘은 k 개의 숫자k−1 rk−2 r로부터 몫 q와 나머지k r을 계산한다.

rk−2 = qkk−1 r + rk

여기k r은 음이 아니며 rk−1 절대값보다 엄격히 작습니다.유클리드 나눗셈의 정의의 기초가 되는 정리는 그러한 몫과 나머지가 항상 존재하고 [18]유일함을 보장한다.

유클리드의 알고리즘의 원래 버전에서는, 몫과 나머지를 반복 감산하는 것에 의해서 구한다.k−1k, 나머지 r이 r보다k−1 작을 때까지 r에서 반복k−2 감산한다.k 후 r과 rk−1 교환되고 프로세스가 반복된다.유클리드 나눗셈은 두 교환 사이의 모든 단계를 한 단계로 줄여 더 효율적입니다.게다가, 몫은 필요하지 않기 때문에, 유클리드 나눗셈을 나머지만 주는 모듈로 연산으로 대체할 수 있다.따라서 유클리드 알고리즘의 반복은 단순해진다.

rk = rk−2 modk−1 r.

실장

알고리즘의 실장은 의사 코드로 표현할 수 있습니다.예를 들어, 분할 기반 버전은 다음과 같이 프로그래밍[19] 수 있습니다.

함수 gcd(a, b)는 b µ 0 t := b := a mod b a := t는 a를 반환합니다.

k번째 반복이 시작될 때 변수 b는 최신의 나머지k−1 r을 보유하는 반면 변수 a는 이전k−2 r을 보유한다.스텝 b := a mod b는 위의 재귀 공식k r µk−2 r modk−1 r과 동일합니다.임시 변수 t는 다음 나머지k r이 계산되는 동안 r의 k−1 유지합니다.루프 반복의 마지막에 변수 b는 나머지k r을 유지하고 변수 a는 이전 r을 유지한다k−1.

(음수 입력이 허용되거나 mod 함수가 음수 값을 반환할 수 있는 경우 마지막 행을 반환 max(a, -a)로 변경해야 합니다.)

유클리드의 원래 버전인 감산 기반 버전에서는 나머지 계산(b := a mod b)는 반복 [20]감산으로 대체됩니다.임의의 정수를 입력으로 사용하는 나눗셈 기반 버전과 달리, 감산 기반 버전은 입력이 양의 정수로 구성되고 a = b:

함수 gcd(a, b)는 a > b a := a - b, b 이외의 b := b - a - return a 입니다.

변수 a와 b는 이전 남은 rk−1k−2 r을 번갈아 유지합니다.반복 시작 시 a가 b보다 크다고 가정합니다.그러면k−2 a는 rk−1 같게 됩니다k−2.루프 반복 중 ab보다 작아질 까지 앞의 나머지 b의 배수만큼 감소합니다.다음으로 a가 나머지k r입니다.그런 다음 b는 다시 a보다 작아질 때까지 a의 배수만큼 감소되고, 그 다음 나머지k+1 r이 됩니다.

재귀[21] 버전은 연속 잔차 GCD의 동등성과 정지 조건 gcd(rN−1, 0) = rN−1 기초한다.

함수 gcd(a, b) b = 0이면 gcd(b, mod b)를 반환합니다.

(위와 같이 음의 입력이 허용되거나 mod 함수가 음의 값을 반환할 수 있는 경우 명령 "return a"를 "return max(a, -a)"로 변경해야 합니다.)

예를 들어 gcd(1071, 462)는 등가 gcd(462, 1071 mod 462) = gcd(462, 147)로부터 계산된다.후자의 GCD는 gcd(θ, 462 mod 147) = gcd(θ, 21)에서 계산되며, gcd(21, 147 mod 21) = gcd(21, 0) = 21에서 계산된다.

최소 절대 잔차법

유클리드의 알고리즘의 또 다른 버전에서, 결과적인 음의 나머지가 일반적인 양의 [22][23]나머지에 비해 크기가 작을 경우, 각 단계의 몫은 1씩 증가한다.지금까지의 방정식은

rk−2 = qkk−1 r + rk

는 r > r > 0k 이라고k−1 가정합니다.그러나 대체 음의 나머지k e는 계산할 수 있다.

rk−2 = (qkk−1 + 1) r + ek

rk−1 > 0 또는

rk−2 = (qkk−1 - 1) r + ek

rk−1 < 0인 경우.

만약k r이 ekk 대체된다면, e < r일 k, 누군가는 다음과 같은 유클리드 알고리즘의 변형을 얻는다.

rk rk−1 r / 2

각 단계에서.

레오폴드 크로네커는 이 버전이 유클리드의 알고리즘 [22][23]중 가장 적은 단계를 필요로 한다는 것을 보여주었다.더 보편적으로 크다면 만약 qk는 r k+1rk<1φ하 0.618,{\displaystyle \left{\frac{r_{k+1}}{r_{k}순서대로}}\right<>{\frac{1}{\varphi}}\sim 0.618,}이φ{\displaystyle \varphi}은 금을 선택한 것은, 모든 입력 숫자를 a와 b에, 스텝 수가 최소한의 입증된 바 있다.쥐~이오[24]

역사적 발전

"Depiction of Euclid as a bearded man holding a pair of dividers to a tablet."
유클리드 알고리즘은 아마도 유클리드 이전에 발명되었을 것이다.여기서 약 1474년의 그림에서 나침반을 들고 묘사된다.

유클리드 알고리즘은 일반적으로 [25]사용되는 가장 오래된 알고리즘 중 하나이다.그것은 유클리드의 원소(기원전 300년경), 특히 7권(제안 1-2)과 10권(제안 2-3)에 나타난다.제7권에서 알고리즘은 정수를 위해 공식화되어 있는 반면 제10권에서는 선분의 길이를 위해 공식화되어 있다.(현대에서는 실수를 위해 공식화되어 있다고 할 수 있다).그러나 현대의 사용법에서 실수로 표현되는 길이, 면적, 부피는 같은 단위로 측정되지 않으며 길이, 면적, 부피의 자연적인 단위는 존재하지 않는다.실수의 개념은 당시에는 알려지지 않았다.)후자의 알고리즘은 기하학적입니다.2개의 길이 a와 b의 GCD는 a와 b를 균등하게 측정하는 최대 길이 g에 대응합니다.즉, 길이 a와 b는 둘 다 길이 g의 정수 배수입니다.

이 알고리즘은 초기 수학자들의 결과를 [26][27]원소에 정리한 유클리드에 의해 발견되지 않았을 것이다.수학자이자 역사학자 B. L. 데르 바덴은 7권이 피타고라스 [28]학파의 수학자들에 의해 쓰여진 수론에 관한 교과서에서 유래했다고 주장한다.그 알고리즘은 아마도 크니두스의 에우독수스(기원전 [25][29]약 375년)에 의해 알려져 있었을 것이다.이 알고리즘은 유클리드[32]아리스토텔레스의 작품에서 기술 용어 ἀνφίίίίίίίίί ίίίίanthanthanthy(인류, 역감산)의 사용으로 판단하여 유독수스 [30][31]이전까지 거슬러 올라갈 수도 있다.

수세기 후, 유클리드의 알고리즘은 인도와 [33]중국에서 독립적으로 발견되었는데, 주로 천문학에서 생겨난 디오판토스 방정식을 풀고 정확한 달력을 만들기 위해서였다.5세기 후반에, 인도의 수학자이자 천문학자 아리아바타는 이 알고리즘을 "펄버라이저"[34]라고 설명했는데, 아마도 디오판토스 [35]방정식을 푸는 데 효과적이었기 때문일 것이다.Although a special case of the Chinese remainder theorem had already been described in the Chinese book Sunzi Suanjing,[36] the general solution was published by Qin Jiushao in his 1247 book Shushu Jiuzhang (數書九章 Mathematical Treatise in Nine Sections).[37]유클리드 알고리즘은 바첼트의 Problémes plaisants et déelectables (쾌하고 즐거운 문제, 1624)[34] 제2판에서 수치적으로 처음 설명되고 유럽에서 대중화되었다.유럽에서도 마찬가지로 디오판토스 방정식을 풀고 연속분수를 개발하는 데 사용되었다.확장 유클리드 알고리즘은 영국수학자 니콜라스 [38]손더슨에 의해 출판되었는데, 그는 이것을 연속 분수를 효율적으로 [39]계산하는 방법으로서 로저 코테스의 탓으로 돌렸다.

19세기에, 유클리드 알고리즘은 가우스 정수와 아이젠슈타인 정수와 같은 새로운 수 체계를 발전시켰다.1815년에 칼 가우스는 비록 그의 연구가 [40]1832년에 처음 발표되었지만, 가우스 정수의 독특한 인수분해를 보여주기 위해 유클리드 알고리즘을 사용했다.가우스는 그의 디스퀴지션 산술 (1801)에서 이 알고리즘을 언급했지만, 오직 연속 [33]분수에 대한 방법으로서만 언급하였다.피터 구스타프 르준 디리클레는 유클리드 알고리즘을 많은 수의 [41]이론의 기초로서 기술한 최초의 사람으로 보인다.Lejeune Dirichlet은 고유 인수분해와 같은 [42]수 이론의 많은 결과들이 유클리드 알고리즘이 적용될 수 있는 숫자의 다른 체계에 대해 사실일 것이라고 언급했다.Lejeune Dirichlet의 수 이론 강의는 유클리드의 알고리즘을 사용하여 새로운 일반적인 유형의 수인 대수 정수를 연구한 Richard Dedekind에 의해 편집되고 확장되었습니다.예를 들어, 데데킨트는 가우스 [43]정수의 독특한 인수분해를 사용하여 페르마의 2제곱 정리를 증명한 최초의 사람이었다.데데킨트는 또한 유클리드 도메인의 개념을 정의했는데, 유클리드 알고리즘의 일반화된 버전이 정의될 수 있는 수 체계이다(아래 설명).19세기 말, 유클리드 알고리즘은 데데킨트의 보다 일반적인 [44]이상 이론에 의해 점차 빛을 잃었다.

[유클리드 알고리즘]은 오늘날까지 남아 있는 가장 오래된 중요하지 않은 알고리즘이기 때문에 모든 알고리즘의 조부입니다.

도날드 크누트, 컴퓨터 프로그래밍의 예술, 제2권: 세미네머ical Algorithms, 제2판(1981년),

유클리드의 알고리즘의 다른 응용 프로그램들은 19세기에 개발되었다.1829년 찰스 스투름은 이 알고리즘이 주어진 [45]구간에서 다항식의 실제 근을 세는 스투름 연쇄법에서 유용하다는 것을 보여주었다.

유클리드 알고리즘은 비례하는 실수 사이의 정수 관계를 찾는 방법인 첫 번째 정수 관계 알고리즘이었다.Helaman Ferguson과 R.W. Forcade(1979)[46]의 알고리즘과 LLL [47][48]알고리즘과 같은 몇 가지 새로운 정수 관계 알고리즘이 개발되었다.

1969년 콜과 데이비는 최적의 전략을 가진 유클리드 [49]게임이라고 불리는 [50]유클리드 알고리즘에 기초한 2인용 게임을 개발했다.선수들은 두 a와 b 돌 더미로 시작한다.플레이어들은 돌아가면서 큰 더미에서 작은 더미의 m배수를 제거한다.따라서 두 개의 말뚝이 x와 y 스톤으로 구성되어 있고, 여기서 x가 y보다 크면 다음 플레이어는 큰 말뚝을 x 스톤에서 x - my 스톤으로 줄일 수 있습니다. 단, 다음 플레이어는 x 스톤이 음이 아닌 정수인 경우입니다.우승자는 한 무더기를 [51][52]0석으로 줄인 첫 번째 선수입니다.

수학적 응용 프로그램

베주 항등식

베주트의 정체성은 두 정수 a와 b의 최대공약수 g가 원래 두 숫자 a[53]b의 선형 합으로 표현될 수 있다고 말한다.즉, 항상 g = sa + [54][55]tb정수 s와 t를 찾을 수 있다.

정수 s와 t는 유클리드의 [56]알고리즘에서 방정식의 순서를 반대로 함으로써 q1, q 으로부터0 계산할 수 있다.다음에서 마지막까지의 방정식을 시작으로, g는 N−1 q와 앞의 두 잔차 rN−2N−3 r로 나타낼 수 있다.

g = rN−1 = rN−3 - qN−1N−2 r 。

이 두 잔재는 마찬가지로 그 몫과 앞의 잔재로도 표현될 수 있다.

rN−2 = rN−4 - qN−2N−3 r 및
rN−3 = rN−5 - qN−3N−4 r 。

이들 rN−3 rN−2 공식을 제1방정식으로 치환하면 나머지N−4 rN−5 r의 선형합으로서 g가 산출된다.이전 수식이 포함된 잔여물을 공식으로 대체하는 과정은 원래 a와 b에 도달할 때까지 계속할 수 있다.

r2 = r0 - q21 r
r1 = b - q10 r
r0 = a - q0 b.

모든 잔여물0 r, r 1 치환한 후, 최종 방정식은 g를 ab의 선형합으로 나타낸다: g = sa + tb.베주트의 동일성과 따라서 이전의 알고리즘은 둘 다 유클리드 도메인의 맥락으로 일반화 될 수 있다.

주요 이상 및 관련 문제

Bézout의 정체는 두 숫자 a[10]b의 최대공약수 g에 대한 또 다른 정의를 제공한다.모든 숫자 ua + vb의 집합을 고려합니다. 여기u와 v는 임의의 두 정수입니다.a와 b는 모두 g로 나누어지기 때문에 집합 내의 모든 숫자는 g로 나누어집니다.즉, 집합의 모든 수는 g의 정수배수입니다.이것은 a와 b의 모든 공통 약수에 해당된다.그러나 다른 공약수와 달리, 최대 공약수는 집합의 구성원이다. 베주 항등식에 따르면 u = s와 v = t선택하면 g가 된다.집합의 모든 구성원은 g로 나누어져야 하므로 더 작은 공통수는 집합의 구성원이 될 수 없습니다.반대로, g의 배수 m은 u = ms v = mt선택하여 얻을 수 있다. 여기s와 t는 베주우 항등식의 정수이다.이는 베주우 신원에 m을 곱하면 알 수 있다.

mg = msa + mtb.

따라서 모든 숫자 ua + vb의 집합은 g의 배수 m의 집합과 같다.즉, 2개의 수(a, b)의 모든 가능한 정수배수의 집합은 gcd(a, b)의 배수 집합과 같다.GCD는 a와 b의 이상을 발생시키는 것으로 알려져 있다.이 GCD 정의는 아이디얼(단일 요소에 의해 생성된 아이디얼)과 주 아이디얼 영역(모든 아이디얼이 주 아이디얼인 영역)의 현대 추상 대수 개념을 이끌었다.

[57]결과를 사용하여 특정 문제를 해결할 수 있습니다.예를 들어, 볼륨 a와 b의 측정 컵 두 개를 고려합니다.첫 번째 컵의 배수 u와 두 번째 컵의 배수 v를 가감산함으로써 임의의 부피 ua + vb를 측정할 수 있다.이러한 부피는 모두 g = gcd(a, b)의 배수이다.

확장 유클리드 알고리즘

베주트 항등식의 정수 s와 t는 확장된 유클리드 알고리즘을 사용하여 효율적으로 계산할 수 있다.이 확장은 유클리드의 알고리즘에[58] 두 개의 재귀 방정식을 추가한다.

sk = sk−2 - qskk−1
tk = tk−2 - qtkk−1

시작값과 함께

s−2 = 1−2, t = 0
s−1 = 0, t−1 = 1 입니다.

이 재귀를 사용하여, Bézout의 정수 s와 t는 s = sN t = tN 주어진다. 여기서 N+1은 알고리즘이 r = 0으로 끝나는N+1 단계이다.

이 접근법의 타당성은 유도로 나타낼 수 있다.알고리즘의 스텝 k - 1까지 재귀공식이 올바르다고 가정합니다.즉, 다음과 같이 가정합니다.

rj = sj a + tj b

k보다 작은 모든 j에 대해알고리즘의 k번째 단계는 다음과 같은 방정식을 제공한다.

rk = rk−2 - qrkk−1.

재귀 공식은 rk−1 r에 대해k−2 정확하다고 가정되었기 때문에 대응하는 s와 t변수로 표현될 수 있다.

rk = (sk−2 a + tk−2 b) - qk(sk−1 a + tk−1 b).

이 방정식을 재배치하면 필요에 따라 k단계의 재귀공식이 생성됩니다.

rk = sk a + tk b = (sk−2 - qskk−1) a + (tk−2 - qtkk−1) b.

매트릭스법

정수 s와 t는 동등한 행렬 [59]방법을 사용하여 찾을 수도 있습니다.유클리드의 알고리즘의 수열

2차원 잔여 벡터를 곱한 2×2의 몫 행렬의 곱으로 쓸 수 있다

M이 모든 몫 행렬의 곱을 나타내도록 하자.

이것은 유클리드 알고리즘을 형태에 단순화한다.

g를 a와 b의 선형 합으로 표현하기 위해, 이 방정식의 양변에 행렬 [59][60]M의 역수를 곱하면 된다.M행렬식은 각각 음수인 몫 행렬의 행렬식들의 곱과 같기 때문에 (-1)N+1과 같습니다.M의 행렬식은 절대 0이 아니기 때문에, 최종 잔류의 벡터는 M의 역수를 사용하여 풀 수 있다.

상위 방정식이 주어지기 때문에

g = (-1)(N+1 m22 a - m12 b),

베주트 항등식의 두 정수는 s = (-1)N+1m22 t = (-1)Nm이다12.행렬 방법은 동등한 재귀만큼 효율적이며, 유클리드 알고리즘의 단계당 두 개의 곱셈과 두 개의 덧셈이 있습니다.

유클리드의 보조인자와 고유인수분해

Bézout의 동일성은 숫자를 소수 [61]인수로 분해하는 것과 같은 유클리드의 알고리즘의 많은 응용에 필수적입니다.이를 설명하기 위해 숫자 L을 두 요인 u와 v의 곱으로 쓸 수 있다고 가정합니다. , L = uv입니다.다른 숫자 w도 L을 나누지만 u와 공역하면 w는 v를 다음 인수로 나누어야 합니다.uw의 최대공약수가 1이면 정수 s와 t는 다음과 같이 구할 수 있습니다.

1 = su + tw.

베주트의 신원이 밝혀졌어요양변에 v를 곱하면 다음과 같은 관계를 얻을 수 있습니다.

v = suv + twv = sL + twv.

w는 오른쪽의 두 항을 나누기 때문에 왼쪽의 v도 나누어야 합니다.이 결과는 유클리드의 [62]보조군이라고 알려져 있다.구체적으로는 소수가 L을 나누면 L의 적어도 1개의 계수를 나누어야 하며, 반대로 w가 일련12 수 a, a, …, an 각각에 대해 공명이라면 w도 그 곱 a1 × a2 × … × [62]an 공명한다.

유클리드의 보조정리는 모든 숫자가 소수로 [63]분해된다는 것을 증명하기에 충분하다.이를 확인하기 위해, L을 각각 m과 n개의 소인자로 분리하는 두 개의 독립적인 인수 분해가 있다고 가정하자.

L = pp12pm = qq12qn.

소수 p는 L을 가정으로 나누므로 q 인자 중 하나를 나누어야 한다. q도 소수이므로 p = q이어야 한다. p 인자로 반복적으로 나누면 각 p가 동등한 상대 q를 갖는다는 것을 알 수 있다. 두 소수 인수는 순서를 제외하고 동일하다.숫자의 소수점으로의 독특한 인수분해는 아래와 같이 수학적 증명에 많은 응용을 가지고 있다.

선형 디오판토스 방정식

"A diagonal line running from the upper left corner to the lower right. Fifteen circles are spaced at regular intervals along the line. Perpendicular x-y coordinate axes have their origin in the lower left corner; the line crossed the y-axis at the upper left and crosse the x-axis at the lower right."
선형 디오판틴 방정식의 그림, 9x + 12y = 483입니다.솔루션은 파란색 원으로 표시됩니다.

디오판토스 방정식은 해답이 정수로 제한되는 방정식이다; 그것들은 3세기 알렉산드리아의 수학자 디오판토스[64]이름을 따서 명명되었다.전형적인 선형 디오판타인 방정식은 다음과 같이[65] 정수 x와 y를 구한다.

ax + by = c

여기서 a, b, c는 정수입니다.이것은 모듈식 산술에서 x에 대한 방정식으로 쓸 수 있습니다.

ax µ c mod b.

g를 ab의 최대공약수로 하자.ax + by의 두 항은 g로 나누어집니다. 따라서 cg로 나누어져야 합니다. 그렇지 않으면 방정식이 해를 갖지 않습니다.양변을 c/g로 나누면 방정식을 베조트의 항등식으로 줄일 수 있다.

sa + tb = g

여기s와 t는 확장된 유클리드 [66]알고리즘으로 찾을 수 있다.이것은 디오판틴 방정식에 대한 하나의 해인1 x = s (c/g)와1 y = t (c/g)를 제공한다.

일반적으로 선형 디오판틴 방정식은 해나 무한대의 [67]해를 가지고 있지 않습니다.후자를 찾으려면 (x1, y1)와 (x2, y2)의 두 가지 솔루션을 고려합니다.

ax1 + by1 = c = ax2 + by2

또는 동등하게

a(x1 - x2) = b(y2 - y1).

따라서 두 x 솔루션 간의 가장 작은 차이b/g이고 y 솔루션 간의 가장 작은 차이는 a/g입니다.따라서 해법은 다음과 같이 표현될 수 있다.

x = x1 - bu/g
y = y1 + au/g.

가능한 모든 정수에 대해 u를 변화시킬 수 있으므로 단일 솔루션(x1, y1)에서 무한대의 솔루션군을 생성할 수 있습니다.용액이 양의 정수(x > 0, y > 0)여야 하는 경우, 사용할 수 있는 용액은 한정되어 있을 수 있습니다.허용 가능한 해법에 대한 이러한 제한은 방정식보다 더 많은 미지의 디오판토스 방정식의 일부 시스템이 유한한 수의 [68]해답을 가질 수 있게 합니다; 이것은 솔루션이 어떤 실수도 될 수 있는 선형 방정식 체계에서는 불가능합니다(미확정 시스템 참조).

곱셈 반전 및 RSA 알고리즘

유한 필드는 4개의 일반화 연산을 가진 숫자의 집합입니다.연산은 덧셈, 뺄셈, 곱셈 및 나눗셈이라고 불리며, 교환성, 연관성분포성과 같은 일반적인 특성이 있습니다.유한 필드의 예로는 모듈식 산술을 사용한 13개의 숫자 {0, 1, 2, ..., 12}의 집합이 있습니다.이 필드에서는 모든 수학적 연산 결과(더하기, 빼기, 곱하기 또는 나눗셈)가 감소한다. 즉, 결과가 0~12 범위 내에 올 때까지 13의 배수가 추가 또는 감산된다.예를 들어, 5 × 7 = 35 mod 13 = 9의 결과입니다.이러한 유한 필드는 임의의 소수 p에 대해 정의할 수 있으며, 보다 정교한 정의를 사용하여 소수 m p의 임의의 제곱 m에 대해서도 정의할 수 있습니다.유한 필드는 종종 Galois 필드라고 불리며 GF(p) 또는 GF(p m)로 축약됩니다.

m개의 숫자가 있는 필드에서, 모든 0이 아닌 요소 a는 aa = aa−1 ≤ 1 mod m이 되는−1 고유−1 모듈식 곱셈 역수를 가진다.이 역수는 합동 방정식 ax ≤ 1 mod [69]m 또는 등가 선형 디오판틴[70] 방정식을 풀어서 찾을 수 있다.

ax + my = 1.

이 방정식은 위에서 설명한 것처럼 유클리드 알고리즘으로 풀 수 있다.곱셈 역수를 찾는 것은 전자 상거래에서 널리 사용되는 RSA 알고리즘의 필수 단계입니다. 구체적으로는 이 방정식에 따라 메시지 [71]복호화에 사용되는 정수가 결정됩니다.RSA 알고리즘은 필드가 아닌 링을 사용하지만, 유클리드 알고리즘은 여전히 존재하는 곱셈 역수를 찾는 데 사용할 수 있습니다.유클리드 알고리즘은 또한 오류 수정 코드에 다른 응용 프로그램도 있습니다. 예를 들어, 갈로아 [72]필드를 기반으로 하는 BCH 및 리드-솔로몬 코드를 해독하기 위한 Berlekamp-Massey 알고리즘의 대안으로 사용될 수 있습니다.

중국어 잔차 정리

유클리드의 알고리즘은 또한 다중 선형 디오판토스 [73]방정식을 푸는 데 사용될 수 있다.이러한 방정식은 정수 x를 나타내는 새로운 방법을 기술하는 중국 나머지의 정리에서 발생합니다.정수를 자릿수로 나타내지 않고, N개의 코프라임 i [74]m의 세트로 나머지i x 모듈로 나타낼 수 있다.

목표는 N개의 잔여 x에서i x를 결정하는 것입니다.해결책은 다중 방정식을 모든 개별 모듈리i m의 곱인 훨씬 큰 계수 M을 가진 단일 선형 디오판틴 방정식으로 결합하는 것입니다. 그리고 M을 다음i 같이 정의합니다.

따라서i 각 M은 m을 제외i 모든 모듈의 곱이다.해결책은 다음과 같은 N개의 새로운 숫자i 찾는 것에 달려 있다.

숫자i h로, 임의의 정수 x는 다음 방정식에 의해 나머지 x로부터i 재구성될 수 있다.

숫자i h는 Mi 곱셈 역수이므로, 이전 항에서 설명한 유클리드의 알고리즘을 사용하여 찾을 수 있다.

스턴브로코트나무

유클리드 알고리즘은 모든 양의 유리수 집합을 스턴-브로코트 트리라고 불리는 무한 이진 탐색 트리로 배열하는 데 사용될 수 있다.숫자 1(분수 1/1로 표현됨)은 트리의 근원에 배치되며, 다른 숫자 a/b의 위치는 유클리드 알고리즘의 원래 형태를 사용하여 gcd(a,b)를 계산함으로써 찾을 수 있다. 여기서 각 단계는 두 주어진 숫자 중 큰 숫자를 작은 숫자(나머지 아님)로 치환하고, tw가 정지할 때,o 같은 수에 도달한다.두 숫자 중 첫 번째 숫자를 대체하는 유클리드 알고리즘의 단계는 노드에서 오른쪽 아이로 이동하는 트리의 단계에 대응하고, 두 숫자 중 두 번째 숫자를 대체하는 단계는 노드에서 왼쪽 아이로 이동하는 트리의 단계에 대응한다.이 방법으로 작성된 스텝의 시퀀스는 a/b가 최저값으로 지정되어 있는지 여부에 따라 달라지지 않고 루트부터 번호 a/[75]b를 포함하는 노드까지의 경로를 형성합니다.이 사실은 각 양의 유리수가 이 트리에 정확히 한 번 나타난다는 것을 증명하기 위해 사용될 수 있습니다.

예를 들어 3/4은 루트에서 시작하여 왼쪽으로 한 번 이동한 후 오른쪽으로 두 번 이동하여 찾을 수 있습니다.

i = 1, 2, 3, 4에 대한 순서 i의 스턴-브로코트 나무 및 스턴-브로코트 시퀀스

유클리드 알고리즘은 칼킨-윌프 트리라고 불리는 유리수의 다른 이진수 트리와 거의 같은 관계를 가지고 있다.다른 점은 경로가 반대된다는 것입니다. 즉, 트리의 루트에서 타깃으로 경로를 생성하는 대신 타깃에서 루트로 경로를 생성합니다.

연속 분수

유클리드 알고리즘은 [76]연속분수와 밀접한 관계가 있다.방정식의 수열은 다음 형식으로 작성될 수 있습니다.

오른쪽의 마지막 항은 항상 다음 방정식의 왼쪽 항과 같습니다.따라서, 처음 두 방정식은 다음과 같이 결합될 수 있다.

세 번째 방정식은 분모항1 r/r0 대체하기 위해 사용될 수 있다.

잔차 rk/rk−1 최종 비율은 항상 최종 방정식까지 시리즈의 다음 방정식을 사용하여 대체할 수 있습니다.결과는 연속 분수입니다.

위의 작업 에서는 gcd(1071, 462)가 계산되었으며, 지수k q는 각각 2, 3, 7이었다.따라서, 1071/462는 다음과 같이 기록될 수 있다.

계산으로 확인할 수 있듯이

인수분해 알고리즘

최대공약수를 계산하는 것은 폴라드의 rho 알고리즘,[78] 쇼르 알고리즘,[79] 딕슨의 인수분해[80] 방법 및 렌스트라 타원곡선 [81]인수분해와 같은 여러 정수 인수분해 [77]알고리즘에서 필수적인 단계입니다.유클리드 알고리즘은 이 GCD를 효율적으로 찾기 위해 사용될 수 있다.연속분율인수분해는 유클리드의 [82]알고리즘을 사용하여 결정되는 연속분수를 사용한다.

알고리즘 효율

"A set of colored lines radiating outwards from the origin of an x-y coordinate system. Each line corresponds to a set of number pairs requiring the same number of steps in the Euclidean algorithm."
gcd(x,y)에 대한 유클리드 알고리즘의 단계 수.옅은(빨간색 및 노란색) 점은 스텝 수가 상대적으로 적은 것을 나타내고, 진한(자줏빛 및 파란색) 점은 스텝 수가 많은 것을 나타냅니다.가장 큰 어두운 영역은 y = δx 을 따릅니다. 여기서 δ황금 비율입니다.

유클리드의 알고리즘의 계산 효율은 [83]철저히 연구되었다.이 효율성은 알고리즘이 필요로 하는 나눗셈 단계의 수에 각 단계의 계산 비용을 곱한 값으로 설명할 수 있습니다.유클리드 알고리즘의 첫번째 알려진 분석 A.A.L. 레노 1811,[84]에는 분열 단계에서 입력(u, v)에 번호를 v에 의해 제한된 데, 후 그는+2. 나중에, 1841년, P.J.E.Finck은 사단 스텝 수가 대부분의 2log2 v+1시에 있으며, 따라서 유클리드 알고리즘 시간 polyno에서 영업합니다 showed[85]v/2에 이 향상되었다고 예정이다.mial에입력 [86]크기에밀 레거는 1837년에 최악의 경우를 연구했는데, 이는 입력이 연속된 피보나치 [86]수인 경우이다.Finck의 [87]분석은 1844년 Gabriel Lamé에 의해 개선되었으며, 그는 완성에 필요한 단계 수가 더 작은 숫자 [88][89]b의 10자리 숫자 h의 5배를 넘지 않는다는 것을 보여주었다.

균일한 비용 모델(단일 기계어에 맞는 숫자에 대한 gcd 계산의 복잡성을 분석하기에 적합)에서는 알고리즘의 각 단계가 일정한 시간이 소요되며, Lamé의 분석은 총 실행 시간도 O(h)임을 암시한다.그러나 큰 숫자의 계산에 적합한 계산 모델에서는 알고리즘의 단일 잔여 계산의 계산 비용은 O(h)[90]만큼2 클 수 있다.이 경우 알고리즘의 모든 스텝에 대한 총 시간은 텔레스코핑 시리즈를 사용하여 분석할 수 있으며, O(h)도2 마찬가지임을 알 수 있습니다.빠른 정수 곱셈을 위한 Schönhage-Strassen 알고리즘에 기초한 최신 알고리즘 기법은 GCD를 [91][92]위한 준선형 알고리즘으로 이어지는 속도를 높이기 위해 사용될 수 있다.

스텝 수

두 자연수 a와 b의 GCD를 계산하는 단계 수는 T(a, b)[93]로 나타낼 수 있다.g가 ab의 GCD일 경우, 코프라임 수 mn에 대해 a = mg, b = ng이다.그리고나서

T(a, b) = T(m, n)

유클리드 알고리즘의 모든 단계를 [94]g로 나누면 알 수 있다.같은 인수로 a와 b에 공통 인수 w를 곱하면 스텝 는 동일하게 유지됩니다: T(a, b) = T(wa, wb).따라서 스텝 T는 2개의 GCD의 크기에 따라 T(a, b) 및 T(a, b + 1)와 같은 인접한 번호 쌍 간에 크게 다를 수 있습니다.

유클리드 알고리즘의 재귀적 특성은 다른 방정식을 제공한다.

T(a, b) = 1 + T(b, r0) = 2 + T(r0, r1) = … = N + T(rN−2, rN−1) = N + 1

여기서 T(x, 0) = 0입니다.[93]

최악의 경우

유클리드 알고리즘에서 자연수 a > b > 0 쌍에 대해 N개의 스텝이 필요한 경우, 이것이 참인 a와 b의 최소값은 [95]각각 피보나치FN+2N+1 F입니다.보다 정확하게 말하면, 유클리드 알고리즘이 쌍 a > b에 대해 N개의 스텝을 필요로 하는 경우, 1개N+2 스텝은 θ F와 b δN+1 F를 가진다.이것은 [96]유도로 나타낼 수 있다.N = 1이면 b는 a를 나머지 없이 나눈다. 이것이 참인 가장 작은 자연수는 각각 F3 F2 b = 1과 a = 2이다.이제 결과가 N에서 M - 1까지의 모든 값에 대해 유지된다고 가정합니다.M 단계 알고리즘의 첫 번째 단계는 a = qb0 + r이며0, 유클리드 알고리즘은 쌍 b > r에 대해0 M - 1 단계를 필요로 한다. 유도 가설에 따르면, 하나는 b fM+1 F0 r fM F를 갖는다.따라서 a = qb0 + r0 b b + r0 fM+1 F + FM = FM+2 원하는 부등식이다.1844년 가브리엘 라메에 의해 발표된 이 증거는 계산 복잡성 [97]이론의 시작이자 피보나치 숫자의 [95]첫 번째 실용적 적용을 나타냅니다.

이 결과는 Euclid 알고리즘의 단계 수가 자릿수의 5배를 초과할 수 없다는 것을 보여주는 것으로 충분하다(기본값 10).[98]알고리즘에 N개의 스텝이 필요한 경우, b는 F보다 크거나 같고, F보다N+1N−1 크거나 같으며, 여기서 θ황금비율입니다.b b φN−1 、 N - 1 logφ logb 。log10's > 1/5이므로 (N - 1)/5 < logb10φ = logb10.따라서 N 5 5 logb10 입니다.따라서 유클리드 알고리즘은 항상 O(h) 나눗셈보다 작아야 합니다. 여기서 h는 작은 숫자 b의 자리수입니다.

평균

유클리드 알고리즘에 의해 취해진 평균 단계 수는 세 가지 다른 방법으로 정의되었다.첫 번째 정의는 0부터 a - 1까지의[93] 정수에서 동일한 확률로 선택된 주어진 숫자 a와 더 작은 자연수 b의 GCD를 계산하는 데 필요한 평균 시간 T(a)이다.

단, T(a, b)는 두 숫자의 GCD에 따라 크게 변동하므로 평균 함수 T(a)도 마찬가지로 "소음"[99]이 된다.

이 노이즈를 줄이기 위해 두 번째 평균 µ(a)가 모든 숫자에 걸쳐서

a보다 작은 θ(a)공칭 정수가 있는데, 여기서 θ는 오일러의 전체 함수이다.이 타우 평균은 a와 함께 부드럽게[100][101] 성장합니다.

여기θ−(1/6) + ε 극소수이며, 잔차입니다.이 공식의 상수 C(포터 상수[102])는 다음과 같습니다.

여기서 θ 오일러-마셰로니 상수이고 θ'는 리만 제타 [103][104]함수의 도함수이다.선행 계수(12/θ2) ln 2는 두 가지 독립적인 [105][106]방법으로 결정되었습니다.

첫 번째 평균은 타우 평균으로부터 계산될 수 있기 때문에, tau[107] 제수 d에 대한 합계에 의해

그것은[108] 공식으로 근사할 수 있다

여기서 δ(d)는 망골트 [109]함수입니다.

세 번째 평균 Y(n)는 ab가 모두 (균일한 분포로) 1에서[108] n까지 무작위로 선택될 때 필요한 평균 단계 수로 정의된다.

이 방정식에 T(a)의 근사 공식을 대입하면 Y(n)[110]대한 추정치가 산출된다.

단계별 계산 비용

유클리드 알고리즘의 각 단계 k에서, k q와 나머지k r은 주어진 정수k−2 rk−1 r 쌍에 대해 계산된다.

rk−2 = qkk−1 r + rk.

스텝당k 계산비용은 주로 q를 찾는k 것과 관련이 있습니다.나머지 r은 r, rk−1 k q에서 빠르게k−2 계산할 수 있기 때문입니다.

rk = rk−2 - qkk−1 r.

h-bit 수를 나누는 계산 비용은 O(h(θ+1))로 계산됩니다.여기서 θ[90]몫의 길이입니다.

비교하자면, 유클리드의 원래 감산 기반 알고리즘은 훨씬 느릴 수 있다.단일 정수 나눗셈은 뺄셈의 q 수와 같습니다.만약 ab의 비율이 매우 크다면, 그 몫은 크고 많은 감산이 필요할 것이다.반면, 그 몫은 작은 정수일 가능성이 매우 높은 것으로 나타났다.주어진 몫 q의 확률은 약 ln u/(u - 1)이며, 여기서 u = (q + 2[111]1)입니다.그림에서 1, 2, 3, 또는 4의 몫 확률은 각각 대략 41.5%, 17.0%, 9.3%, 5.9%입니다.뺄셈의 연산이 나눗셈보다 빠르기 때문에, 특히 큰 [112]수의 경우, 뺄셈 기반의 유클리드의 알고리즘은 나눗셈 기반의 [113]버전과 경쟁적입니다.이것은 유클리드의 [114]알고리즘의 바이너리 버전에서 이용된다.

추정 단계 수와 단계당 추정 계산 비용을 결합하면 유클리드의 알고리즘이 처음 두 숫자 a와 b의 평균 자릿수 h와 2차적으로 성장한다는2 것을 알 수 있다.h0, h1, ..., hN−1 연속되는 잔차0 r, r1, ..., rN−1 자릿수를 나타냅니다.N의 스텝수는 h에 따라 선형적으로 증가하므로 실행 시간은 다음과 같이 제한됩니다.

대체 방법

유클리드의 알고리즘은 그 [115]단순성 때문에 특히 적은 숫자에 대해 실제로 널리 사용되고 있다.비교를 위해 유클리드의 알고리즘에 대한 대안들의 효율성을 결정할 수 있다.

자연수 a와 b의 GCD를 찾는 비효율적인 접근법 중 하나는 모든 공통수를 계산하는 것이다. 그러면 GCD가 가장 큰 공통수가 된다.공통 제수는 두 숫자를 2부터 작은 숫자 b까지의 연속 정수로 나누어 찾을 수 있습니다.이 어프로치의 스텝 수는 b에 따라 선형적으로 증가하거나 자리수로 기하급수적으로 증가합니다.또 다른 비효율적인 접근법은 하나 또는 두 숫자의 소인수를 찾는 것입니다.위에서 설명한 바와 같이, GCD는 두 개의 숫자 a[6]b가 공유하는 소인수의 곱과 같다.현재의 소인수 분해 방식도 비효율적입니다. 현대의 많은 암호화 시스템은 이러한 [9]비효율성에 의존하고 있습니다.

바이너리 GCD [116][117]알고리즘컴퓨터에서 사용되는 바이너리 표현을 이용하여 보다 빠른 연산으로 분할을 대체하는 효율적인 대안입니다.그러나 이 대안은 O()같이 스케일도 조정됩니다.이것은 일반적으로 실제 컴퓨터의 유클리드 알고리즘보다 빠릅니다. 비록 같은 방식으로 [91]확장되더라도 말이죠.2개의 숫자 a[118][119]b의 선두 자리만을 조사하는 것으로, 한층 더 효율화를 얻을 수 있다.바이너리 알고리즘은 다른 베이스(k-ary 알고리즘)[120]로 확장할 수 있으며 속도가 [121]최대 5배 향상됩니다.레머의 GCD 알고리즘은 바이너리 알고리즘과 같은 일반 원리를 사용하여 임의의 베이스에서 GCD 계산 속도를 높입니다.

매우 큰 정수(25,000자리 이상)에 대한 재귀적 접근은 Schönhage [123][124]알고리즘,[122] Stehlé 및 Zimmermann과 [125]같은 준선형 정수 GCD 알고리즘으로 이어진다.이 알고리즘들은 위에 주어진 유클리드 알고리즘의 2×2 행렬 형식을 이용한다.이러한 준선형 방법은 일반적으로 O(h(log 2h))(log log h)[91][92]로 확장된다.

일반화

비록 유클리드 알고리즘이 두 자연수의 최대공약수를 찾는 데 사용되더라도, 그것은 실수와 다항식,[126] 2차[127] 정수, 그리고 후르비츠 [128]사분수와 같은 다른 수학적 물체로 일반화 될 수 있다.후자의 경우, 유클리드 알고리즘은 고유한 인수 분해의 결정적인 속성을 증명하기 위해 사용된다. 즉, 그러한 숫자는 소수의 대항수인 환원 불가능한 요소로 고유하게 인수 분해될 수 있다.독특한 인수분해는 많은 수의 이론 증명에 필수적이다.

유리수와 실수수

유클리드의 알고리즘은 유클리드가 그의 원소 10권에서 설명한 대로 실수에 적용할 수 있다.알고리즘의 목적은 두 개의 주어진 실수 a와 b가 그것의 정수 배수인 a = mg와 b = ng가 되도록 실수 g를 식별하는 것이다. 여기m과 n은 [26]정수이다.이 식별은 실수 a와 b 사이의 정수 관계를 찾는 것과 같다. 즉, sa + tb = 0되도록 정수 s와 t를 결정한다.유클리드는 이 알고리즘을 사용하여 비교할 수 없는 [129][130]길이의 문제를 다룬다.

실수 유클리드 알고리즘은 두 가지 점에서 정수 알고리즘과 다르다.먼저, 나머지 rk 실수이지만, 이전과 같이k quotients q는 정수이다.둘째, 알고리즘이 한정된 수의 N개의 스텝으로 끝나는 것을 보증하지 않습니다.만약 그렇다면, 분수 a/b는 유리수, 즉 두 정수의 비율이다.

유한 연속분수 [q0; q12, q, ..., qN]로 쓸 수 있습니다.알고리즘이 정지하지 않으면 분수 a/b무리수이며 무한 연속분수 [q0; q12, q, …][131]로 나타낼 수 있습니다.무한 연속 분수의 예로는 황금 비율 θ = [1; 1, 1, ...], 2의 제곱근 θ2 = [1; 2, 2, ...][132] 등이 있습니다.2개의 실수의 거의 모든 비율 a/b가 [133]비이성적이기 때문에 알고리즘이 멈출 가능성은 거의 없습니다.

스텝 k [q0;q1, q2, ..., qk]에서 무한 연속 분수를 잘라서 k가 증가할수록 개선되는 a/b에 대한 근사치를 얻을 수 있다.근사치는 수렴 mk/n으로k 설명되며, 분자와 분모는 공명하며 반복 관계를 따릅니다.

여기−1 m = n−2 = 1 −2 m = n−1 = 0은 재귀의 초기 값입니다.수렴k m/nk 분모k [134]n을 갖는 a/b에 대한 최선유리수 근사치입니다.

다항식

단일 변수 x의 다항식은 더하고, 곱하고, 줄일 수 없는 다항식으로 인수분해할 수 있는데, 이는 정수에 대한 소수들의 유사체이다.다항식 a(x)와 b(x)의 최대공약수 다항식 g(x)는 유클리드 [126]알고리즘을 사용하여 식별할 수 있는 그들의 공유 불가역 다항식의 곱으로 정의된다.기본 절차는 정수와 비슷합니다.스텝 k에서 재귀 방정식을 만족시키기 위해 몫 다항식k q(x)와 나머지 다항식k r(x)를 동정한다.

여기−2 r(x) = a(x)r−1(x) = b(x)이다.각 몫 다항식은 각 나머지가 0이거나 이전 수준인 deg[rk(x)] < deg[rk−1(x)]보다 작은 차수를 가지도록 선택된다.정도는 음이 아닌 정수이기 때문에, 그리고 모든 단계에서 감소하기 때문에, 유클리드 알고리즘은 유한한 수의 단계로 끝납니다.마지막 0이 아닌 나머지는 원래의 두 다항식, a(x)와 b([135]x)의 최대 공약수이다.

예를 들어, 각 인자가 두 개의 2차 다항식으로 구성된 다음 두 개의 4차 다항식을 고려합니다.

a(x)를 b(x)로 나누면 나머지0 r(x) = x3 + (2/3)x2 + (5/3)x - (2/3)가 된다.다음 단계에서 b(x)를 r(x)0 나누면 나머지1 r(x2) = x + x + 2가 된다.마지막으로, r(x)를 r(x)1 나누면0 0이 남는다. 이는 r(x)가 인수분해와 일치하는 a(x)와 b(x)의 최대공약수 다항식임을 나타낸다1.

위에서 설명한 정수 응용 프로그램의 대부분은 다항식으로 [136]넘어갑니다.유클리드 알고리즘은 다항식의 선형 디오판타 방정식과 중국어 잔차 문제를 푸는 데 사용될 수 있다. 다항식의 연속된 분율도 정의할 수 있다.

다항식 유클리드 알고리즘은 주어진 실구간 [137]안에 있는 다항식의 0을 세는 방법인 스터름 체인 같은 다른 응용 프로그램을 가지고 있다.이는 제어 [138]이론 Routh-Hurwitz 안정성 기준과 같은 여러 분야에서 적용된다.

마지막으로, 다항식의 계수는 정수, 실수 또는 복소수에서 도출할 필요가 없다.예를 들어 계수는 위에서 설명한 유한 필드 GF(p)와 같은 일반 필드로부터 도출할 수 있다.유클리드 알고리즘과 그 응용에 대한 해당 결론은 그러한 [126]다항식에도 적용된다.

가우스 정수

"A set of dots lying within a circle. The pattern of dots has fourfold symmetry, i.e., rotations by 90 degrees leave the pattern unchanged. The pattern can also be mirrored about four lines passing through the center of the circle: the vertical and horizontal axes, and the two diagonal lines at ±45 degrees."
규범2 u + v2 500 미만인 복합 평면에서 가우스 소수 u + vi 분포

가우스 정수는 α = u + vi 형식복소수이며, 여기u와 v는 일반[note 2] 정수이고 i는 음수 [139]1의 제곱근이다.유클리드 알고리즘의 아날로그를 정의함으로써,[40] 가우스 정수는 위의 인수에 의해 유일하게 인수분해된다는 것을 보여줄 수 있다.이 독특한 인수분해는 모든 피타고라스 3배를 도출하거나 두 [139]제곱합에 대한 페르마의 정리를 증명하는 것과 같은 많은 응용 분야에서 도움이 됩니다.일반적으로, 유클리드 알고리즘은 그러한 어플리케이션에서 편리하지만 필수적이지는 않다. 예를 들어, 이론들은 종종 다른 인수에 의해 증명될 수 있다.

두 개의 가우스 정수 α와 β에 대해 개발된 유클리드 알고리즘은 일반 [140]정수와 거의 동일하지만 두 가지 측면에서 다르다.이전과 같이, 우리는 r = α−1 r = β를 설정하고−2, 각 단계 k에서의 과제는 다음과 같이 k q와 나머지 rk 식별하는 것이다.

여기서 모든 나머지는 이전 값보다 엄격히 작다: rk < rk−1. 첫 번째 차이점은 몫과 잔차는 그 자체로 가우스 정수이며, 따라서 복소수라는 것이다.k q는 일반적으로 정확한 비율(복소수 α/β 등)의 실수 부분과 복소 부분을 가장 가까운 [140]정수로 반올림하여 구한다.두 번째 차이점은 한 복소수가 다른 복소수보다 "작을" 수 있는 방법을 정의할 필요성에 있습니다.이를 위해 모든 가우스 정수 u + vi를 일반 정수2 변환하는2 표준 함수 f(u + vi) = u + v가 정의됩니다.유클리드 알고리즘의 각 단계 k 후에, 나머지 f(rk)의 노름은 앞의 나머지 f(rk−1)의 노름보다 작다.노름은 음이 아닌 정수이며 단계마다 감소하기 때문에 가우스 정수에 대한 유클리드 알고리즘은 제한된 수의 단계로 [141]끝납니다.마지막 0이 아닌 나머지는 α와 β를 나누는 가장 큰 노름의 가우스 정수인 gcd(α, β)이다. 단위는 ±1 또는 ±[142]i이다.

유클리드 알고리즘의 다른 많은 응용 프로그램들은 가우스 정수로 대체된다.예를 들어, 선형 디오판타 방정식과 가우스 [143]정수에 대한 중국어 나머지 문제를 푸는 데 사용할 수 있습니다. 가우스 정수의 연속 분율도 [140]정의할 수 있습니다.

유클리드 도메인

덧셈과 곱셈으로 표시된 두 개의 2진수 연산 하에서 일련의 원소는 교환환 R을 형성하면 유클리드 도메인이라고 불리며,[144][145] 대략적으로 말하면 일반화된 유클리드 알고리즘이 그것들에 대해 수행될 수 있다면 유클리드 도메인이라고 불린다.이러한 고리의 두 연산은 일반 산술의 덧셈과 곱셈일 필요는 없으며, 수학 이나 모노이드의 연산과 같이 더 일반적일 수 있다.그럼에도 불구하고, 이러한 일반 연산은 교환성, 연관성분배성과 같은 일반적인 산술에 관한 많은 법칙을 존중해야 한다.

일반화 유클리드 알고리즘은 유클리드 함수, 즉 R에서 음이 아닌 정수 세트로의 매핑 f를 필요로 한다. 즉, R에서 0이 아닌 두 요소 a와 b에 대해, R qb + rf(r) < f(b)[146]가 존재하도록 q와 r가 존재한다.이러한 매핑의 예로는 정수의 절대값, 일변량 다항식의 정도, 위의 [147][148]가우스 정수의 노름 등이 있습니다.알고리즘의 각 스텝이 f를 무한히 감소시키는 것이 기본 원리입니다.따라서 f를 한정된 횟수만 줄일 수 있다면 알고리즘은 한정된 수의 스텝으로 정지해야 합니다.이 원리는 음이 아닌 정수의 순서의 특성에 의존하며, 음이 아닌 정수의 빈 집합은 모두 최소 [149]멤버를 가지고 있다고 주장합니다.

산술의 기본정리는 모든 유클리드 영역에 적용된다.유클리드 영역의 어떤 숫자든 환원 불가능한 요소로 고유하게 인수분해할 수 있다.모든 유클리드 도메인은 고유 인수분해 도메인(UFD)이지만, 그 반대가 [149]참은 아니다.유클리드 도메인과 UFD는 GCD 도메인의 하위 분류로, 두 숫자의 최대공약수가 [150]항상 존재한다.다시 말해, 최대공약수는 유클리드 알고리즘을 사용하여 찾을 수 없지만 (도메인 내의 모든 요소 쌍에 대해) 존재할 수 있다.유클리드 도메인은 항상 모든 이상이 주 [151]아이디얼통합 도메인인 주요 아이디얼 도메인이다.다시 말하지만, 그 반대는 사실이 아니다: 모든 PID가 유클리드 도메인은 아니다.

유클리드 도메인의 고유한 인수분해는 많은 응용 분야에서 유용하다.예를 들어, 가우스 정수의 독특한 인수분해는 모든 피타고라스 3배의 공식을 도출하고 [139]제곱합에 대한 페르마의 정리를 증명하는 데 편리하다.독특한 인수분해는 1847년 유클리드의 알고리즘의 효율성을 조셉 리우빌[152]제안에 기초하여 분석한 수학자 가브리엘 라메에 의해 발표된 페르마의 마지막 정리의 핵심 증명에서도 핵심 요소였다.라메의 접근방식은 x + µy 형식의 숫자에 대한 고유한 인수분해를 필요로 했다. 여기x와 y는 정수이고, θ2/n = e는 1의 n번째 루트이다. 즉, θn = 1. 이 접근방식은 n의 일부 값(: n = 3, 아이젠슈타인 정수)에 대해 성공하지만, 일반적으로 그러한 숫자들은 고유하게 인수분해를 하지 않는다.몇몇 사이클로토믹 분야에서 독특한 인수분해의 실패는 에른스트 쿠머를 이상적인 수의 개념으로 이끌었고, 후에 리하르트 데데킨트[153]이상을 이끌어냈다.

2차 정수의 고유 인수분해

"A set of dots lying within a circle. The pattern of dots has sixfold symmetry, i.e., rotations by 60 degrees leave the pattern unchanged. The pattern can also be mirrored about six lines passing through the center of the circle: the vertical and horizontal axes, and the four diagonal lines at ±30 and ±60 degrees."
아이젠슈타인의 분포는 500 미만의 규범으로 복소 평면에서 u + 소수화한다.숫자 is1의 세제곱근입니다.

2차 정수 은 유클리드 영역을 설명하는 데 유용합니다.2차 정수는 가상 단위 i가 숫자 θ로 대체되는 가우스 정수의 일반화입니다.따라서 이들 형식은 u + v,입니다.여기u와 v는 정수이며 has파라미터 D에 따라 두 가지 형식 중 하나입니다.D가 4+1의 배수와 같지 않은 경우

, D가 4+1의 배수일 경우

만약 함수 f가 위의 가우스 정수를 정렬하는데 사용되는 과 같은 노름 함수에 대응한다면, 그 영역은 노름-유클리드라고 알려져 있다.2차 정수의 노름-유클리드 고리는 정확히 D가 -11, -7, -2, -1, 2, 3, 5, 7, 11, 13, 17, 19, 21, 29, 33, 37, 41, 57, 또는 [154][155]73의 값 중 하나일 이다.사례 D = -1 D = -3은 각각 가우스 정수아이젠슈타인 정수를 산출한다.

만약 f가 유클리드 함수가 되도록 허용된다면, 그 도메인이 유클리드인 D의 가능한 값의 [156]목록은 아직 알려지지 않았다.규범-유클리드 영역이 아닌 유클리드 영역의 첫 번째 예는 [156]1994년에 발표되었다.1973년, 와인버거는 D > 0인 2차 정수환이 유클리드라는 것을 증명하였다. 만약 그것이 일반화된 리만 가설[127]유지된다면, 그리고 그것이 주요 이상 영역일 경우에만.

비가환환

유클리드 알고리즘은 후르비츠 [clarification needed][128]사분위수 집합과 같은 일부 비가환환에 적용될 수 있다.α와 β는 이러한 고리로부터 2개의 원소를 나타내도록 하자.이들은 α = β = β = β β일 경우 링 내 ββ 중 어떤 선택을 위해 공통의 오른쪽 제수를 갖는다.마찬가지로, 이들은 α = β = dθ일 경우 공통의 왼쪽 제수를 갖는다.곱셈은 가환적이지 않기 때문에, 유클리드 알고리즘에는 오른쪽 제수를 위한 것과 왼쪽 제수를 [128]위한 것의 두 가지 버전이 있습니다.올바른 제수를 선택하면, 유클리드 알고리즘에 의해 gcd(α, β)를 찾는 첫 번째 단계가 기록될 수 있다.

여기서 repres0 지수를 나타내고 [clarification needed]the0 나머지를 나타냅니다.이 방정식은 α와 β의 어떤 공통 오른쪽 약수도 마찬가지로 나머지 β0 공통 약수임을 보여준다.왼쪽 제수에 대한 유사한 방정식은 다음과 같습니다.

어느 쪽을 선택해도 오른쪽 또는 왼쪽의 최대 공통 약수가 식별될 때까지 위와 같은 과정을 반복합니다.유클리드 영역에서와 같이, 나머지 θ0 "크기" (공식적으로 그것의 노름)는 β보다 엄격히 작아야 하며, 알고리즘의 [157]종료를 보증하기 위해 θ0 대해 가능한 크기의 유한한 수만이 있어야 한다.

GCD에 대한 대부분의 결과는 비가환적인 [clarification needed]수치로 넘어갑니다.예를 들어 Bézout의 동일성은 오른쪽 gcd(α, β)가 α[158]β의 선형 조합으로 표현될 수 있음을 나타낸다.즉, 숫자 and과 숫자 such가 있고, 다음과 같은 것이 있습니다.

왼쪽 GCD에 대한 유사한 ID는 거의 동일합니다.

베조의 정수는 디오판토스 방정식을 푸는 데 사용될 수 있다.예를 들어, 모든 양의 정수가 4제곱의 합으로 표현될 수 있다는 라그랑주 정리의 표준 증명 중 하나는 이러한 방식으로 [157]4제곱 GCD에 기초한다.

「 」를 참조해 주세요.

  • 유클리드 리듬, 유클리드 알고리즘을 사용하여 음악 리듬을 생성하는 방법

메모들

  1. ^ I. N. Herstein대수학 주제와 Serge Lang의 대수학 같은 널리 사용되는 몇몇 교과서들은 유클리드 나눗셈을 언급하기 위해 "유클리드 알고리즘"이라는 용어를 사용한다.
  2. ^ "일반 정수"라는 문구는 보통 정수와 가우스 정수를 구별하기 위해, 그리고 더 일반적으로 대수 정수와 구별하기 위해 사용됩니다.

레퍼런스

  1. ^ 스타크 1978, 페이지 16
  2. ^ 스타크 1978, 페이지 21
  3. ^ 르베크 1996, 32페이지
  4. ^ 르베크 1996, 31페이지
  5. ^ Grossman, J. W. (1990). Discrete Mathematics. New York: Macmillan. p. 213. ISBN 0-02-348331-8.
  6. ^ a b 슈뢰더 2005, 페이지 21-22
  7. ^ 슈뢰더 2005, 페이지 19
  8. ^ Ogilvy, C. S.; Anderson, J. T. (1966). Excursions in number theory. New York: Oxford University Press. pp. 27–29.
  9. ^ a b 슈뢰더 2005, 216–219페이지
  10. ^ a b 르베크 1996, 33페이지
  11. ^ 스타크 1978, 페이지 25
  12. ^ 광석 1948, 47~48페이지
  13. ^ 스타크 1978, 페이지 18
  14. ^ 스타크 1978, 16-20페이지
  15. ^ Knuth 1997, 320페이지
  16. ^ Lovász, L.; Pelikán, J.; Vesztergombi, K. (2003). Discrete Mathematics: Elementary and Beyond. New York: Springer-Verlag. pp. 100–101. ISBN 0-387-95584-4.
  17. ^ Kimberling, C. (1983). "A Visual Euclidean Algorithm". Mathematics Teacher. 76: 108–109.
  18. ^ Dummit, David S.; Foote, Richard M. (2004). Abstract Algebra. John Wiley & Sons, Inc. pp. 270–271. ISBN 978-0-471-43334-7.
  19. ^ Knuth 1997, 319–320페이지
  20. ^ Knuth 1997, 318–319페이지
  21. ^ 스틸웰 1997, 14페이지
  22. ^ a b 광석 1948, 페이지 43
  23. ^ a b Stewart, B. M. (1964). Theory of Numbers (2nd ed.). New York: Macmillan. pp. 43–44. LCCN 64010964.
  24. ^ Lazard, D. (1977). "Le meilleur algorithme d'Euclide pour K[X] et Z". Comptes rendus de l'Académie des Sciences (in French). 284: 1–4.
  25. ^ a b Knuth 1997, 318페이지
  26. ^ a b Weil, A. (1983). Number Theory. Boston: Birkhäuser. pp. 4–6. ISBN 0-8176-3141-0.
  27. ^ Jones, A. (1994). "Greek mathematics to AD 300". Companion encyclopedia of the history and philosophy of the mathematical sciences. New York: Routledge. pp. 46–48. ISBN 0-415-09238-8.
  28. ^ van der Waerden, B. L. (1954). Science Awakening. translated by Arnold Dresden. Groningen: P. Noordhoff Ltd. pp. 114–115.
  29. ^ von Fritz, K. (1945). "The Discovery of Incommensurability by Hippasus of Metapontum". Annals of Mathematics. 46 (2): 242–264. doi:10.2307/1969021. JSTOR 1969021.
  30. ^ Heath, T. L. (1949). Mathematics in Aristotle. Oxford Press. pp. 80–83.
  31. ^ Fowler, D. H. (1987). The Mathematics of Plato's Academy: A New Reconstruction. Oxford: Oxford University Press. pp. 31–66. ISBN 0-19-853912-6.
  32. ^ Becker, O. (1933). "Eudoxus-Studien I. Eine voreuklidische Proportionslehre und ihre Spuren bei Aristoteles und Euklid". Quellen und Studien zur Geschichte der Mathematik B. 2: 311–333.
  33. ^ a b 스틸웰 1997, 31페이지
  34. ^ a b 태터솔 2005, 페이지 70
  35. ^ 로젠 2000, 86~87페이지
  36. ^ 광석 1948, 페이지 247~248
  37. ^ 태터솔 2005, 페이지 72, 184-185
  38. ^ Saunderson, Nicholas (1740). The Elements of Algebra in Ten Books. University of Cambridge Press. Retrieved 1 November 2016.
  39. ^ 태터솔 2005, 72-76페이지
  40. ^ a b 가우스, C.F.(1832년)."Theoria biquadraticorum residuorum".가. 속짱. 레지. Sci.Gött. 레크리에이션. 4. 가우스, C.F.(2011년)에서 Reprinted."Theoriabiquadraticorum commentatio의 프리 residuorum".Werke.Vol2. 케임브리지 대학교프레스.를 대신하여 서명함. 65–92. doi:10.1017/CBO9781139058230.004.아이 에스비엔 9781139058230., 그리고 가우스, C.F.(2011년)."Theoriabiquadraticorumcommentatio secunda residuorum".Werke.Vol2. 케임브리지 대학교프레스.를 대신하여 서명함. 93–148. doi:10.1017/CBO9781139058230.005.아이 에스비엔 9781139058230.
  41. ^ 스틸웰 1997, 31-32페이지
  42. ^ 르준 디리클레 1894, 29-31페이지
  43. ^ Lejeune Dirichlet 1894의 Richard Dedekind, 부록 11
  44. ^ 스틸웰 2003, 페이지 41~42
  45. ^ Sturm, C. (1829). "Mémoire sur la résolution des équations numériques". Bull. Des sciences de Férussac (in French). 11: 419–422.
  46. ^ Weisstein, Eric W. "Integer Relation". MathWorld.
  47. ^ Peterson, I. (12 August 2002). "Jazzing Up Euclid's Algorithm". ScienceNews.
  48. ^ Cipra, Barry Arthur (16 May 2000). "The Best of the 20th Century: Editors Name Top 10 Algorithms" (PDF). SIAM News. Society for Industrial and Applied Mathematics. 33 (4). Archived from the original (PDF) on 22 September 2016. Retrieved 19 July 2016.
  49. ^ Cole, A. J.; Davie, A. J. T. (1969). "A game based on the Euclidean algorithm and a winning strategy for it". Math. Gaz. 53 (386): 354–357. doi:10.2307/3612461. JSTOR 3612461. S2CID 125164797.
  50. ^ Spitznagel, E. L. (1973). "Properties of a game based on Euclid's algorithm". Math. Mag. 46 (2): 87–92. doi:10.2307/2689037. JSTOR 2689037.
  51. ^ 로젠 2000, 95페이지
  52. ^ Roberts, J. (1977). Elementary Number Theory: A Problem Oriented Approach. Cambridge, MA: MIT Press. pp. 1–8. ISBN 0-262-68028-9.
  53. ^ Jones, G. A.; Jones, J. M. (1998). "Bezout's Identity". Elementary Number Theory. New York: Springer-Verlag. pp. 7–11.
  54. ^ 로젠 2000, 페이지 81
  55. ^ 콘 1962, 페이지 104
  56. ^ 로젠 2000, 페이지 91
  57. ^ 슈뢰더 2005, 페이지 23
  58. ^ 로젠 2000, 90-93페이지
  59. ^ a b Koshy, T. (2002). Elementary Number Theory with Applications. Burlington, MA: Harcourt/Academic Press. pp. 167–169. ISBN 0-12-421171-2.
  60. ^ Bach, E.; Shallit, J. (1996). Algorithmic number theory. Cambridge, MA: MIT Press. pp. 70–73. ISBN 0-262-02405-5.
  61. ^ 스타크 1978, 26~36페이지
  62. ^ a b 광석 1948, 페이지 44
  63. ^ 스타크 1978, 281~292페이지
  64. ^ 로젠 2000, 119-125페이지
  65. ^ 슈뢰더 2005, 106~107페이지
  66. ^ 슈뢰더 2005, 108~109페이지
  67. ^ 로젠 2000, 120~121페이지
  68. ^ 스타크 1978, 페이지 47
  69. ^ 슈뢰더 2005, 107~109페이지
  70. ^ 스틸웰 1997, 186-187페이지
  71. ^ 슈뢰더 2005, 페이지 134
  72. ^ Moon, T. K. (2005). Error Correction Coding: Mathematical Methods and Algorithms. John Wiley and Sons. p. 266. ISBN 0-471-64800-0.
  73. ^ 로젠 2000, 143-170페이지
  74. ^ 슈뢰더 2005, 194-195페이지
  75. ^ Graham, R.; Knuth, D. E.; Patashnik, O. (1989). Concrete mathematics. Addison-Wesley. p. 123.
  76. ^ Vinogradov, I. M. (1954). Elements of Number Theory. New York: Dover. pp. 3–13.
  77. ^ Crandall & Pomerance 2001, 페이지 225 – 349
  78. ^ Knuth 1997, 369-371페이지
  79. ^ Shor, P. W. (1997). "Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer". SIAM Journal on Scientific and Statistical Computing. 26 (5): 1484–1509. arXiv:quant-ph/9508027. Bibcode:1995quant.ph..8027S. doi:10.1137/s0097539795293172. S2CID 2337707.
  80. ^ Dixon, J. D. (1981). "Asymptotically fast factorization of integers". Math. Comput. 36 (153): 255–260. doi:10.2307/2007743. JSTOR 2007743.
  81. ^ Lenstra, H. W., Jr. (1987). "Factoring integers with elliptic curves". Annals of Mathematics. 126 (3): 649–673. doi:10.2307/1971363. hdl:1887/2140. JSTOR 1971363.
  82. ^ Knuth 1997, 380-384페이지
  83. ^ Knuth 1997, 339-364페이지
  84. ^ Reynaud, A.-A.-L. (1811). Traité d'arithmétique à l'usage des élèves qui se destinent à l'École Polytechnique (6th ed.). Paris: Courcier. Note 60, p. 34. Shallit(1994)가 인용한 바와 같이.
  85. ^ Finck, P.-J.-E. (1841). Traité élémentaire d'arithmétique à l'usage des candidats aux écoles spéciales (in French). Derivaux.
  86. ^ a b Shallit, J. (1994). "Origins of the analysis of the Euclidean algorithm". Historia Math. 21 (4): 401–419. doi:10.1006/hmat.1994.1031.
  87. ^ Lamé, G. (1844). "Note sur la limite du nombre des divisions dans la recherche du plus grand commun diviseur entre deux nombres entiers". Comptes Rendus Acad. Sci. (in French). 19: 867–870.
  88. ^ Grossman, H. (1924). "On the Number of Divisions in Finding a G.C.D". The American Mathematical Monthly. 31 (9): 443. doi:10.2307/2298146. JSTOR 2298146.
  89. ^ Honsberger, R. (1976). Mathematical Gems II. The Mathematical Association of America. pp. 54–57. ISBN 0-88385-302-7.
  90. ^ a b Knuth 1997, 257-261페이지
  91. ^ a b c Crandall & Pomerance 2001, 77-79페이지, 81-85, 425-431
  92. ^ a b Möller, N. (2008). "On Schönhage's algorithm and subquadratic integer gcd computation" (PDF). Mathematics of Computation. 77 (261): 589–607. Bibcode:2008MaCom..77..589M. doi:10.1090/S0025-5718-07-02017-0.
  93. ^ a b c Knuth 1997, 344페이지
  94. ^ 광석 1948, 페이지 45
  95. ^ a b Knuth 1997, 343페이지
  96. ^ 몰린 2008, 페이지 21
  97. ^ 르베크 1996, 페이지 35
  98. ^ 몰린 2008, 21~22페이지
  99. ^ Knuth 1997, 353페이지
  100. ^ Knuth 1997, 357페이지
  101. ^ Tonkov, T. (1974). "On the average length of finite continued fractions". Acta Arithmetica. 26: 47–57. doi:10.4064/aa-26-1-47-57.
  102. ^ Weisstein, Eric W. "Porter's Constant". MathWorld.
  103. ^ Porter, J. W. (1975). "On a Theorem of Heilbronn". Mathematika. 22: 20–28. doi:10.1112/S0025579300004459.
  104. ^ Knuth, D. E. (1976). "Evaluation of Porter's Constant". Computers and Mathematics with Applications. 2 (2): 137–139. doi:10.1016/0898-1221(76)90025-0.
  105. ^ Dixon, J. D. (1970). "The Number of Steps in the Euclidean Algorithm". J. Number Theory. 2 (4): 414–422. Bibcode:1970JNT.....2..414D. doi:10.1016/0022-314X(70)90044-2.
  106. ^ Heilbronn, H. A. (1969). "On the Average Length of a Class of Finite Continued Fractions". In Paul Turán (ed.). Number Theory and Analysis. New York: Plenum. pp. 87–96. LCCN 76016027.
  107. ^ Knuth 1997, 354페이지
  108. ^ a b Norton, G. H. (1990). "On the Asymptotic Analysis of the Euclidean Algorithm". Journal of Symbolic Computation. 10: 53–58. doi:10.1016/S0747-7171(08)80036-3.
  109. ^ Knuth 1997, 355페이지
  110. ^ Knuth 1997, 356페이지
  111. ^ Knuth 1997, 352페이지
  112. ^ Wagon, S. (1999). Mathematica in Action. New York: Springer-Verlag. pp. 335–336. ISBN 0-387-98252-3.
  113. ^ 코헨 1993, 페이지 14
  114. ^ 코헨 1993, 페이지 14~15, 17~18
  115. ^ Sorenson, Jonathan P. (2004). "An analysis of the generalized binary GCD algorithm". High primes and misdemeanours: lectures in honour of the 60th birthday of Hugh Cowie Williams. Fields Institute Communications. Vol. 41. Providence, RI: American Mathematical Society. pp. 327–340. ISBN 9780821887592. MR 2076257. The algorithms that are used the most in practice today [for computing greatest common divisors] are probably the binary algorithm and Euclid's algorithm for smaller numbers, and either Lehmer's algorithm or Lebealean's version of the k-ary GCD algorithm for larger numbers.
  116. ^ Knuth 1997, 321–323페이지
  117. ^ Stein, J. (1967). "Computational problems associated with Racah algebra". Journal of Computational Physics. 1 (3): 397–405. Bibcode:1967JCoPh...1..397S. doi:10.1016/0021-9991(67)90047-2.
  118. ^ Knuth 1997, 328페이지
  119. ^ Lehmer, D. H. (1938). "Euclid's Algorithm for Large Numbers". The American Mathematical Monthly. 45 (4): 227–233. doi:10.2307/2302607. JSTOR 2302607.
  120. ^ Sorenson, J. (1994). "Two fast GCD algorithms". J. Algorithms. 16: 110–144. doi:10.1006/jagm.1994.1006.
  121. ^ Weber, K. (1995). "The accelerated GCD algorithm". ACM Trans. Math. Softw. 21: 111–122. doi:10.1145/200979.201042. S2CID 14934919.
  122. ^ Aho, A.; Hopcroft, J.; Ullman, J. (1974). The Design and Analysis of Computer Algorithms. New York: Addison–Wesley. pp. 300–310. ISBN 0-201-00029-6.
  123. ^ Schönhage, A. (1971). "Schnelle Berechnung von Kettenbruchentwicklungen". Acta Informatica (in German). 1 (2): 139–144. doi:10.1007/BF00289520. S2CID 34561609.
  124. ^ Cesari, G. (1998). "Parallel implementation of Schönhage's integer GCD algorithm". In G. Buhler (ed.). Algorithmic Number Theory: Proc. ANTS-III, Portland, OR. Lecture Notes in Computer Science. Vol. 1423. New York: Springer-Verlag. pp. 64–76.
  125. ^ Stehlé, D.; Zimmermann, P. (2005). "Gal's accurate tables method revisited". Proceedings of the 17th IEEE Symposium on Computer Arithmetic (ARITH-17). Los Alamitos, CA: IEEE Computer Society Press.
  126. ^ a b c Lang, S. (1984). Algebra (2nd ed.). Menlo Park, CA: Addison–Wesley. pp. 190–194. ISBN 0-201-05487-6.
  127. ^ a b Weinberger, P. (1973). "On Euclidean rings of algebraic integers". Proc. Sympos. Pure Math. Proceedings of Symposia in Pure Mathematics. 24: 321–332. doi:10.1090/pspum/024/0337902. ISBN 9780821814246.
  128. ^ a b c 스틸웰 2003, 페이지 151~152
  129. ^ Boyer, C. B.; Merzbach, U. C. (1991). A History of Mathematics (2nd ed.). New York: Wiley. pp. 116–117. ISBN 0-471-54397-7.
  130. ^ Cajori, F (1894). A History of Mathematics. New York: Macmillan. p. 70. ISBN 0-486-43874-0.
  131. ^ Joux, Antoine (2009). Algorithmic Cryptanalysis. CRC Press. p. 33. ISBN 9781420070033.
  132. ^ Fuks, D. B.; Tabachnikov, Serge (2007). Mathematical Omnibus: Thirty Lectures on Classic Mathematics. American Mathematical Society. p. 13. ISBN 9780821843161.
  133. ^ Darling, David (2004). "Khintchine's constant". The Universal Book of Mathematics: From Abracadabra to Zeno's Paradoxes. John Wiley & Sons. p. 175. ISBN 9780471667001.
  134. ^ Williams, Colin P. (2010). Explorations in Quantum Computing. Springer. pp. 277–278. ISBN 9781846288876.
  135. ^ Cox, Little & O'Shea 1997, 37-46 페이지
  136. ^ 슈뢰더 2005, 페이지 254~259
  137. ^ Grattan-Guinness, Ivor (1990). Convolutions in French Mathematics, 1800-1840: From the Calculus and Mechanics to Mathematical Analysis and Mathematical Physics. Volume II: The Turns. Science Networks: Historical Studies. Vol. 3. Basel, Boston, Berlin: Birkhäuser. p. 1148. ISBN 9783764322380. Our subject here is the 'Sturm sequence' of functions defined from a function and its derivative by means of Euclid's algorithm, in order to calculate the number of real roots of a polynomial within a given interval
  138. ^ Hairer, Ernst; Nørsett, Syvert P.; Wanner, Gerhard (1993). "The Routh–Hurwitz Criterion". Solving Ordinary Differential Equations I: Nonstiff Problems. Springer Series in Computational Mathematics. Vol. 8 (2nd ed.). Springer. pp. 81ff. ISBN 9783540566700.
  139. ^ a b c 스틸웰 2003, 101-116페이지
  140. ^ a b c Hensley, Doug (2006). Continued Fractions. World Scientific. p. 26. ISBN 9789812564771.
  141. ^ Dedekind, Richard (1996). Theory of Algebraic Integers. Cambridge Mathematical Library. Cambridge University Press. pp. 22–24. ISBN 9780521565189.
  142. ^ Johnston, Bernard L.; Richman, Fred (1997). Numbers and Symmetry: An Introduction to Algebra. CRC Press. p. 44. ISBN 9780849303012.
  143. ^ Adams, William W.; Goldstein, Larry Joel (1976). Introduction to Number Theory. Prentice-Hall. Exercise 24, p. 205. ISBN 9780134912820. State and prove an analogue of the Chinese remainder theorem for the Gaussian integers.
  144. ^ 스타크 1978, 페이지 290
  145. ^ 콘 1962, 104~105페이지
  146. ^ Lauritzen, Niels (2003). Concrete Abstract Algebra: From Numbers to Gröbner Bases. Cambridge University Press. p. 130. ISBN 9780521534109.
  147. ^ 로리첸 (2003), 페이지 132
  148. ^ 로리첸 (2003), 페이지 161
  149. ^ a b Sharpe, David (1987). Rings and Factorization. Cambridge University Press. p. 55. ISBN 9780521337182.
  150. ^ 샤프(1987), 페이지 52
  151. ^ 로리첸 (2003), 페이지 131
  152. ^ Lamé, G. (1847). "Mémoire sur la résolution, en nombres complexes, de l'équation An + Bn + Cn = 0". J. Math. Pures Appl. (in French). 12: 172–184.
  153. ^ Edwards, H. (2000). Fermat's last theorem: a genetic introduction to algebraic number theory. Springer. p. 76.
  154. ^ 콘 1962, 페이지 104~110
  155. ^ LeVeque, W. J. (2002) [1956]. Topics in Number Theory, Volumes I and II. New York: Dover Publications. pp. II:57, 81. ISBN 978-0-486-42539-9. Zbl 1009.11001.
  156. ^ a b Clark, D. A. (1994). "A quadratic field which is Euclidean but not norm-Euclidean". Manuscripta Mathematica. 83: 327–330. doi:10.1007/BF02567617. S2CID 895185. Zbl 0817.11047.
  157. ^ a b Davidoff, Giuliana; Sarnak, Peter; Valette, Alain (2003). "2.6 The Arithmetic of Integer Quaternions". Elementary Number Theory, Group Theory and Ramanujan Graphs. London Mathematical Society Student Texts. Vol. 55. Cambridge University Press. pp. 59–70. ISBN 9780521531436.
  158. ^ Ribenboim, Paulo (2001). Classical Theory of Algebraic Numbers. Universitext. Springer-Verlag. p. 104. ISBN 9780387950709.

참고 문헌

외부 링크