Jump to content

Euclidean algorithm

This is a fully translated article. Click here for more information.
From DawoumWiki, the free Mathematics self-learning
Original article: w:Euclidean algorithm
This article is about an algorithm for the greatest common divisor. For the mathematics of space, see Euclidean geometry. For other uses of "Euclidean", see Euclidean (disambiguation).
Euclid's method for finding the greatest common divisor (GCD) of two starting lengths BA and DC, both defined to be multiples of a common "unit" length. The length DC being shorter, it is used to "measure" BA, but only once because remainder EA is less than DC. EA now measures (twice) the shorter length DC, with remainder FC shorter than EA. Then FC measures (three times) length EA. Because there is no remainder, the process ends with FC being the GCD. On the right Nicomachus's example with numbers 49 and 21 resulting in their GCD of 7 (derived from Heath 1908:300).

수학(mathematics)에서, 유클리드 알고리듬(Euclidean algorithm,[note 1] 또는 Euclid's algorithm)은 두 정수 (숫자)의 최대 공통 약수(greatest common divisor) (GCD)를 계산하는 효율적인 방법으로, 나머지(remainder)없이 둘을 나누는 가장 큰 숫자입니다. 그것은 고대 그리스의 수학자(mathematician) 유클리드(Euclid)의 이름을 따서 지어졌으며, 그는 처음으로 그의 원론(Elements) (기원전 c. 300)에서 그것을 묘사했습니다. 그것은 알고리듬(algorithm), 잘-정의된 규칙에 따라 계산을 수행하는 단계별 절차의 예제이고, 공통적인 사용에서 가장-오래된 알고리듬 중 하나입니다. 그것은 분수(fraction)를 가장-간단한 형식(simplest form)으로 줄이는 데 사용할 수 있고, 많은 다른 숫자-이론적 및 암호화 계산의 일부입니다.

유클리드 알고리듬은, 두 숫자의 최대 공통 약수가, 만약 큰 숫자가 작은 숫자와의 차이로 대체되면, 변하지 않는다는 원리를 기반으로 합니다. 예를 들어, 21은 252와 105의 GCD (252 = 21 × 12 및 105 = 21 × 5)이고, 같은 숫자 21은 105와 252 − 105 = 147의 역시 GCD입니다. 이 대체는 더 큰 두 숫자를 줄이기 때문에, 이 과정을 반복하면 두 숫자가 같게 될 때까지 더 작은 숫자 쌍을 연속적으로 제공합니다. 이것이 발생할 때, 그들은 원래 두 숫자의 GCD입니다. 그 단계를 반대로 함으로써 또는 확장된 유클리드 알고리듬(extended Euclidean algorithm)을 사용함으로써, GCD는 두 개의 원래 숫자의 선형 조합(linear combination), 즉 두 숫자의 합에 각각 정수(integer)를 곱한 값으로 표현될 수 있습니다 (예를 들어, 21 = 5 × 105 + (−2) × 252.). GCD가 항상 이런 방법으로 표현될 수 있다는 사실은 베주의 항등식(Bézout's identity)으로 알려져 있습니다.

위에서 설명된 유클리드 알고리듬의 버전은, 주어진 숫자 중 하나가 다른 숫자보다 훨씬 더 클 때, GCD를 찾기 위해 많은 뺄셈 단계를 수행할 수 있습니다. 보다 효율적인 알고리듬의 버전은, 두 숫자 중 큰 숫자를 두 숫자 중 작은 것으로 나눈 나머지로 대체함으로써 이들 단계를 짧게 만듭니다 (이 버전과 함께, 알고리듬은 영 나머지에 도달할 때 멈춥니다). 이 개선으로, 알고리듬은 더 작은 정수의 (밑수 10) 자릿수의 5배보다 더 많은 단계를 절대 요구하지 않습니다. 이것은 1844년에 개브리엘 라미(Gabriel Lamé)에 의해 입증되었고, 계산 복잡도 이론(computational complexity theory)의 시작을 만듭니다. 알고리듬의 효율성을 향상시키기 위한 추가적인 방법은 20세기에 개발되었습니다.

유클리드 알고리듬은 많은 이론적이고 실용적인 응용을 가집니다. 그것은 분수(fraction)를 가장-단순한 형식으로 줄이는 것에 사용되고 모듈러 산술(modular arithmetic)에서 나눗셈(division)을 수행하는 것에 사용됩니다. 이 알고리듬을 사용하는 계산은 인터넷(internet) 통신을 안전하게 하기 위해 사용되는 암호학적 프로토콜(cryptographic protocol)의 일부를 형성하고, 큰 복합 숫자를 인수화함으로써 이들 암호화-시스템을 파괴하는 방법에 사용됩니다. 유클리드 알고리듬은, 중국 나머지 정리(Chinese remainder theorem)에 따라 여러 적합성을 만족시키는 숫자를 찾는 것과 같은, 디오판토스 방정식(Diophantine equation)을 푸는 것 및 연속 분수(continued fraction)를 구성하는 것, 및 실수에 대한 정확한 유리 근사(rational approximations)를 찾는 것에 사용될 수 있습니다. 마지막으로, 그것은 라그랑주 네-제곱 정리(Lagrange's four-square theorem)와 소수 인수분해의 고유성(uniqueness of prime factorizations)과 같은 숫자 이론(number theory)에서 이론을 증명하기 위한 기본 도구로 사용될 수 있습니다. 원래 알고리듬은 자연수와 기하학적 길이 (실수)에 대해 오직 설명되었지만, 그 알고리듬은 가우스 정수(Gaussian integer) 및 한 변수의 다항식(polynomial)과 같은 다른 숫자의 유형으로 일반화되었습니다. 이것은 유클리드 도메인(Euclidean domain)과 같은 현대 추상 대수(abstract algebra)적 개념으로 이어졌습니다.

Background: greatest common divisor

Main article: Greatest common divisor

유클리드 알고리듬은 두 자연수(natural number) a와 b의 최대 공통 약수 (GCD)를 계산합니다. 최대 공통 약수 g는 나머지 남김없이 a와 b 둘 다를 나누는 가장 큰 자연수입니다. GCD에 대해 동의어는 최대 공통 인수 (greatest common factor, 줄여서 GCF), 최고 공통 계수 (highest common factor, 줄여서 HCF), 최고 공통 인수 (highest common divisor, 줄여서 HCD), 및 최대 공통 측정 (greatest common measure, 줄여서 GCM)를 포함합니다. 최대 공통 약수는 종종 gcd(a, b), 또는 보다 간단히, (a, b)로 쓰이지만,[1] 후자 표기법은 모호한데, GCD와 밀접하게 관련된 정수의 링(ring of integers)에서 아이디얼(ideal)과 같은 개념에 대해 역시 사용됩니다.

만약 gcd(a, b) = 1이면, a와 b는 서로소(coprime) (또는 상대적으로 소수)라고 말합니다.[2] 이 속성은 a 또는 b가 자체로 소수(prime number)임을 의미하지는 않습니다.[3] 예를 들어, 6과 35는 둘 다 소수가 아닌데, 왜냐하면 두 소수 인수를 갖기 때문입니다: 6 = 2 × 3 and 35 = 5 × 7. 그럼에도 불구하고, 6과 35는 서로소입니다. 1 이외의 자연수는 6과 35를 나누지 않는데, 왜냐하면 그들은 공통으로 소수 인수를 가지지 않기 때문입니다.

"Tall, slender rectangle divided into a grid of squares. The rectangle is two squares wide and five squares tall."
A 24-by-60 rectangle is covered with ten 12-by-12 square tiles, where 12 is the GCD of 24 and 60. More generally, an a-by-b rectangle can be covered with square tiles of side-length c only if c is a common divisor of a and b.

g = gcd(a, b)라고 놓습니다. a와 b는 둘 다 g의 배수이므로, 그들은 a = mg와 b = ng라고 쓸 수 있고, 이것이 참인 것에 대해 더 큰 숫자 G > g는 없습니다. 자연수 m과 n은 서로소여야 하는데, 왜냐하면 임의의 공통 인수는 g를 더 크게 만들기 위해 m과 n의 인수로 묶을 수 있기 때문입니다. 따라서, a와 b 둘 다를 나누는 임의의 다른 숫자 c는 역시 g를 나누어야 합니다. a와 b의 최대 공통 약수 g는 임의의 다른 공통 약수 c로 나누어질 수 있는 a와 b의 고유한 (양수) 공통 약수입니다. [4]

GCD는 다음과 같이 시각화될 수 있습니다.[5] 직사각형 넓이 a 곱하기 b, 및 a와 b 둘 다를 정확하게 나누는 공통 약수 c를 생각해 보십시오. 직사각형의 변은 길이 c의 선분으로 분할될 수 있으며, 이것은 직사각형을 변의 길이 c의 정사각형의 격자로 나눕니다. 최대 공통 약수 g는 이것이 가능한 것에 대해 c의 최댓값입니다. 그림에 대해, 24-곱하기-60 사각형 넓이는 1-곱하기-1 정사각형, 2-곱하기-2 정사각형, 3-곱하기-3 정사각형, 4-곱하기-4 정사각형, 6-곱하기-6 정사각형 또는 12-곱하기-12 정사각형의 격자로 나누어질 수 있습니다. 그러므로, 12는 24와 60의 최대 공통 약수입니다. 24-곱하기-60 직사각형 넓이는 12-곱하기-12 정사각형의 격자로 나누어질 수 있으며, 한쪽 가장자리를 따라 두 정사각형 (24/12 = 2)과 다른 가장자리를 따라 다섯 정사각형 (60/12 = 5)을 가집니다.

두 숫자 a와 b의 GCD는 두 숫자에 의해 공유된 소수 인수의 곱이며, 여기서 같은 소수 인수는 여러 번 사용될 수 있지만, 이들 인수의 곱이 a와 b 둘 다를 나누는 한에서만 가능합니다.[6] 예를 들어, 1386은 2 × 3 × 3 × 7 × 11로 인수화될 수 있고, 3213은 3 × 3 × 3 × 7 × 17로 인수화될 수 있으므로, 1386과 3213의 최대 공통 약수는 63 = 3 × 3 × 7, 소수 인수가 공유된 그들의 곱과 같습니다. 만약 두 숫자가 공통으로 소수 인수를 가지지 않으면, 그들의 최대 공통 약수는 1이며 (여기서 빈 곱(empty product)의 예제로 얻음), 달리 말해서 그들은 서로소입니다. 유클리드 알고리듬의 주요 장점은 소수 인수를 계산하는 것없이 효과적으로 GCD를 찾을 수 있다는 것입니다.[7][8] 큰 정수의 인수분해(Factorization)는 계산적으로 매우 어려운 문제로 믿어지고, 널리 사용되는 많은 암호화 프로토콜(cryptographic protocol)의 보안은 그것의 타당성을 기반으로 합니다.[9]

GCD의 또 다른 정의는 고급 수학, 특히 링 이론(ring theory)에서 도움이 됩니다.[10] 두 비-영 숫자 a와 b의 최대 공통 약수 g는 그들의 가장 작은 양의 정수 선형 조합, 즉, 형시 ua + vb의 가장 작은 양수이며, 여기서 u와 v는 정수입니다. a와 b의 모든 정수 선형 조합의 집합은 실제로 g의 모든 배수의 집합과 동일합니다 (mg, 여기서 m은 정수입니다). 현대의 수학적 언어에서, a와 b에 의해 생성된 아이디얼(ideal)은 g 단독으로 생성된 아이디얼입니다 (단일 원소에 의해 생성된 아이디얼은 주요 아이디얼(principal ideal)이라고 불리고, 정수의 모든 아이디얼은 주요 아이디얼입니다). GCD의 일부 속성은, 예를 들어 a와 b의 임의의 공통 약수가 GCD를 역시 나눈다는 사실 (ua + vb의 두 항을 나눈 것)과 같은, 실제로 이 설명으로 이해하는 것이 더 쉽습니다. 이 GCD 정의와 다른 정의의 동등성은 아래에 설명됩니다.

셋 이상의 숫자의 GCD는 모든 숫자에 공통적인 소수 인수의 곱과 같지만,[11] 숫자 쌍의 GCD를 반복적으로 취함으로써 역시 계산될 수 있습니다.[12] 예를 들어

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

따라서, 두 정수의 GCD를 계산하는, 유클리드의 알고리듬은 임의적으로 많은 정수의 GCD를 계산하기에 충분합니다.

Description

Procedure

유클리드 알고리듬은 각 단계의 출력이 다음 단계에 대해 입력으로 사용되도록 일련의 단계로 진행됩니다. k를 0으로 시작하는 알고리듬의 단계를 세는 정수라고 놓습니다. 따라서, 초기 단계는 k = 0에 해당하고, 다음 단계는 k = 1에 해당하며, 이런 식으로 진행됩니다.

각 단계는 비-음 나머지 rk−1과 rk−2와 함께 시작합니다. 알고리듬은 나머지가 모든 단계에서 꾸준히 감소하는 것임을 보장하므로, rk−1은 이전-나머지 rk−2보다 작습니다. k번째 단계의 목표는 다음 방정식을 만족시키는 몫(quotient) qk와 나머지(remainder) rk를 찾는 것는 것입니다:

그리고 여기서 0 ≤ rk < rk−1를 가집니다. 달리 말해서, 나머지 rk가 rk−1보다 작을 때까지, 더 작은 숫자 rk−1의 배수는 더 큰 숫자 rk−2에서 빼집니다.

초기 단계 (k = 0)에서, 나머지 r−2와 r−1는 a와 b, GCD를 찾으려는 숫자와 같습니다. 다음 단계 (k = 1)에서, 나머지는 초기 단계의 b와 나머지 r0와 같으며, 이런 식으로 진행합니다. 따라서, 알고리듬은 일련의 다음 방정식으로 쓸 수 있습니다:

만약 a가 b보다 작으면, 알고리듬의 첫 번째 단계에서 숫자를 서로 바꿉니다. 예를 들어, 만약 a < b이면, 초기 몫 q0는 0이고, 나머지 r0는 a입니다. 따라서, rk는 모든 k ≥ 0에 대해 이전-나머지 rk−1보다 작습니다.

나머지는 모든 각 단계마다 감소하지만 음수가 될 수는 없으므로, 나머지 rN은 결국 0과 같아야 하며, 이 시점에서 알고리듬이 중지됩니다.[13] 마지막 비-영 나머지 rN−1은 a와 b의 최대 공통 약수입니다. 숫자 N은 무한대는 절대 아닌데 왜냐하면 초기 나머지 r0와 0 사이에 단지 비-음 정수의 유한 숫자이기 때문입니다.

Proof of validity

유클리드 알고리듬의 타당성은 2-단계 논증으로 입증될 수 있습니다.[14] 첫 번째 단계에서, 마지막 비-영 나머지 rN−1은 a와 b 둘 다를 나누는 것으로 표시됩니다. 그것은 공통 약수이므로, 최대 공통 약수 g보다 작거나 같아야 합니다. 두 번째 단계에서, g를 포함한, a와 b의 임의의 공통 약수가 rN−1을 나누어야 함을 보여줍니다; 그러므로, g는 rN−1보다 작거나 같아야 합니다. 이들 두 결론은 rN−1 = g가 아니면 불일치입니다.

rN−1이 a와 b 둘 다를 나눈다는 것을 시연하기 위해 (첫 번째 단계), rN−1은 이전-나머지 rN−2를 나눕니다:

rN−2 = qN rN−1

왜냐하면 마지막 나머지 rN는 영이기 때문입니다. rN−1은 역시 그것의 다음 이전-나머지 rN−3를 역시 나눕니다:

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

왜냐하면 그것이 방정식의 오른쪽 변에 두 항을 나누기 때문입니다. 같은 논증을 반복하면, rN−1은 a와 b를 포함하여 모든 이전의 나머지를 나눕니다. 선행 나머지 rN−2, rN−3, 등의 어떤 것도 a와 b를 나누지 않는데, 왜냐하면 그들은 나머지를 남기기 때문입니다. rN−1은 a와 b의 공통 약수이므로, rN−1 ≤ g입니다.


두 번째 단계에서, a와 b 둘 다를 나누는 임의의 자연수 c (달리 말해서, a와 b의 임의의 공통 약수)는 나머지 rk를 나눕니다. 정의에 의해, a와 b는 c의 배수로 쓸 수 있습니다: a = mc 및 b = nc, 여기서 m과 n은 자연수입니다. 그러므로, c는 초기 나머지 r0를 나누는데, 왜냐하면 r0 = a − q0b = mc − q0nc = (m − q0n)c이기 때문입니다. 유사한 논증은 c가 후속 나머지 r1, r2, 등을 역시 나눈다는 것을 보여줍니다. 그러므로, 최대 공통 약수 g는 rN−1를 나누어야 하며, 이것은 g ≤ rN−1임을 의미합니다. 논증의 첫 번째 부분은 반대 (rN−1 ≤ g)를 나타내므로, g = rN−1임을 따릅니다. 따라서, g는 모든 후속 쌍의 최대 공통 약수입니다:[15][16]

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

Worked example

Animation in which progressively smaller square tiles are added to cover a rectangle completely.
Subtraction-based animation of the Euclidean algorithm. The initial rectangle has dimensions a = 1071 and b = 462. Squares of size 462×462 are placed within it leaving a 462×147 rectangle. This rectangle is tiled with 147×147 squares until a 21×147 rectangle is left, which in turn is tiled with 21×21 squares, leaving no uncovered area. The smallest square size, 21, is the GCD of 1071 and 462.

예를 들어, 유클리드 알고리듬은 a = 1071와 b = 462의 최대 공통 약수를 찾기 위해 사용될 수 있습니다. 시작하기 위해, 나머지가 462보다 작아질 때까지 462의 배수가 1071에서 빼집니다. 두 그러한 배수가 빼질 수 있으며 (q0 = 2), 147의 나머지를 남깁니다:

1071 = 2 × 462 + 147.

그런-다음 나머지가 147보다 작아질 때까지 147의 배수가 462에서 빼집니다. 세 배수가 빼질 수 있으며 (q1 = 3), 21의 나머지를 남깁니다:

462 = 3 × 147 + 21.

그런-다음 나머지가 21보다 작아질 때까지 21의 배수가 147에서 빼집니다. 일곱 배수가 빼질 수 있으며 (q2 = 7), 나머지를 남기지 않습니다:

147 = 7 × 21 + 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; 알고리듬이 끝납니다.

Visualization

유클리드 알고리듬은 최대 공통 약수에 대해 위에 주어진 타일링 비유로 시각화될 수 있습니다.[17] 우리는 a×b 직사각형을 정확히 정사각형 타일들로 덮고 싶다고 가정하며, 여기서 a는 두 숫자 중 더 큰 숫자입니다. 우리는 먼저 b×b 정사각형 타일을 사용하여 직사각형 타일을 시도합니다; 어쨌든, 이것은 타일되지 않은 r0-×-b 남은 직사각형을 남기며, 여기서 r0 < b입니다. 우리는 그런-다음 남은 직사각형을 r0-×-r0 정사각형 타일로 타일링을 시도합니다. 이것은 두 번째 남은 직사각형 r1-×-r0을 남기며, 우리가 이것을 r1-×-r1 정사각형 타일을 사용하여 타일링을 시도하고, 이것이 계속됩니다. 순서는 남은 직사각형이 없을 때, 즉 정사각형 타일이 이전 남은 직사각형을 정확히 덮을 때 끝납니다. 가장 작은 정사각형 타일의 변의 길이는 원래 직사각형 크기의 GCD입니다. 예를 들어, 인접한 그림에서 가장 작은 정사각형 타일은 21×21 (빨간색으로 표시)이고, 21은 1071과 462, 원래 직사각형의 넓이 (녹색으로 표시)의 GCD입니다.

Euclidean division

Main article: Euclidean division

모든 각 단계 k에서, 유클리드 알고리듬은 두 숫자 rk−1와 rk−2로부터 몫 qk와 나머지 rk를 계산합니다:

rk−2 = qk rk−1 + rk

여기서 rk는 비-음수이고 rk−1의 절댓값(absolute value)보다 엄격하게 작습니다. 유클리드 나눗셈(Euclidean division)의 정의를 뒷받침하는 정리는 그러한 몫과 나머지가 항상 존재하고 고유하다는 것을 보장합니다.[18]

유클리드의 원래 버전의 알고리듬에서, 몫과 나머지는 반복된 뺄셈에 의해 구해집니다; 즉, 나머지 rk가 rk−1보다 작아질 때까지 rk−1는 rk−2에서 반복적으로 빼집니다. 그 후 rk와 rk−1이 교환되고 과정이 반복됩니다. 유클리드 나눗셈은 두 교환 사이의 모든 단계를 단 하나의 단계로 줄이며, 따라서 보다 효율적입니다. 게다가, 몫은 필요하지 않으며, 따라서 우리는 유클리드 나눗셈을 모듈로 연산(modulo operation)으로 대체할 수 있으며, 이것은 오직 나머지를 제공합니다. 따라서 유클리드 알고리듬의 반복은 다음처럼 간단히 됩니다:

rk = rk−2 mod rk−1.

Implementations

알고리듬의 구현은 유사-코드(pseudocode)로 표현될 수 있습니다. 예를 들어, 나눗셈-기반 버전은 다음과 같이 프로그래밍(programming)될 수 있습니다:[19] 

function gcd(a, b)
    while b ≠ 0
        t := b
        b := a mod b
        a := t
    return a

k번째 반복의 시작에서, 변수 b는 마지막 나머지 rk−1을 보유하지만, 변수 a는 그것의 이전 변수, rk−2를 보유합니다. 단계 b := a mod b는 위의 재귀 공식 rk ≡ rk−2 mod rk−1과 동등합니다. 임시 변수(temporary variable) t는 다음 나머지 rk가 계산되는 동안 rk−1의 값을 보유합니다. 루프 반복의 끝에서, 변수 b는 나머지 rk를 보유하지만, 변수 a는 그것의 이전 나머지, rk−1를 보유합니다.

유클리드의 원래 버전이었던 뺄셈-기반 버전에서, 나머지 계산 (b := a mod b)은 반복된 뻴셈에 의해 대체됩니다.[20] 임의의 정수를 입력으로 사용하는 나눗셈-기반 버전과 달리, 뺄셈-기반 버전은 입력이 양의 정수로 구성되고 a = b일 때 중지한다고 가정합니다: 

function gcd(a, b)
    while a ≠ b 
        if a > b
            a := a − b
        else
            b := b − a
    return a

변수 a와 b는 보유하는 이전 나머지 rk−1과 rk−2를 교대로 대체합니다. a는 반복의 시작에서 b보다 더 크다고 가정합니다; 그런-다음 a는 rk−2와 같은데, 왜냐하면 rk−2 > rk−1이기 때문입니다. 루프 반복 동안, a가 b보다 작을 때까지 a는 이전 나머지 b의 배수만큼 감소됩니다. 그런-다음 a는 다음 나머지 rk입니다. 그런 다음 b는 그것이 a보다 다시 작아질 때까지 a의 배수만큼 감소하여, 다음 나머지 rk+1을 제공하는데, 이런 식으로 계속됩니다.

재귀 버전은[21] 연속하는 나머지의 GCD의 상등과 중지하는 조건 gcd(rN−1, 0) = rN−1을 기반으로 합니다. 

function gcd(a, b)
    if b = 0
        return a
    else
        return gcd(b, a mod b)

설명을 위해, gcd(1071, 462)는 동등한 gcd(462, 1071 mod 462) = gcd(462, 147)에서 계산됩니다. 후자의 GCD는 gcd(147, 462 mod 147) = gcd(147, 21)에서 계산되며, 이것은 차례로 gcd(21, 147 mod 21) = gcd(21, 0) = 21에서 계산됩니다.

Method of least absolute remainders

유클리드 알고리듬의 또 다른 버전에서, 각 단계에서 몫은 만약 결과로 생성되는 음의 나머지가 전형적인 양의 나머지보다 크기에서 작으면 1씩 증가합니다.[22][23] 이전에는, 방정식

rk−2 = qk rk−1 + rk

은 |rk−1| > rk > 0임을 가정되었습니다. 어쨌든, 대안적인 음의 나머지 ek는 만약 rk−1 > 0이면 다음으로 계산될 수 있습니다:

rk−2 = (qk + 1) rk−1 + ek

또는 만약 rk−1 < 0이면, 다음으로 계산될 수 있습니다:

rk−2 = (qk − 1) rk−1 + ek.

만약 rk가 ek로 대체되면, |ek| < |rk|일 때, 우리는 각 단계에서 다음을 만족하는 유클리드 알고리듬의 변형을 얻습니다.

|rk| ≤ |rk−1| / 2.

레오폴트 크로네커(Leopold Kronecker)는 이 버전이 임의의 버전의 유클리드 알고리듬 중 가장 적은 단계를 요구한다는 것을 보여 왔습니다.[22][23] 보다 일반적으로, 모든 각 입력 숫자 a와 b에 대해, 단계의 숫자가 최소인 것과 qk가 순서에서 인 것으로 선택되는 것은 필요충분 조건임을 입증했으며, 여기서 는 황금 비율(golden ratio)입니다.[24]

Historical development

"Depiction of Euclid as a bearded man holding a pair of dividers to a tablet."
The Euclidean algorithm was probably invented before Euclid, depicted here holding a compass in a painting of about 1474.

유클리드 알고리듬은 공통적인 사용에서 가장 오래된 알고리듬 중 하나입니다.[25] 그것은 유클리드의 원론(Euclid's Elements) (기원전 c. 300), 특히 7권 (제안 1–2) 및 10권 (제안 2–3)에 나와 있습니다. 7권에서, 그 알고리듬이 정수에 대해 공식화되었지만, 10권에서, 그것은 선분의 길이에 대해 공식화되었습니다. (현대의 사용에서, 우리는 그곳에서 실수(real number)로 공식화되었다고 말할 수 있습니다. 그러나 현대의 사용에서 실수로 표현되는 길이, 넓이, 및 부피는 같은 단위로 측정되지 않고 길이, 넓이, 또는 부피의 자연스러운 단위가 없습니다; 실수의 개념은 그 당시에 알려지지 않았습니다.) 후자의 알고리듬은 기하학적입니다. 두 길이 a와 b의 GCD는 균등하게 a와 b를 측정하는 최대 길이 g에 해당합니다; 달리 말해서, 길이 a와 b는 둘 다 길이 g의 정수 배수입니다.

그 알고리듬은 아마도 유클리드(Euclid)에 의해 발견되지 않았을 것이며, 그는 원론에서 초기 수학자들의 결과를 수집했습니다.[26][27] 수학자이자 역사가 바르털 레인더르트 반 데르 바르던(B. L. van der Waerden)은 책 VII가 피타고라스(Pythagoras)의 학교에서 수학자들에 의해 쓰인 숫자 이론(number theory)에 대한 교과서에서 파생되었다고 제안합니다.[28] 그 알고리듬은 아마도 크니도스의 에우독소스(Eudoxus of Cnidus) (기원전 약 375)에 의해 알려졌을 것입니다.[25][29] 그 알고리듬은 심지어 에우독소스 이전-시대일 수 있으며,[30][31] 유클리드와 아리스토텔레스의 연구에서 기술 용어 ἀνθυφαίρεσις (anthyphairesis, 역수 뺄셈)의 사용으로부터 판단합니다.[32]

수세기 후, 유클리드의 알고리듬은 인도와 중국에서 둘 다 독립적으로 발견되었으며,[33] 주로 천문학에서 발생하는 디오판토스 방정식(Diophantine equations)을 풀고 정확한 달력을 만들기 위해 사용되었습니다. 5세기 후반에서, 인도의 수학자이자 천문학자 아리아바타(Aryabhata)는 그 알고리듬을 "분쇄기"라고 설명했으며,[34] 아마도 디오판토스 방정식을 푸는 데 효과가 있기 때문일 것입니다.[35] 비록 중국 나머지 정리(Chinese remainder theorem)의 특별한 경우가 이미 중국 책 Sunzi Suanjing에 설명되어 있지만,[36] 일반적인 해는 그의 1247 책 Shushu Jiuzhang (數書九章 Mathematical Treatise in Nine Sections)에서 진규소(Qin Jiushao)에 의해 발표했습니다.[37] 유클리드 알고리듬은 바셰의(Bachet's) Problèmes plaisants et délectables (Pleasant and enjoyable problems, 1624)의 두 번째 판에서 처음으로 수치적으로 설명되고 유럽에서 대중화되었습니다.[34] 유럽에서, 마찬가지로 디오판토스 방정식을 풀고 연속된 분수(continued fraction)를 개발하는 데 사용되었습니다. 확장된 유클리드 알고리듬(extended Euclidean algorithm)은 영국 수학자 니컬러스 손더슨(Nicholas Saunderson)에 의해 발표되었으며,[38] 그는 연속 분수를 효율적으로 계산하는 것에 대해 방법으로 로저 코츠(Roger Cotes)에 의해 그것이 발생한 것으로 여깁니다.[39]

19세기에서, 유클리드 알고리듬은 가우스 정수(Gaussian integer)와 아이젠슈타인 정수(Eisenstein integer)와 같은 새로운 숫자 시스템의 개발로 이어졌습니다. 1815년에서, 카를 가우스(Carl Gauss)는, 비록 그의 연구가 1832년에 처음 출판되었지만, 유클리드 알고리듬을 가우스 정수(Gaussian integer)의 고유한 인수-분해를 시연하기 위해 사용했습니다.[40] 가우스는 그의 Disquisitiones Arithmeticae (1801년 출판됨)에서 그 알고리듬을 언급했지만, 연속 분수(continued fraction)에 대해 오직 한 방법으로 사용되었습니다.[33] 페터 구스타프 르죈 디리클레(Peter Gustav Lejeune Dirichlet)는 많은 숫자 이론의 기초로 유클리드 알고리듬을 최초로 기술한 것으로 보입니다.[41] 르죈 디리클레는 고유한 인수분해와 같은 숫자 이론의 많은 결과가 유클리드 알고리듬이 적용될 수 있는 임의의 다른 숫자의 시스템에 대해 참을 유지함을 주목했습니다.[42] 숫자 이론에 대한 르죈 디리클레의 강의는 리하르트 데데킨트(Richard Dedekind)에 의해 편집되고 확장되었으며, 그는 유클리드의 알고리듬을 대수적 숫자(algebraic integer), 새로운 일반적인 유형의 숫자를 연구하기 위해 사용했습니다. 예를 들어, 데데킨트는 가우스 정수의 고유한 인수분해를 사용하여 페르마의 둘-제곱 정리를 최초로 입증했습니다.[43] 데데킨트는 유클리드 도메인(Euclidean domain), 유클리드 알고리듬의 일반화된 버전이 정의될 수 있는 숫자 시스템의 개념을 역시 정의했습니다 (아래 설명을 참조하십시오). 19세기의 마지막 수십 년 동안, 유클리드 알고리듬은 데데킨트의 보다 일반적인 아이디얼(ideals)의 이론에 의해 점차 가려졌습니다.[44]

"[유클리드 알고리듬]은 모든 알고리듬의 할아버지인데, 왜냐하면 그것은 현재까지 살아남은 가장 오래된 비-자명한 알고리듬이기 때문입니다."

도널드 커누스(Donald Knuth), The Art of Computer Programming, Vol. 2: Seminumerical Algorithms, 2판 (1981), p. 318.

유클리드 알고리듬의 또 다른 응용은 19세기에 개발되었습니다. 1829년에서, 샤를 스튀름(Charles Sturm)은 그 알고리듬이 임의의 주어진 구간에서 다항식의 실ㅅ 근을 세는 것에 대해 스튀름 체인(Sturm chain) 방법에 유용하다는 것을 보였습니다.[45]

유클리드 알고리듬은 최초의 정수 관계 알고리듬(integer relation algorithm)이며, 이것은 비례하는 실수 사이의 정수 관계를 찾는 것에 대한 방법입니다. 힐러맨 퍼거슨(Helaman Ferguson)과 R.W. Forcade (1979)[46] 및 LLL 알고리듬(LLL algorithm)과 같은, 여러 새로운 정수 관계 알고리듬이 개발되어 왔습니다.[47][48]

1969년에서, 콜과 데이비(Cole and Davie)는 최적의 전략을 가진, The Game of Euclid라고 불리는,[49] 유클리드 알고리듬을 기반으로 하는 2인용 게임을 개발했습니다.[50] 플레이어는 a와 b 돌 더미로 시작합니다. 플레이어는 교대로 큰 더미에서 작은 더미의 m 배수를 제거합니다. 따라서, 만약 두 더미가 x와 y 돌로 구성되어 있으면, 여기서 x가 y보다 크며, 다음 플레이어는 더 큰 더미를 x 돌에서 x − my 돌로 줄일 수 있는데, 후자가 비-음의 정수여야 합니다. 승자는 더미 1을 0 돌로 먼저 줄이는 플레이어입니다. [51][52]

Mathematical applications

Bézout's identity

베주의 항등식(Bézout's identity)은 두 정수 a와 b의 최대 공통 약수 g가 원래 두 숫자 a와 b의 선형 합으로 표현될 수 있음을 말합니다.[53] 다시 말해서, g = sa + tb를 만족하는 정수 s와 t를 항상 찾을 수 있습니다.[54][55]

정수 s와 t는 유클리드 알고리듬에서 방정식의 순서를 반대로 함으로써 몫 q0, q1, 등에서 계산될 수 있습니다.[56] 마지막에서-다음 방정식으로 시작하여, g는 몫 qN−1과 두 이전 나머지, rN−2 및 rN−3의 관점에서 표현될 수 있습니다:

g = rN−1 = rN−3 − qN−1 rN−2 .

그들 두 나머지는 그들의 몫과 이전 나머지의 관점에서 마찬가지로 표현될 수 있습니다:

rN−2 = rN−4 − qN−2 rN−3 및
rN−3 = rN−5 − qN−3 rN−4 .

rN−2 및 rN−3에 대해 이들 공식을 첫 번째 방정식에 대입하면 나머지 rN−4 및 rN−5의 선형 합으로 g를 산출합니다. 나머지를 그들의 이전 값을 포함하는 공식으로 대체하는 과정은 원래 숫자 a와 b에 도달할 때까지 계속될 수 있습니다:

r2 = r0 − q2 r1
r1 = b − q1 r0
r0 = a − q0 b.

모든 나머지 r0, r1 등이 대입된 후, 마지막 방정식은 g를 a와 b의 선형 합: g = sa + tb으로 표현합니다. 베주의 항등식(Bézout's identity), 및 따라서 이전 알고리듬은 유클리드 도메인(Euclidean domain)의 문맥에서 둘 다 일반화될 수 있습니다.

Principal ideals and related problems

베주의 항등식은 두 숫자 a와 b의 최대 공통 약수 g의 여전히 또 다른 정의를 제공합니다.[10] 모든 숫자 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의 배수의 집합과 동등합니다. 달리 말해서, 두 숫자 (a와 b)의 정수 배수의 모든 가능한 합의 집합은 gcd(a, b)의 배수의 집합과 동등합니다. GCD는 a와 b의 아이디얼(ideal)의 생성자라고 말합니다. 이 GCD 정의는 주요 아이디얼(principal ideal) (단일 원소에 의해 생성된 아이디얼)과 주요 아이디얼 도메인(principal ideal domain) (모든 각 아이디얼이 주요 아이디얼인 도메인(domain))의 현대 추상 대수(abstract algebra)적 개념으로 이어졌습니다.

특정 문제는 이 결과를 사용하여 해결될 수 있습니다.[57] 예를 들어, 부피 a와 b의 두 개의 측정 컵을 생각해 보십시오. 첫 번째 컵의 u 배수와 두 번째 컵의 v 배수를 더함으로써/뺌으로써, 모든 부피 ua + vb는 측정될 수 있습니다. 이들 부피는 모두 g = gcd(a, b)의 배수입니다.

Extended Euclidean algorithm

Main article: Extended Euclidean algorithm

베주의 항등식의 정수 s와 t는 확장된 유클리드 알고리듬(extended Euclidean algorithm)을 사용하여 효율적으로 계산될 수 있습니다. 이 확장은 유클리드의 알고리듬에 다음 시작 값과 함께,

s−2 = 1, t−2 = 0
s−1 = 0, t−1 = 1,

두 개의 다음 재귀 방정식을 추가합니다:[58]

sk = sk−2 − qksk−1
tk = tk−2 − qktk−1

이 재귀를 사용하여, 베주의 정수 s와 t는 s = sN 및 t = tN에 의해 제공되며, 여기서 N+1은 알고리듬이 rN+1 = 0으로 종료되는 단계입니다.

이 접근법의 타당성은 귀납법에 의해 보일 수 있습니다. 재귀 방정식이 알고리듬의 단계 k − 1까지 정확하다고 가정합니다; 달리 말해서, k보다 작은 모든 j에 대해, 다음임을 가정합니다:

rj = sj a + tj b.

알고리듬의 k번째 단계는 다음 방정식을 제공합니다:

rk = rk−2 − qkrk−1.

재귀 공식이 rk−2와 rk−1에 대해 정확한 것으로 가정되었으므로, 그들은 해당하는 s와 t 변수의 관점에서 표현될 수 있습니다:

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

이 방정식을 재정렬하면, 필요에 따라, 단계 k에 대해 재귀 공식을 산출합니다:

rk = sk a + tk b = (sk−2 − qksk−1) a + (tk−2 − qktk−1) b.

Matrix method

정수 s와 t는 동등한 행렬(matrix) 방법을 사용하여 역시 구할 수 있습니다.[59] 유클리드 알고리듬의 방정식의 다음 수열은

2-×-2 몫 행렬에 이-차원 나머지 벡터를 곱하는 곱으로 쓸 수 있습니다:

M은 모든 몫 행렬의 곱을 나타내는 것으로 놓습니다:

이것은 유클리드 알고리듬을 다음 형식으로 단순화합니다:

g를 b와 b의 선형 합으로 표현하기 위해, 이 방정식의 양쪽 변은 행렬 M의 역(inverse)에 의해 곱해질 수 있습니다.[59][60] M의 행렬식(determinant)은 (−1)N+1와 같은데, 왜냐하면 그것은, 그것의 각각은 음의 일인, 몫 행렬의 행렬식의 곱과 같기 때문입니다. M의 행렬식은 절코 영이 아니므로, 최종 나머지의 벡터는 M의 역을 사용하여 풀릴 수 있습니다:

제일 위의 방정식은 다음을 제공하므로:

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

베주의 항등식의 두 정수는 s = (−1)N+1m22 및 t = (−1)Nm12입니다. 행렬 방법은 유클리드 알고리듬의 단계마다 두 곱셈과 두 덧셈과 함께 동등한 재귀 방법만큼 효과적입니다.

Euclid's lemma and unique factorization

베주의 항등식은 숫자를 소수 인수로의 고유한 인수분해(unique factorization)를 보여주는 것과 같은 유클리드 알고리듬의 많은 응용에 필수적입니다.[61] 이를 설명하기 위해, 숫자 L이 두 인수 u와 v의 곱, 즉 L = uv으로 작성될 수 있다고 가정합니다. 만약 또 다른 숫자 w가 역시 L을 나누지만 u와 서로소이면, w는 다음 논증에 의해 v를 나누어야 합니다: 만약 u와 w의 최대 공통 약수가 1이면, 베주의 항등식에 의해 다음을 만족하는 정수 s와 t를 찾을 수 있습니다:

1 = su + tw .

양쪽 변에 v를 곱하면 다음 관계를 제공합니다:

v = suv + twv = sL + twv .

w는 오른쪽 변의 두 항을 나누기 때문에, 그것은 역시 왼쪽 변, v를 나누어야 합니다. 이 결과는 유클리드의 보조정리(Euclid's lemma)로 알려져 있습니다.[62] 구체적으로 특별히, 만약 소수가 L을 나누면, 그것은 L의 적어도 하나의 인수를 나누어야 합니다. 반대로, 만약 숫자 w가 숫자 a1, a2, ..., an의 수열의 각각에 대해 서로소이면, w는 역시 그들의 곱, a1 × a2 × ... × an에 대해 서로소입니다.[62]

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

L = p1p2…pm = q1q2…qn .

각 소수 p는 가정에 의해 L을 나누기 때문에, 그것은 q 인자 중 하나를 역시 나누어야 합니다; 각 q가 마찬가지로 소수이므로, 그것은 p = q여야 합니다. 반복적으로 p 인수로 나누면 각 p가 같은 짝 q를 가지고 있음을 보여줍니다; 두 개의 소수 인수분해는 그들의 순서를 제외하고는 동일합니다. 숫자를 소수로의 고유한 인수분해는, 아래에서 보인 것처럼, 수학적 증명에서 많은 응용을 가집니다.

Linear Diophantine equations

"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."
Plot of a linear Diophantine equation, 9x + 12y = 483. The solutions are shown as blue circles.

디오판토스 방정식은 그 해가 정수로 제한되는 방정식입니다; 그들은 3세기 알렉산드리아 수학자 디오판토스(Diophantus)의 이름을 따서 지어졌습니다.[64] 전형적인 선형 디오판토스 방정식은 다음을 만족하는 정수 x와 y를 찾습니다:[65]

ax + by = c

여기서 a, b 및 c는 주어진 정수입니다. 이것은 모듈러 산술(modular arithmetic)에서 x에 대해 방정식으로 쓸 수 있습니다:

ax ≡ c mod b.

g를 a와 b의 최대 공통 약수로 놓습니다. ax + by에서 두 항은 g로 나누어질 수 있습니다; 그러므로, c가 g에 의해 역시 나누어져야 하거나, 방정식은 해를 가지지 않습니다. 양쪽 변을 c/g로 나눔으로써, 방정식은 베주의 항등식으로 줄어들 수 있습니다:

sa + tb = g

여기서 s와 t는 확장된 유클리드 알고리듬(extended Euclidean algorithm)에 의해 구해집니다.[66] 이것은 디오판토스 방정식에 대한 하나의 해, x1 = s (c/g) 및 y1 = 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] 이것은 해가 임의의 실수(real number)가 될 수 있을 때 선형 방정식의 시스템(system of linear equations)에 대해 불가능합니다 (미달-결정된 시스템(underdetermined system)을 참조하십시오).

Multiplicative inverses and the RSA algorithm

유한 필드(finite field)는 네 가지 일반화 연산을 갖는 숫자의 집합입니다. 그 연산은 덧셈, 뺄셈, 곱셈 및 나눗셈이라고 불리고, 교환성(commutativity), 결합성(associativity) 및 분배성(distributivity)과 같은 그들의 보통 속성을 가집니다. 유한 필드의 예제는 모듈러 산술(modular arithmetic)을 사용하는 13 개의 숫자 {0, 1, 2, ..., 12}의 집합입니다. 이 필드에서, 임의의 수학적 연산 (덧셈, 뺄셈, 곱셈, 또는 나눗셈)의 결과는 모듈로(modulo) 13으로 줄어듭니다; 즉, 결과가 범위 0–12 이내에 들어갈 때까지 13의 배수가 더해지거나 빼집니다. 예를 들어, 5 × 7 = 35 mod 13 = 9의 결과입니다. 그러한 유한 필드는 임의의 소수 p에 대해 정의될 수 있습니다; 보다 정교한 정의를 사용하여, 그들은 소수 p m의 임의의 거듭제곱 m에 대해 역시 정의될 수 있습니다. 유한 필드는 종종 갈루아(Galois) 필드라고 불리고, GF(p) 또는 GF(p m)로 축약됩니다.

m 숫자를 갖는 그러한 필드에서, 모든 각 비-영 원소 a는 aa−1 = a−1a ≡ 1 mod m을 만족하는 고유한 모듈러 곱셈 역(modular multiplicative inverse), a−1을 가집니다. 이 역은 합동 방정식 ax ≡ 1 mod m,[69] 또는 동등한 다음 선형 디오판토스 방정식[70]을 풂으로써 구할 수 있습니다:

ax + my = 1.

이 방정식은 위에서 설명한 것처럼 유클리드 알고리듬에 의해 풀릴 수 있습니다. 곱셈 역을 찾는 것은 전자 상거래(electronic commerce)에서 널리 사용되는 RSA 알고리듬(RSA algorithm)의 필수 단계입니다; 구체적으로 특별히, 그 방정식은 메시지를 해독하기 위해 사용되는 정수를 결정합니다.[71] 비록 RSA 알고리듬이 필드가 아닌 링(rings)을 사용할지라도, 유클리드 알고리듬은 여전히 존재하는 곱셈 역을 찾기 위해 사용될 수 있습니다. 유클리드 알고리듬은 역시 오류-수정 코드(error-correcting code)에서 다른 응용을 가집니다; 예를 들어, 그것은 갈루아 필드를 기반으로하는 BCH 및 리드–솔로몬 코드(Reed–Solomon code)를 디코딩하는 벌러캠프-매시 알고리듬(Berlekamp–Massey algorithm)의 대안으로 사용될 수 있습니다.[72]

Chinese remainder theorem

유클리드의 알고리듬은 여러 선형 디오판토스 방정식을 풀기 위해 역시 사용될 수 있습니다.[73] 그러한 방정식은 정수 x를 나타내기 위한 새로운 방법을 설명하는 중국 나머지 정리(Chinese remainder theorem)에서 발생합니다. 정수를 그것의 자릿수로 표시하는 대신에, N 서로소 숫자 mi의 집합을 그것의 나머지 xi 모듈로에 의해 나타낼 수 있습니다:[74]

목표는 N 나머지 xi로부터 x를 결정하는 것입니다. 해는 여러 방정식을 모든 개별 모듈로 mi의 곱인 훨씬 더 큰 모듈러스 M을 갖는 단일 선형 디오판토스 방정식으로 결합하고 Mi를 다음으로 정의하는 것입니다:

따라서, 각 Mi는 mi를 제외한 모든 모듈로의 곱입니다. 해는 다음을 만족하는 N 새로운 숫자 hi를 찾는 것에 의존합니다:

이들 숫자 hi와 함께, 임의의 정수 x는 다음 방정식에 의해 그것의 나머지 xi로부터 다시-구성될 수 있습니다:

이들 숫자 hi는 Mi의 곱셈의 역이므로, 그들은 이전 하위-섹션에서 설명된 것처럼 유클리드의 알고리듬을 사용하여 찾아질 수 있습니다.

Stern–Brocot tree

Main article: Stern–Brocot tree

유클리드 알고리듬은 모든 양의 유리수(rational number)의 집합을 스턴–브로코 트리(Stern–Brocot tree)라고 불리는 무한 이진 검색 트리(binary search tree)로 배열하기 위해 사용될 수 있습니다. 숫자 1 (분수 1/1로 표시됨)은 트리의 뿌리에 배치되고, 임의의 다른 숫자 a/b의 위치는 유클리드 알고리듬의 원래 형식을 사용하여 gcd(a,b)를 계산함으로써 찾아질 수 있으며, 이것에서 각 단계는 두 주어진 숫자 중 더 큰 숫자를 (그것의 나머지가 아닌) 더 작은 숫자로 바꾸며, 두 개의 같은 숫자가 도달될 때 중지합니다. 두 숫자 중 첫 번째 숫자를 대체하는 유클리드 알고리듬의 단계는 노드에서 그것의 오른쪽 자식까지의 트리에서 단계에 해당하고, 두 숫자 중 두 번째 숫자를 대체하는 단계는 노드의 그것의 왼쪽 자식까지의 트리에서 단계에 해당합니다. 이 방법에서 구성된 단계의 수열은 a/b가 가장-낮은 항으로 주어졌는지 여부에 의존하지 않고, 뿌리에서 숫자 a/b를 포함하는 노드로의 경로를 형성합니다.[75] 이 사실은 각 양의 유리수가 이 트리에서 정확히 한번 나타남을 입증하기 위해 사용될 수 있습니다.

예를 들어, 3/4는 뿌리에서 시작하고, 왼쪽으로 한번 가고, 그런-다음 오른쪽으로 두번 감으로써 찾아질 수 있습니다:

The Stern–Brocot tree, and the Stern–Brocot sequences of order i for i = 1, 2, 3, 4

유클리드 알고리듬은 콜킨–윌프 트리(Calkin–Wilf tree)라고 불리는 유리수에 대한 또 다른 이진 트리와 거의 같은 관계를 가집니다. 차이는 경로가 반전된다는 것입니다: 트리의 뿌리에서 대상으로의 경로를 생성하는 대신에, 그것은 대상에서 뿌리로의 경로를 생성합니다.

Continued fractions

유클리드 알고리듬은 연속된 분수(continued fraction)와 밀접한 관계를 가집니다.[76] 방정식의 수열은 다음 형식으로 작성될 수 있습니다:

오른쪽 변에 대한 마지막 항은 항상 다음 방정식의 왼쪽 변의 역과 같습니다. 따라서, 처음 두 방정식은 다음 형식으로 결합될 수 있습니다:

세 번째 방정식은 분모 항 r1/r0을 대체하기 위해 사용될 수 있으며, 다음을 산출합니다:

나머지 rk/rk−1의 마지막 비율은, 마지막 방정시까지, 급수에서 다음 방정식을 사용하여 항상 대체될 수 있습니다. 그 결과는 다음 연속된 분수입니다:

위에서 작동하는 예제에서, gcd(1071, 462)는 계산되었고, 몫 qk는 각각 2, 3, 및 7이었습니다. 그러므로, 분수 1071/462는, 계산에서 확인될 수 있는 것처럼, 다음으로 쓸 수 있습니다:

.

Factorization algorithms

최대 공약수를 계산하는 것은 폴라드의 로우 알고리듬(Pollard's rho algorithm),[77] 쇼어의 알고리듬(Shor's algorithm),[78] 딕슨의 인수분해 방법(Dixon's factorization method)[79] 및 렌스트라 타원형 곡선 인수분해[80]와 같은 여러 정수 인수분해(integer factorization) 알고리듬[81]에서 필수적인 단계입니다. 유클리드 알고리듬은 이 GCD를 효율적으로 찾기 위해 사용될 수 있습니다. 연속된 분수 인수분해(Continued fraction factorization)는 유클리드의 알고리듬을 사용하여 결정되는 연속된 분수를 사용합니다.[82]

Algorithmic efficiency

"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."
Number of steps in the Euclidean algorithm for gcd(x,y). Lighter (red and yellow) points indicate relatively few steps, whereas darker (violet and blue) points indicate more steps. The largest dark area follows the line y = Φx, where Φ is the golden ratio.

유클리드 알고리듬의 계산 효율성은 철저하게 연구되어 왔습니다.[83] 이 효율성은 알고리듬에 필요한 나눗셈 단계의 숫자에 각 단계의 계산 비용을 곱한 것에 의해 설명될 수 있습니다. 유클리드 알고리듬의 첫 번째 알려진 분석은 1811년에 A. A. L. Reynaud에 의한 것이며,[84] 그는 입력 (u, v)의 나눗셈 단계의 숫자가 v에 의해 경계짐을 보였습니다; 나중에 그는 이것을 v/2  + 2로 개선했습니다. 나중에, 1841년에, 팡키(P. J. E. Finck)는 나눗셈 단계의 숫자가 최대 2 log2 v + 1임을 보였었고,[85] 따라서 유클리드의 알고리듬은 시간 다항식에서 입력의 크기에서 실행합니다.[86] 에밀 리지(Émile Léger)는, 1837년에, 최악의 경우를 연구했으며, 그것은 입력이 연속적인 피보나치 숫자(Fibonacci numbers)일 때입니다.[86] 팡키의 분석은 1844년에 개브리엘 라미(Gabriel Lamé)에 의해 개량되었으며,[87] 그는 완성에 필요한 단계의 숫자가 더 작은 숫자 b의 밑수-10 자릿수의 숫자 h의 5배를 절대 넘지 않는다는 것을 보였습니다.[88][89]

(단일 기계 단어에 맞는 숫자에 대한 gcd 계산의 복잡성을 분석하는 데 적합한) 균등 비용 모델(uniform cost model)에서, 알고리듬의 각 단계는 상수 시간(constant time)이 걸리고, 라미의 분석은 전체 실행 시간이 역시 O(h)임을 의미합니다. 어쨌든, 더 큰 숫자와 함께 계산에 적합한 계산의 모델에서, 알고리듬에서 단일 나머지 계산의 계산 비용이 O(h2)만큼 클 수 있습니다.[90] 이 경우에서, 알고리듬의 모든 단계에 대해 전체 시간은 망원 급수(telescoping series)를 사용하여 분석될 수 있으며, 그것은 역시 O(h2)임을 보여줍니다. 빠른 정수 곱셈에 대해 쇤하게–슈트라센 알고리듬(Schönhage–Strassen algorithm)에 기반한 현대 알고리듬 기술은 이를 가속화하기 위해 사용될 수 있으며, GCD에 대해 준-선형 알고리듬(quasilinear algorithms)으로 이어집니다.[91][92]

Number of steps

두 자연수, a와 b의 GCD를 계산하는 단계의 숫자는 T(a, b)로 표시될 수 있습니다.[93] 만약 g가 a와 b의 GCD이면, 두 개의 서로소 숫자 m과 n에 대해 a = mg 및 b = ng입니다. 이때

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

왜냐하면 유클리드 알고리듬에서 모든 단계를 g로 나눔으로써 알 수 있기 때문입니다.[94] 같은 논증에 의해, 만약 a와 b가 공통 인수 w에 의해 곱해지면: T(a, b) = T(wa, wb), 단계의 숫자는 같은 것으로 유지됩니다. 그러므로, 단계 T의 숫자는, 두 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]

Worst-case

만약 유클리드 알고리듬이 한 쌍의 자연수 a > b > 0에 대해 N 단계를 요구하면, 이것이 참인 a와 b의 가장 작은 값은 각각 피보나치 숫자(Fibonacci number) FN+2 및 FN+1입니다.[95] 보다 정확하게, 만약 유클리드 알고리듬이 쌍 a > b에 대해 N 단계를 요구하면, 우리는 a ≥ FN+2 및 b ≥ FN+1를 가집니다. 이것은 귀납법(induction)으로 보일 수 있습니다.[96] 만약 N = 1이면, b는 나머지없이 a를 나눕니다; 이것이 참인 가장 작은 자연수는 b = 1 및 a = 2이며, 각각 F2 및 F3입니다. 이제 결과가 N의 모든 값에 대해 M − 1까지 유지된다고 가정합니다. M-단계 알고리듬의 첫 번째 단계는 a = q0b + r0이고, 유클리드 알고리듬은 쌍 b > r0에 대해 M − 1 단계를 요구합니다. 귀납 가설에 의해, 우리는 b ≥ FM+1 및 r0 ≥ FM을 가집니다. 그러므로, a = q0b + r0 ≥ b + r0 ≥ FM+1 + FM = FM+2이며, 이것은 원했던 부등식입니다. 이 증명은, 1844년에 개브리엘 라미(Gabriel Lamé)에 의해 발표되었으며, 계산 복잡도 이론(computational complexity theory)의 시작,[97] 및 역시 피보나치 숫자의 최초 실제 적용을 나타냅니다.[95]

이 결과는 유클리드 알고리듬의 단계의 숫자가 그것의 자릿수 (밑수 10)의 다섯 배를 넘을 수 없음을 보여주기에 충분합니다.[98] 알고리듬이 N 단계가 필요한 것에 대해, b는 FN+1보다 크거나 같으며 차례로 φN−1보다 크거나 같으며, 여기서 φ는 황금 비율(golden ratio)입니다. b ≥ φN−1이므로, N − 1 ≤ logφb입니다. log10φ > 1/5이므로, (N − 1)/5 < log10φ logφb = log10b입니다. 따라서, N ≤ 5 log10b입니다. 따라서, 유클리드 알고리듬은 항상 O(h) 나눗셈보다 작게 필요하며, 여기서 h는 더 작은 숫자 b의 자릿수입니다.

Average

유클리드 알고리듬에 의해 수행된 평균 단계의 숫자는 세 가지 다른 방법으로 정의되어 왔습니다. 첫 번째 정의는 정수 0에서 a − 1까지 같은 확률로 선택된 주어진 숫자 a와 더 작은 자연수 b의 GCD를 계산하기 위해 요구된 평균 시간 T(a)입니다:[93]

어쨌든, T(a, b)는 두 숫자의 GCD에 따라 극적으로 변동하므로, 평균된 함수 T(a)도 마찬가지로 "노이즈"입니다.[99]

이 노이즈를 줄이기 위해 두 번째 평균 τ(a)는 모든 숫자를 a와 서로소로 취합니다:

a보다 작은 서로소 정수 φ(a)가 있으며, 여기서 φ는 오일러의 토션트 함수(Euler's totient function)입니다. 이 타우 평균은 a와 함께 매끄럽게 증가합니다:[100][101]

여기서 잔여 오차는 차수 a−(1/6) + ε의 것이며, ε는 무한소(infinitesimal)입니다. 이 공식에서 상수 C (포터의 상수(Porter's Constant)[102])는 다음과 같습니다:

여기서 γ는 오일러–마스케로니 상수(Euler–Mascheroni constant)이고 ζ'는 리만 제타 함수(Riemann zeta function)의 도함수(derivative)입니다.[103][104] 선행 계수 (12/π2) ln 2는 두 독립적인 방법에 의해 결정되었습니다.[105][106]

첫 번째 평균은 a의 약수 d에 걸쳐 합함으로써 타우 평균으로부터 계산될 수 있으므로:[107]

그것은 다음 공식에 의해 근사화될 수 있습니다:[108]

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

세 번째 평균 Y(n)는 a와 b 둘 다가 1에서 n까지 (균등 분포와 함께) 무작위로 선택될 때 요구된 단계의 숫자의 평균으로 정의됩니다:[108]

T(a)에 대해 근사 공식을 이 방정식에 대입하면 Y(n)에 대해 평가를 산출합니다:[110]

Computational expense per step

유클리드 알고리듬의 각 단계 k에서, 몫 qk와 나머지 rk는 주어진 정수의 쌍 rk−2와 rk−1에 대해 계산됩니다:

rk−2 = qk rk−1 + rk.

단계 당 계산 비용은 주로 qk를 찾는 것과 관련이 있는데, 왜냐하면 나머지 rk는 rk−2, rk−1, 및 qk으로부터 빠르게 계산될 수 있습니다:

rk = rk−2 − qk rk−1.

h-비트 숫자를 나누는 계산 비용은 O(h(ℓ+1))으로 스케일되며, 여기서 ℓ은 몫의 길이입니다.[90]

비교를 위해, 유클리드의 원래 뺄셈-기반 알고리듬은 훨씬 더 느릴 수 있습니다. 단일 정수 나눗셈은 뺄셈의 몫 q 숫자와 동등합니다. 만약 a와 b의 비율이 매우 크면, 몫이 크고 많은 뺄셈이 요구될 것입니다. 다른 한편으로, 몫이 작은 정수일 가능성이 매우 높다는 것을 보여 왔습니다. 주어진 몫 q의 확률은 근사적으로 ln|u/(u − 1)|이며 여기서 u = (q + 1)2입니다.[111] 설명을 위해, 1, 2, 3, 또는 4의 몫의 확률은 각각 약 41.5%, 17.0%, 9.3%, 및 5.9%입니다. 뺄셈의 연산이 나눗셈보다 빠르기 때문에, 특히 매우 큰 숫자에 대해,[112] 뺄셈-기반 유클리드 알고리듬은 나눗셈-기반 버전과 경쟁합니다.[113] 이것은 유클리드 알고리듬의 이진 버전(binary version)에서 악용됩니다.[114]

추정된 단계의 숫자와 단계 당 추정된 계산 비용을 조합하면 유클리드의 알고리듬이 초기 두 숫자 a와 b에서 자릿수 h의 평균 숫자와 함께 이차적으로 (h2) 증가함을 보여줍니다. h0, h1, ..., hN−1가 연속된 나머지 r0, r1, ..., rN−1에서 자릿수의 숫자를 나타내는 것으로 놓습니다. 단계의 숫자 N은 h와 함께 선형적으로 증가하므로, 실행 시간은 다음에 의해 경계집니다:

Alternative methods

유클리드의 알고리듬은 단순함으로 인해 특히 작은 숫자에 대해 실제로 널리 사용됩니다.[115] 비교를 위해, 유클리드 알고리듬에 대한 대안의 효율성은 결정될 수 있습니다.

두 자연수 a와 b의 GCD를 찾는 하나의 비효율적인 방법은 모든 그들의 공통 약수를 계산하는 것입니다; GCD는 가장 큰 공통 약수입니다. 공통 약수는 두 숫자를 2에서 더 작은 숫자 b까지 연속적인 정수로 나눔으로써 구할 수 있습니다. 이 접근 방식의 단계의 숫자는 b와 함께 선형적으로 증가하거나, 자릿수의 숫자에서 기하급수적으로 증가합니다. 또 다른 비효율적인 접근법은 하나 또는 두 숫자의 소수 인수를 찾는 것입니다. 위에서 언급했듯이, GCD는 두 숫자 a와 b에 의해 공유된 소수 인수의 곱과 같습니다.[6] 현재의 소수 인수분해(prime factorization)에 대해 방법은 역시 비효율적입니다; 많은 현대 암호화 시스템은 심지어 이러한 비효율성에 의존합니다.[9]

이진 GCD 알고리듬(binary GCD algorithm)은 컴퓨터에서 사용되는 이진(binary) 표현을 이용함으로써 나눗셈을 더 빠른 연산으로 대체하는 효율적인 대안입니다.[116][117] 어쨌든, 이 대안은 O(h²)처럼 역시 스케일됩니다. 심지어 그것이 같은 방법으로 스케일되지만, 일반적으로 실제 컴퓨터에서 유클리드 알고리듬보다 더 빠릅니다.[91] 추가적인 효율성은 두 숫자 a와 b의 오직 선행 자릿수를 검사함으로써 수집될 수 있습니다.[118][119] 이진 알고리듬은, 속도에서 증가하는 다섯겹까지와 함께,[120] 다른 밑수 (k-진수 알고리듬)으로 확장될 수 있습니다.[121] 레머의 GCD 알고리듬(Lehmer's GCD algorithm)은 임의의 밑수에서 GCD 계산 속도를 높이기 위해 이진 알고리듬과 같은 일반적인 원칙을 사용합니다.

매우 큰 정수 (25,000 자릿수 이상)에 대해 재귀적 접근 방식은 쇤하게(Schönhage),[122][123] 및 스틸리(Stehlé)와 짐머만(Zimmermann)[124]과 같은 준-선형(quasilinear) 정수 GCD 알고리듬을 유도합니다.[125] 이들 알고리듬은 위에 주어진 유클리드 알고리듬의 2x2 행렬 형식을 활용합니다. 이들 준-선형 방법은 일반적으로 O(h (log h)2 (log log h))로 스케일됩니다.[91][92]

Generalizations

비록 유클리드 알고리듬이 두 자연수 (양의 정수)의 최대 공통 약수를 찾기 위해 사용되지만, 실수로, 및 다항식(polynomial),[126] 이차 정수(quadratic integer)[127] 및 후르비츠 쿼터니언(Hurwitz quaternion)[128]과 같은 다른 수학적 대상으로 일반화될 수 있습니다. 후자의 경우에서, 유클리드 알고리듬은 고유한 인수분해의 중요한 속성을 입증하기 위해 사용됩니다. 즉, 그러한 숫자는 기약 원소(irreducible element), 소수의 짝으로 고유하게 인수화될 수 있습니다. 고유한 인수분해는 숫자 이론의 많은 증명에 필수적입니다.

Rational and real numbers

유클리드의 알고리듬은, 그의 원론(Elements)의 책 10에서 유클리드에 의해 설명된 것처럼, 실수(real number)에 적용될 수 있습니다. 알고리듬의 목표는 두 주어진 실수, a와 b가 그것의 정수 배수: a = mg와 b = ng가 됨을 만족하는 실수 g를 식별하는 것이며, 여기서 m과 n은 정수(integer)입니다.[26] 이 식별은 실수 a와 b 사이의 정수 관계(integer relation)를 찾는 것과 동등합니다; 즉, 그것은 sa + tb = 0를 만족하는 정수 s와 t를 결정합니다. 유클리드는 이 알고리듬을 비-정수-비율-가능 길이(incommensurable lengths)의 문제를 다루기 위해 사용합니다. [129][130]

실수 유클리드 알고리듬은 두 가지 측면에서 정수 짝과 다릅니다. 첫째, 비록 몫 qk가 이전과 같이 정수일지라도, 나머지 rk는 실수입니다. 둘째, 알고리듬은 유한한 단계의 숫자 N으로 끝나는 것이 보장하지 않습니다. 만약 그렇다면, 분수 a/b는 유리수, 즉 두 정수의 비율입니다:

그리고 유한 연속된 분수 [q0; q1, q2, ..., qN]로 쓸 수 있습니다. 만약 알고리듬이 멈추지 않으면, 분수 a/b는 무리수(irrational number)이고 무한한 연속된 분수 [q0; q1, q2, …]에 의해 설명될 수 있습니다.[131] 무한 연속된 분수의 예제는 황금 비율(golden ratio) φ = [1; 1, 1, ...]이고 이의 제곱근(square root of two), √2 = [1; 2, 2, ...]입니다.[132] 알고리듬이 멈출 가능성은 거의 없는데, 왜냐하면 두 실수의 거의 모든(almost all) 비율 a/b은 무리수이기 때문입니다.[133]

무한 연속된 분수는 k가 증가함에 따라 개선되는 a/b에 대한 근사를 산출하기 위해 단계 k [q0; q1, q2, ..., qk]에서 잘릴 수 있습니다. 근사는 수렴(convergents) mk/nk에 의해 설명됩니다; 분자와 분모는 서로소이고 다음 재귀 관계(recurrence relation)를 따릅니다:

여기서 m−1 = n−2 = 1 및 m−2 = n−1 = 0는 재귀의 초기 값입니다. 수렴하는 mk/nk는 분모 nk를 갖는 a/b에 대한 가장-좋은 유리수(rational number) 근사입니다:[134]

Polynomials

Main article: Polynomial greatest common divisor

단일 변수 x에서 다항식은 정수에 대해 소수의 아날로그인 기약 다항식(irreducible polynomial)으로 더해지고, 곱해지고, 인수화될 수 있습니다. 두 다항식 a(x)와 b(x)의 최대 공통 약수 다항식 g(x)는 그들의 공유된 기약 다항식의 곱으로 정의되며, 이것은 유클리드 알고리듬을 사용하여 식별될 수 있습니다.[126] 기본 절차는 정수에 대해 절차와 비슷합니다. 각 단계 k에서, 몫 다항식 qk(x) 및 나머지 다항식 rk(x)가 재귀 방정식을 만족시키기 위해 식별됩니다:

여기서 r−2(x) = a(x) 및 r−1(x) = b(x)입니다. 각 몫 다항식은 각 나머지가 영이거나 그것의 이전의 차수보다 더 작은 것: deg[rk(x)] < deg[rk−1(x)]을 갖는 것을 만족하게 선택됩니다. 차수는 비-음의 정수이고, 모든 각 단계마다 감소하므로, 유클리드 알고리듬은 유한한 단계의 숫자에서 끝납니다. 마지막 비-영 나머지는 원래 두 다항식 a(x)와 b(x)의 최대 공통 약수입니다. [135]

예를 들어, 각 인수가 두 이차 다항식인, 다음 두 사차 다항식을 생각해 보십시오:

a(x)를 b(x)로 나누면(Dividing) 나머지 r0(x) = x3 + (2/3)x2 + (5/3)x − (2/3)를 산출합니다. 다음 단계에서, b(x)가 나머지 r1(x) = x2 + x + 2를 산출하는 r0(x)로 나뉩니다. 마지막으로, r0(x)를 r1(x)로 나누면 영 나머지를 산출하며, r1(x)가, 그들의 인수분해와 일치하는, a(x)와 b(x)의 최대 공통 약수 다항식임을 나타냅니다.

정수에 대해 위에서 설명된 많은 응용은 다항식에 걸쳐 이어집니다.[136] 유클리드 알고리듬은 다항식에 대해 선형 디오판토스 방정식과 중국 나머지 문제를 풀기 위해 사용될 수 있습니다; 다항식의 연속된 분수는 역시 정의될 수 있습니다.

다항식 유클리드 알고리듬은 스튀름 체인(Sturm chain), 주어진 실수 구간(real interval) 안에 놓이는 다항식의 영들(zeros of a polynomial)을 세는 방법과 같은 다른 응용을 가집니다.[137] 이것은 차례로 제어 이론(control theory)에서 루우쓰–후어비츠 안정성 기준(Routh–Hurwitz stability criterion)과 같은 여러 영역에서 응용을 가집니다. [138]

마지막으로, 다항식의 계수는 정수, 실수 또는 심지어 복소수에서 추출될 필요가 없습니다. 예를 들어, 계수는 위에서 설명된 유한 필드 GF(p)와 같은 일반적인 필드에서 추출될 수 있습니다. 유클리드 알고리듬과 그것의 응용에 대한 해당하는 결론은 심지어 그러한 다항식에 대해 역시 유지됩니다.[126]

Gaussian integers

"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."
Distribution of Gaussian primes u + vi in the complex plane, with norms u2 + v2 less than 500

가우스 정수는 형식 α = u + vi의 복소수(complex number)이며, 여기서 u와 v는 보통의 정수(integer)이고[note 2] i는 음의 일의 제곱근(square root of negative one)입니다.[139] 유클리드 알고리듬의 아날로그를 정의함으로써, 가우스 정수는 위의 논증에 의해 고유하게 인수분해될 것으로 보일 수 있습니다.[40] 이 고유한 인수분해는 모든 피타고라스 세-쌍(Pythagorean triple)을 도출하는 것 또는 두 제곱의 합에 대한 페르마의 정리(Fermat's theorem on sums of two squares)를 입증하는 것과 같은 많은 응용에서 도움이 됩니다.[139] 일반적으로, 유클리드 알고리듬은 그러한 응용에 편리하지만 필수적인 것은 아닙니다; 예를 들어, 그 정리는 종종 다른 논증에 의해 입증될 수 있습니다.

두 개의 가우스 정수 α와 β에 대해 개발된 유클리드 알고리듬은 보통의 정수에 대한 것과 거의 같지만,[140] 두 가지 측면에서 다릅니다. 이전과 마찬가지로, 각 단계 k에서 태스크는 다음을 만족하는 몫 qk와 나머지 rk를 식별하는 것입니다:

여기서 rk−2 = α, 및 rk−1 = β이고, 모든 각 나머지는 그것의 이전 것보다 엄격하게 더 작습니다: |rk| < |rk−1|. 첫 번째 차이점은 몫과 나머지가 그 자체로 가우스 정수이고, 따라서 복소수(complex number)라는 것입니다. 몫 qk는 일반적으로 (복소수 α/β와 같은) 정확한 비율의 실수와 복소수 부분을 가장 가까운 정수로 반올림함으로써 구해집니다.[140] 두 번째 차이점은 하나의 복소수 나머지가 또 다른 것보다 "더 작게" 될 수 있는 방법을 정의할 필요성에 있습니다. 이것을 하기 위해, 노름 함수(norm function) f(u + vi) = u2 + v2가 정의되며, 이것은 모든 각 가우스 정수 u + vi를 보통의 정수로 변환합니다. 유클리드 알고리듬의 각 단계 k 후에, 나머지 f(rk)의 노름은 이전 나머지의 노름, f(rk−1)보다 작습니다. 노름은 비-음의 정수이고 모든 각 단계마다 감소하므로, 가우스 정수에 대해 유클리드 알고리듬은 유한한 단계로 끝납니다.[141] 마지막 비-영 나머지는 gcd(α, β), α와 β 둘 다를 나누는 가장 큰 노름의 가우스 정수입니다; 그것은 단위, ±1 또는 ±i에 의한 곱셈까지 고유합니다.[142]

유클리드 알고리듬의 다른 많은 응용은 가우스 정수로 이어집니다. 예를 들어, 가우스 정수에 대해 선형 디오판토스 방정식과 중국 나머지 문제를 해결하기 위해 사용될 수 있습니다;[143] 가우스 정수의 연속된 분수는 역시 정의될 수 있습니다.[140]

Euclidean domains

덧셈과 곱셈으로 표시되는 두 개의 이항 연산(binary operation) 아래의 원소의 집합은, 만약 그것이 교환적 링(commutative ring) R을 형성하고, 대략적으로 말하면, 일반화된 유클리드 알고리듬이 그들 위에 수행될 수 있으면 유클리드 도메인(Euclidean domain)이라고 불립니다.[144][145] 그러한 링의 두 가지 연산은 보통의 산술의 덧셈과 곱셈일 필요는 없습니다; 오히려, 그들은 수학적 그룹(mathematical group) 또는 모노이드(monoid)의 연산과 같은 보다 일반적일 수 있습니다. 그럼에도 불구하고, 이들 일반적인 연산은 교환성(commutativity), 결합성(associativity) 및 분배성(distributivity)과 같은, 보통의 산술을 지배하는 많은 법칙을 존중해야 합니다.

일반화된 유클리드 알고리듬은 유클리드 함수, 즉, R에서 임의의 두 비-영 원소 a와 b에 대해, a = qb + r 및 f(r) < f(b)를 만족하는 R에서 q와 r이 존재함을 만족하는 R에서 비-음 정수의 집합으로의 매핑 f를 요구합니다.[146] 그러한 매핑의 예제는 정수에 대해 절댓값, 일변수 다항식(univariate polynomial)에 대해 차수, 및 위의 가우스 정수에 대해 노름이 있습니다.[147][148] 기본 원리는 알고리듬의 각 단계가 엄청나게 f를 감소시키는 것입니다; 따라서, 만약 f가 오직 유한한 횟수로 줄여질 수 있으면, 알고리듬은 유한한 단계의 숫자에서 중지해야 합니다. 이 원리는 비-음의 정수의 바른-순서(well-order)화 속성에 의존하며, 이것은 비-음의 정수의 모든 각 비-빈 집합이 가장 작은 구성원을 갖는다고 주장합니다.[149]

산술의 기본 정리(fundamental theorem of arithmetic)는 임의의 유클리드 도메인에 적용됩니다: 유클리드 도메인으로부터 임의의 숫자는 기약 원소(irreducible element)로 고유하게 인수화될 수 있습니다. 임의의 유클리드 도메인은, 비록 전환이 참은 아닐지라도, 고유한 인수분해 도메인(unique factorization domain) (UFD)입니다.[149] 유클리드 도메인과 UFD는 GCD 도메인(GCD domain), 두 수의 최대 공통 약수가 항상 존재하는 도메인의 부분-클래스입니다.[150] 달리 말해서, 비록 최대 공통 약수가 유클리드 알고리듬을 사용하여 찾을 수 없을지라도, 최대 공통 약수가 (도메인에서 모든 원소 쌍에 대해) 존재할 수 있습니다. 유클리드 도메인은 항상 주요 아이디얼 도메인(principal ideal domain) (PID), 모든 각 아이디얼(ideal)이 주요 아이디얼(principal ideal)인 정수 도메인(integral domain)입니다.[151] 다시 한번, 그 전환은 참이 아닙니다: 모든 각 PID가 유클리드 도메인은 아닙니다.

유클리드 도메인의 고유한 인수분해는 많은 응용에서 유용합니다. 예를 들어, 가우스 정수의 고유한 인수분해는 모든 피타고라스 세-쌍(Pythagorean triple)에 대해 공식을 유도하는 것 및 두 제곱의 합에 대한 페르마의 정리(Fermat's theorem on sums of two squares)를 입증하는 것에서 편리합니다.[139] 고유한 인수분해는, 조제프 리우빌(Joseph Liouville)의 제안에 기초한 유클리드 알고리듬의 효율성을 분석한 같은 수학자, 개브리엘 라미(Gabriel Lamé)에 의해 1847년에 발표된 페르마의 마지막 정리(Fermat's Last Theorem)의 시되된 증명에서 핵심 요소였습니다.[152] 라미의 접근은 형시 x + ωy의 숫자의 고유한 인수분해를 요구하며, 여기서 x와 y는 정수이고, ω = e2iπ/n은 1의 n번째 근, 즉, ωn = 1입니다. 비록 이 접근이 (n = 3, 아이슈타인 정수(Eisenstein integer)와 같은) n의 일부 값에 대해 성공할지라도, 일반적으로 그러한 숫자는 고유하게 인수화되지 않습니다. 일부 원분 필드(cyclotomic field)에서 고유한 인수분해의 이 실패는 에른스트 쿠머(Ernst Kummer)를 아이디얼 숫자(ideal number)의 개념으로, 나중에 리하르트 데데킨트(Richard Dedekind)를 아이디얼(ideals)로 이끌었습니다.[153]

Unique factorization of quadratic integers

"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."
Distribution of Eisenstein primes u + vω in the complex plane, with norms less than 500. The number ω is a cube root of 1.

이차 정수(quadratic integer) 링은 유클리드 도메인을 설명하는 것에 도움이 됩니다. 이차 정수는 허수 단위(imaginary unit) i가 숫자 ω로 대체되는 것에서 가우스 정수의 일반화입니다. 따라서, 그들은 형식 u + vω를 가지며, 여기서 u와 v는 정수이고 ω는 매개변수 D에 의존하는 두 가지 형식 중 하나를 가집니다. 만약 D가 사의 배수 더하기 일과 같지 않으면,

만약, 어쨌든, D가 사의 배수 더하기 일과 같으면,

만약 함수 f가 위의 가우스 정수의 차수에 사용되는 그것과 같은 노름(norm) 함수에 해당하면, 그 도메인은 노름-유클리드(norm-Euclidean)로 알려져 있습니다. 이차 정수의 노름-유클리드 링이 정확히 그들의 것이며 여기서 D는 값 −11, −7, −3, −2, −1, 2, 3, 5, 6, 7, 11, 13, 17, 19, 21, 29, 33, 37, 41, 57, 또는 73 중의 하나입니다.[154][155] 경우 D = −1 및 D = −3는 각각 가우스 정수(Gaussian integer)이고 아인슈타인 정수(Eisenstein integer)를 산출합니다.

만약 f가 임의의 유클리드 함수가 될 수 있으면, 도메인이 유클리드인 D의 가능한 값의 목록은 여전히 알려져 있지 않습니다.[156] (D = 69를 갖는) 노름-유클리드이 아닌 유클리드 도메인의 첫 번째 예제는 1994년에 발표되었습니다.[156] 1973년에서, 베인베르거(Weinberger)는 D > 0를 갖는 이차 정수 링이 유클리드인 것과 그것이 일반화된 리만 가설(generalized Riemann hypothesis)이 유지되는 조건 아래에서 주요 아이디얼 도메인(principal ideal domain)이 필요충분 조건임을 증명했습니다.[127]

Noncommutative rings

유클리드 알고리듬은 후르비츠 쿼터니언(Hurwitz quaternion)의 집합과 같은 일부 비-교환 링에 적용될 수 있습니다.[clarification needed][128] α와 β가 그러한 링으로부터 두 원소를 나타내는 것으로 놓습니다. 그들은 만약 링에서 ξ와 η의 일부 선택에 대해 α = ξδ 및 β = ηδ이면, 공통 오른쪽 약수 δ를 가집니다. 비슷하게, 그들은 만약 링에서 ξ와 η의 일부 선택에 대해 α = dξ 및 β = dη이면, 공통 왼쪽 약수를 가집니다. 곱셈은 교환적이 아니기 때문에, 유클리드 알고리듬의 두 가지 버전이 있으며, 하나는 오른쪽 약수에 대한 것이고 하나는 왼쪽 약수에 대한 것입니다.[128] 오른쪽 약수를 선택하면, 유클리드 알고리듬에 의해 gcd(α, β)를 찾는 첫 번째 단계는 다음과 같이 쓸 수 있습니다:

여기서 ψ0는 몫을 나타내고 ρ0는 나머지를 나타냅니다.[clarification needed] 이 방정식은 α와 β의 임의의 공통 오른쪽 약수는 마찬가지로 나머지 ρ0의 공통 약수임을 보였습니다. 왼쪽 약수에 대해 유사한 방정식은 두 선택과 함께 다음일 것입니다:

그 과정은 최대 공통 오른쪽 또는 왼쪽 약수가 식별될 때까지 위와 같이 반복됩니다. 유클리드 도메인에서 처럼, 나머지 ρ0의 "크기"는 β보다 엄격하게 더 작아야 하고, 그 알고리듬이 종료하는 것을 보장하는 것이 되도록, ρ0에 대해 오직 가능한 크기의 유한한 숫자가 있어야 합니다.[clarification needed][157]

GCD에 대한 대부분의 결과는 비-교환적 숫자에 대해 이어집니다.[clarification needed] 예를 들어, 베주의 항등식(Bézout's identity)은 오른쪽 gcd(α, β)가 α와 β의 선형 조합으로 표현될 수 있음을 말합니다.[158] 달리 말해서, 다음을 만족하는 숫자 σ와 τ가 있습니다:

왼쪽 GCD에 대해 유사한 항등식은 거의 같습니다:

베주의 항등식은 디오판토스 방정식을 풀기 위해 사용될 수 있습니다. 예를 들어, 모든 각 양의 정수가 네 제곱의 합으로 표현될 수 있다는 라그랑주 네-제곱 정리(Lagrange's four-square theorem)의 표준 증명 중 하나는 이러한 방법으로 쿼터니언 GCD를 기반으로 합니다.[157]

See also

  • Euclidean rhythm, a method for using the Euclidean algorithm to generate musical rhythms

Notes

  1. ^ Some widely used textbooks, such as I. N. Herstein's Topics in Algebra and Serge Lang's Algebra, use the term "Euclidean algorithm" to refer to Euclidean division
  2. ^ The phrase "ordinary integer" is commonly used for distinguishing usual integers from Gaussian integers, and more generally from algebraic integers.

References

  1. ^ Stark 1978, p. 16
  2. ^ Stark 1978, p. 21
  3. ^ LeVeque 1996, p. 32
  4. ^ LeVeque 1996, p. 31
  5. ^ Grossman, J. W. (1990). Discrete Mathematics. New York: Macmillan. p. 213. ISBN 0-02-348331-8.
  6. ^ a b Schroeder 2005, pp. 21–22
  7. ^ Schroeder 2005, p. 19
  8. ^ Ogilvy, C. S.; Anderson, J. T. (1966). Excursions in number theory. New York: Oxford University Press. pp. 27–29.
  9. ^ a b Schroeder 2005, pp. 216–219
  10. ^ a b LeVeque 1996, p. 33
  11. ^ Stark 1978, p. 25
  12. ^ Ore 1948, pp. 47–48
  13. ^ Stark 1978, p. 18
  14. ^ Stark 1978, pp. 16–20
  15. ^ Knuth 1997, p. 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, pp. 319–320
  20. ^ Knuth 1997, pp. 318–319
  21. ^ Stillwell 1997, p. 14
  22. ^ a b Ore 1948, p. 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, p. 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 Stillwell 1997, p. 31
  34. ^ a b Tattersall 2005, p. 70
  35. ^ Rosen 2000, pp. 86–87
  36. ^ Ore 1948, pp. 247–248
  37. ^ Tattersall 2005, pp. 72, 184–185
  38. ^ Saunderson, Nicholas (1740). The Elements of Algebra in Ten Books. University of Cambridge Press. Retrieved 1 November 2016.
  39. ^ Tattersall 2005, pp. 72–76
  40. ^ a b Gauss, C. F. (1832). "Theoria residuorum biquadraticorum". Comm. Soc. Reg. Sci. Gött. Rec. 4. Reprinted in Gauss, C. F. (2011). "Theoria residuorum biquadraticorum commentatio prima". Werke. Vol. 2. Cambridge Univ. Press. pp. 65–92. doi:10.1017/CBO9781139058230.004. and Gauss, C. F. (2011). "Theoria residuorum biquadraticorum commentatio secunda". Werke. Vol. 2. Cambridge Univ. Press. pp. 93–148. doi:10.1017/CBO9781139058230.005.
  41. ^ Stillwell 1997, pp. 31–32
  42. ^ Lejeune Dirichlet 1894, pp. 29–31
  43. ^ Richard Dedekind in Lejeune Dirichlet 1894, Supplement XI
  44. ^ Stillwell 2003, pp. 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. 33 (4). Society for Industrial and Applied Mathematics. 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.
  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. ^ Rosen 2000, p. 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. ^ Rosen 2000, p. 81
  55. ^ Cohn 1962, p. 104
  56. ^ Rosen 2000, p. 91
  57. ^ Schroeder 2005, p. 23
  58. ^ Rosen 2000, pp. 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. ^ Stark 1978, pp. 26–36
  62. ^ a b Ore 1948, p. 44
  63. ^ Stark 1978, pp. 281–292
  64. ^ Rosen 2000, pp. 119–125
  65. ^ Schroeder 2005, pp. 106–107
  66. ^ Schroeder 2005, pp. 108–109
  67. ^ Rosen 2000, pp. 120–121
  68. ^ Stark 1978, p. 47
  69. ^ Schroeder 2005, pp. 107–109
  70. ^ Stillwell 1997, pp. 186–187
  71. ^ Schroeder 2005, p. 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. ^ Rosen 2000, pp. 143–170
  74. ^ Schroeder 2005, pp. 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. ^ Knuth 1997, pp. 369–371
  78. ^ 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: 1484–1509. arXiv:quant-ph/9508027. Bibcode:1995quant.ph..8027S. doi:10.1137/s0097539795293172.
  79. ^ Dixon, J. D. (1981). "Asymptotically fast factorization of integers". Math. Comput. 36 (153): 255–260. doi:10.2307/2007743. JSTOR 2007743.
  80. ^ Lenstra, H. W., Jr. (1987). "Factoring integers with elliptic curves". Annals of Mathematics. 126 (3): 649–673. doi:10.2307/1971363. JSTOR 1971363.{{cite journal}}: CS1 maint: multiple names: authors list (link)
  81. ^ Crandall & Pomerance 2001, pp. 225–349
  82. ^ Knuth 1997, pp. 380–384
  83. ^ Knuth 1997, pp. 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. As cited by 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: 401–419. doi:10.1006/hmat.1994.1031. {{cite journal}}: Invalid |ref=harv (help)
  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, pp. 257–261
  91. ^ a b c Crandall & Pomerance 2001, pp. 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, p. 344
  94. ^ Ore 1948, p. 45
  95. ^ a b Knuth 1997, p. 343
  96. ^ Mollin 2008, p. 21
  97. ^ LeVeque 1996, p. 35
  98. ^ Mollin 2008, pp. 21–22
  99. ^ Knuth 1997, p. 353
  100. ^ Knuth 1997, p. 357
  101. ^ Tonkov, T. (1974). "On the average length of finite continued fractions". Acta Arithmetica. 26: 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, p. 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, p. 355
  110. ^ Knuth 1997, p. 356
  111. ^ Knuth 1997, p. 352
  112. ^ Wagon, S. (1999). Mathematica in Action. New York: Springer-Verlag. pp. 335–336. ISBN 0-387-98252-3.
  113. ^ Cohen 1993, p. 14
  114. ^ Cohen 1993, pp. 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, pp. 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, p. 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. ^ Weber, K. (1995). "The accelerated GCD algorithm". ACM Trans. Math. Softw. 21: 111–122. doi:10.1145/200979.201042.
  121. ^ Sorenson, J. (1994). "Two fast GCD algorithms". J. Algorithms. 16: 110–144. doi:10.1006/jagm.1994.1006.
  122. ^ Schönhage, A. (1971). "Schnelle Berechnung von Kettenbruchentwicklungen". Acta Informatica (in German). 1 (2): 139–144. doi:10.1007/BF00289520.
  123. ^ 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.
  124. ^ 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.
  125. ^ 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.
  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. "On Euclidean rings of algebraic integers". Proc. Sympos. Pure Math. 24: 321–332.
  128. ^ a b c Stillwell 2003, pp. 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, pp. 37–46
  136. ^ Schroeder 2005, pp. 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 Stillwell 2003, pp. 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. ^ Stark 1978, p. 290
  145. ^ Cohn 1962, pp. 104–105
  146. ^ Lauritzen, Niels (2003). Concrete Abstract Algebra: From Numbers to Gröbner Bases. Cambridge University Press. p. 130. ISBN 9780521534109. {{cite book}}: Invalid |ref=harv (help)
  147. ^ Lauritzen (2003), p. 132
  148. ^ Lauritzen (2003), p. 161
  149. ^ a b Sharpe, David (1987). Rings and Factorization. Cambridge University Press. p. 55. ISBN 9780521337182. {{cite book}}: Invalid |ref=harv (help)
  150. ^ Sharpe (1987), p. 52
  151. ^ Lauritzen (2003), p. 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. ^ Cohn 1962, pp. 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. 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.

Bibliography

External links

Wikimedia Commons has media related to Euclidean algorithm.

Retrieved from "https://dawoum.duckdns.org/w/index.php?title=Euclidean_algorithm&oldid=84614"