Greatest common divisor

수학(mathematics)에서, 모두 비-영인, 둘 이상 정수(integer)의 최대 공통 약수(greatest common divisor, 또는 줄여서 gcd)는 각 정수를 나누는 최대 양의 정수입니다. 예를 들어, 8과 12의 gcd는 4입니다.^[1]^[2]

이름 "최대 공통 약수"에서, 형용사 "최대(greatest)"는 "가장 높음(highest)"으로 대체될 수 있고, 단어 "약수"는 "인소"로 대체될 수 있으므로, 다른 이름은 최대 공통 인수(greatest common factor 또는 줄여서 gcf), 등을 포함합니다.^[3]^[4]^[5]^[6] 역사적으로, 같은 개념에 대해 다른 이름은 최대 공통 측정(greatest common measure)을 포함해 왔습니다. ^[7]

이 개념은 다항식 (다항식 최대 공약수(Polynomial greatest common divisor) 참조) 및 다른 교환적 링 (아래 참조)로 확장될 수 있습니다.

Overview

Definition

두 개의 비-영 정수(integer) $a$ 와 $b$ 의 최대 공통 약수 (greatest common divisor, 줄여서 GCD)는 $d$ 가 $a$ 와 $b$ 둘 다의 약수(divisor)임을 만족하는 가장 큰 양의 정수(positive integer) $d$ 입니다; 즉, $a = de$ 와 $b = df$ 를 만족하는 정수 $e$ 와 $f$ 가 있고, $d$ 는 그러한 정수 중 가장 큰 값입니다. $a$ 와 $b$ 의 GCD는 일반적으로 $gcd(a, b)$ 로 표시됩니다.^[8]

이 정의는 역시 $a$ 와 $b$ 중 하나가 0일 때에도 적용됩니다. 이 경우에서, GCD는 비-영 정수의 절댓값입니다: $gcd(a, 0) = gcd(0, a) = | a |$ . 이 경우는 유클리드 알고리듬의 종료 단계(Euclidean algorithm)로서 중요합니다.

위의 정의는 $gcd(0, 0)$ 를 정의하는 데 사용될 수 없는데, 왜냐하면 $0 \times n = 0$ 이고, 영은 따라서 최대 약수를 가지지 않습니다. 어쨌든, 영은 만약 최대가 나눔가능성 관계의 문맥에서 이해되면 그것 자체 최대 약수이므로, $gcd(0, 0)$ 는 공통적으로 0으로 정의됩니다. 이것은 GCD에 대해 보통의 항등식, 특히 베주의 항등식(Bézout's identity), 즉 $gcd(a, b)$ 가 ${a, b}$ 로 같은 아이디얼(ideal)을 생성함을 보존합니다.^[9]^[10]^[11] 이 규칙은 많은 컴퓨터 대수 시스템(computer algebra system)에서 따릅니다.^[12] 그럼에도 불구하고, 일부 저자는 $gcd(0, 0)$ 을 정의되지 않은 상태로 둡니다.^[13]

$a$ 와 $b$ 의 GCD는 나눔가능성(divisibility)의 준순서 관계(preorder relation)에서 최대 양의 공통 약수입니다. 이것은 $a$ 와 $b$ 의 공통 약수가 정확히 그것들의 GCD의 약수임을 의미합니다. 이것은 공통적으로 유클리드의 보조정리(Euclid's lemma), 산술의 기본 정리(fundamental theorem of arithmetic), 또는 유클리드 알고리듬(Euclidean algorithm)을 사용함으로써 증명됩니다. 이것은 GCD 개념의 일반화에 사용되는 "최대"의 의미입니다.

Example

54와 24의 최대 공통 약수는 무엇입니까?

숫자 54는 여러 다른 방법으로 두 정수의 곱으로 표현될 수 있습니다:

54\times 1=27\times 2=18\times 3=9\times 6.\,

따라서 54의 약수는 다음입니다: $1,2,3,6,9,18,27,54.\,$

비슷하게, 24의 약수는 다음입니다: $1,2,3,4,6,8,12,24.\,$

이들 두 목록이 공통으로 공유하는 숫자는 54와 24의 공통 약수입니다:

1,2,3,6.\,

이들의 가장 큰 것은 6입니다. 즉, 54와 24의 최대 공통 약수입니다. 우리는 다음을 씁니다:

\gcd(54,24)=6.\,

Coprime numbers

두 숫자는 만약 그들의 최대 공통 약수가 1과 같으면, 상대적으로 소수 또는 서로소(coprime)라고 불립니다. 예를 들어, 9와 28은 상대적으로 소수입니다.

A geometric view

"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.

예를 들어, 24x60 직사각형 넓이는 1x1 정사각형, 2x2 정사각형, 3x3 정사각형, 4x4 정사각형, 6x6 정사각형 또는 12x12 정사각형의 격자로 나눌 수 있습니다. 그러므로, 12는 24와 60의 최대 공통 약수입니다. 24x60 직사각형 넓이는 12x12 정사각형의 격자로 나눌 수 있으며, 하나의 가장자리는 두 정사각형 (24/12 = 2)이 있고 다른 것은 다섯 (60/12 = 5)이 있습니다.

Applications

Reducing fractions

최대 공통 약수는 분수(fraction)를 가장 낮은 항으로 줄이는 것에 유용합니다. 예를 들어, gcd(42, 56) = 14이므로,

{\frac {42}{56}}={\frac {3\cdot 14}{4\cdot 14}}={\frac {3}{4}}.

Least common multiple

최대 공통 약수는, 최대 공통 약수가 알려져 있을 때, 다음 관계를 사용하여, 두 숫자의 최소 공통 배수를 구하기 위해 사용될 수 있습니다:

\operatorname {lcm} (a,b)={\frac {|a\cdot b|}{\operatorname {gcd} (a,b)}}.

Calculation

Using prime factorizations

최대 공통 약수는 다음 예제와 같이 두 숫자의 소수 인수분해(prime factorization)를 결정하고 약수를 비교함으로써 계산될 수 있습니다: gcd(18, 84)를 계산하기 위해, 우리는 소수 인수분해 18 = 2 · 3² 및 84 = 2² · 3 · 7를 찾고 두 표현의 "중복"은 2 · 3입니다; 따라서 gcd(18, 84) = 6입니다. 실제로, 이 방법은 작은 숫자에 대해 오직 실행할 수 있습니다; 소수 인수분해를 계산하는 것은 일반적으로 너무 오래 걸립니다.

다음은 벤 다이어그램(Venn diagram)으로 표시된 또 다른 구체적인 예제입니다. 48과 180의 최대 공통 약수를 찾는 것을 희망한다고 가정합니다. 먼저, 두 숫자의 소수 인수분해를 찾습니다:

48 = 2 × 2 × 2 × 2 × 3,

180 = 2 × 2 × 3 × 3 × 5.

그들이 공통적으로 공유하는 것은 두 개의 "2"와 하나의 "3"입니다:

^[14]

최소 공통 배수 = 2 × 2 × ( 2 × 2 × 3 ) × 3 × 5 = 720

최대 공통 약수 = 2 × 2 × 3 = 12.

Euclid's algorithm

Animation showing an application of the Euclidean algorithm to find the greatest common divisor of 62 and 36, which is 2.

훨씬 더 효율적인 방법은 유클리드 알고리듬(Euclidean algorithm)이며, 긴 나눗셈(long division)과 같은 나눗셈 알고리듬(division algorithm)을 두 숫자의 gcd가 그들의 차이를 나눈다는 관찰과 함께 조합으로 사용합니다. gcd(48,18)을 계산하기 위해, 48을 18로 나누면 몫 2와 나머지 12를 얻습니다. 그런-다음 18을 12로 나누면 몫 1과 나머지 6을 얻습니다. 그런-다음 12를 6으로 나누면 0의 나머지를 얻으며, 이것은 6이 gcd임을 의미합니다. 우리는 나머지가 0에 도달했을 때의 주의를 제외하고 각 단계에서 몫을 무시하고, 답에 도달했음을 알립니다. 공식적으로, 그 알고리듬은 다음으로 설명될 수 있습니다:

\gcd(a,0)=a

\gcd(a,b)=\gcd(b,a\,\mathrm {mod} \,b)

,

여기서

a\,\mathrm {mod} \,b=a-b\left\lfloor {a \over b}\right\rfloor

.

만약 인수가 둘 다 영보다 크면, 그 알고리듬은 다음과 같은 보다 기본 항에서 쓸 수 있습니다:

\gcd(a,a)=a

,

\gcd(a,b)=\gcd(a-b,b)\quad ,

if a > b

\gcd(a,b)=\gcd(a,b-a)\quad ,

if b > a

Lehmer's GCD algorithm

레머의 알고리듬은 유클리드의 알고리듬에 의해 생성된 초기 몫이 오직 처음 몇 자릿수를 기초하여 결정될 수 있다는 관찰에 기초합니다; 이것은 컴퓨터 단어(computer word)보다 더 큰 숫자에 대해 유용합니다. 본질적으로, 우리는 초기 자릿수를 추출하며, 전형적으로 하나 또는 두 개의 컴퓨터 단어를 형성하고, 몫이 원래 숫자로 얻어질 수 있는 것과 같다는 것이 보장되는 한, 유클리드 알고리듬을 이들 더 작은 숫자로 실행합니다. 그들 몫은 원래의 숫자를 줄이기 위해 한 번에 그들 모두를 사용하는 것에 대해, 작은 2x2 변환 행렬 (즉 단일-단어 정수의 행렬)로 수집됩니다. 이 과정은 숫자가 이진 알고리듬 (아래 참조)이 보다 효율적인 크기를 가질 때까지 반복됩니다.

이 알고리듬은 속력을 향상시키는데, 왜냐하면 그것은 매우 많은 큰 숫자에 대한 연산의 숫자를 줄이고 대부분의 연산에 대해 하드웨어 산술의 속력을 사용할 수 있기 때문입니다. 실제로, 대부분의 몫은 매우 작으므로, 유클리드 알고리듬의 공정한 단계의 숫자는 단일-단어 정수의 2x2 행렬로 수집될 수 있습니다. 레마의 알고리듬이 너무 큰 몫을 만나면, 그것은 큰 숫자의 유클리드 나눗셈(Euclidean division)과 함께, 유클리드 알고리듬의 하나의 반복으로 되돌아가야 합니다.

Binary GCD algorithm

이진 GCD 알고리듬은 2로 뺄셈과 나눗셈을 오직 사용합니다. 방법은 다음과 같습니다: a와 b를 두 비-음 정수로 놓습니다. 정수 d를 0으로 놓습니다. 다섯 가능성이 있습니다:

a = b.

gcd(a, a) = a이기 때문에, 원했던 gcd는 a × 2^d입니다 (왜냐하면 a와 b가 다른 경우에서 변경되고, d는 a와 b가 다음 단계에서 둘 다 2로 나누어진 횟수의 숫자를 기록하며, 최기 쌍의 gcd는 a와 2^d의 곱이기 때문입니다).

a와 b 둘 다가 짝수입니다.

그때에 2는 공통 약수입니다. a와 b 둘 다를 2로 나누고, 2가 공통 약수인 횟수의 숫자를 기록하기 위해 d를 1씩 증가시키고 계속합니다.

a는 짝수이고 b는 홀수입니다.

그때에 2는 공통 약수가 아닙니다. a를 2로 나누고 계속합니다.

a는 홀수이고 b는 짝수입니다.

그때에 2는 공통 약수가 아닙니다. b를 2로 나누고 계속합니다.

a와 b 둘 다가 홀수입니다.

gcd(a,b) = gcd(b,a)이기 때문에, 만약 a < b이면 a와 b를 서로-바꿉니다. 숫자 c = a − b는 양수이고 a보다 작습니다. a와 b를 나누는 임의의 숫자는 반드시 역시 c를 나누므로 a와 b의 모든 각 공통 약수는 역시 b와 c의 공통 약수입니다. 비슷하게, a = b + c이고 b와 c의 모든 각 공통 약수는 역시 a와 b의 공통 약수입니다. 그래서 두 쌍 (a, b) 및 (b, c)는 같은 공통 약수를 가지고, 따라서 gcd(a,b) = gcd(b,c)입니다. 게다가, a와 b가 둘 다 홀수, c는 짝수이기 때문에, 그 과정은 쌍 (a, b)을 gcd의 변경없이 더 작은 숫자 (c/2, b)에 의해 대체와 함께 계속될 수 있습니다.

위의 단계들 각각은 그들을 비-음수로 남겨둔 채로 a와 b 중 적어도 하나를 감소시키고 그래서 횟수의 유한 숫자를 오직 반복될 수 있습니다. 따라서 결국 그 과정은 a = b, 중지하는 경우를 초래합니다. 그런-다음 gcd는 a × 2^d입니다.

예제: (a, b, d) = (48, 18, 0) → (24, 9, 1) → (12, 9, 1) → (6, 9, 1) → (3, 9, 1) → (3, 3, 1) ; 원래 gcd는 따라서 2^d = 2¹와 a= b= 3의 곱 6입니다.

이진 GCD 알고리듬은 이진 컴퓨터에서 구현하는 것이 특히 쉽습니다. 그것의 계산 복잡도(computational complexity)는 다음입니다:

O((\log a+\log b)^{2})

계산 복잡도는 보통 입력의 길이 $n$ 의 관점에서 주어집니다. 여기서, 이 길이는 $n=\log a+\log b$ 이고 복잡도는 따라서 다음입니다:

O(n^{2})

.

Other methods

만약 a와 b가 둘 다 비-영이면, a와 b의 최대 공통 약수는 a와 b의 최소 공통 배수(least common multiple, 줄여서 lcm)을 사용함으로써 계산될 수 있습니다:

\gcd(a,b)={\frac {|a\cdot b|}{\operatorname {lcm} (a,b)}}

,

그러나 보다 공통적으로 lcm은 gcd로터 계산됩니다.

토메 함수(Thomae's function) f를 사용하여,

\gcd(a,b)=af\left({\frac {b}{a}}\right),

이것은 a와 b를 유리수(rational number) 또는 정수-비율-가능한(commensurable) 실수로 일반화됩니다.

키이스 슬래빈(Keith Slavin)은 홀수 a ≥ 1에 대해 다음임을 보였습니다:

\gcd(a,b)=\log _{2}\prod _{k=0}^{a-1}(1+e^{-2i\pi kb/a})

이것은 복소수 b에 대해 평가될 수 있는 함수입니다.^[15] 볼프강 슈람(Wolfgang Schramm)은 다음임을 보였습니다:

\gcd(a,b)=\sum \limits _{k=1}^{a}\exp(2\pi ikb/a)\cdot \sum \limits _{d\left|a\right.}{\frac {c_{d}(k)}{d}}

는 모든 양의 정수 a에 대해 변수 b에서 전체 함수(entire function)이며 여기서 c_d(k)는 라마누젠의 합(Ramanujan's sum)입니다.^[16]

Complexity

최대 공통 약수의 계산의 계산 복잡도(computational complexity)는 널리 연구되어 왔습니다.^[17] 만약 우리가 유클리드 알고리듬(Euclidean algorithm)과 곱셈과 나눗셈에 대해 기본 알고리듬을 사용하면, 많아야 $n$ 비트(bit)의 두 정수의 최대 공통 약수의 계산은 $O(n^{2})$ 입니다. 이것은 최대 공통 약수는, 상수 인수까지, 곱셈과 같은 복잡도를 가집니다.

어쨌든, 만약 빠른 곱셈 알고리듬(multiplication algorithm)이 사용되면, 우리는 복잡도를 개선하는 것에 대해 유클리드 알고리듬을 수정할 수 있지만, 최대 공통 약수의 계산은 곱셈보다 더 느리게 됩니다. 보다 정확하게, 만약 $n$ 비트의 두 정수의 곱셈이 $T (n)$ 의 시간이 걸리면, 최대 공통 약수에 대해 가장-빠른 알려진 알고리듬은 복잡도 $O\left(T(n)\log n\right)$ 를 가집니다. 이것은 가장-빠른 알려진 알고리듬이 $O\left(n\,(\log n)^{2}\log \log n\right)$ 의 복잡도를 가짐을 의미합니다.

이전 복잡도는 보통 계산의 모델(models of computation), 특히 멀티-테이프 튜링 기계(multitape Turing machine) 및 무작위-접근 기계(random-access machine)에 대해 유효합니다.

최대 공통 약수의 계산은 준-선형 시간(quasilinear time)에서 해결될 수 있는 문제의 클래스에 따라서 속합니다. 포르티오리(fortiori), 해당하는 의사-결정 문제(decision problem)는 다항식 시간에서 해결될 수 있는 문제의 클래스 P에 속합니다. GCD 문제는 NC에 있는 것으로 알려져 있지 않고, 따라서 그것을 효율적으로 병렬화(parallelize)할 수 있는 알려진 방법이 없습니다; 또한 P-완전(P-complete)으로 알려져 것이 없으며, 이것은 GCD 계산을 효율적으로 병렬화할 수 없을 것임을 의미합니다. Shallcross et al.은 관련된 문제 (EUGCD, 유클리드 알고리듬 중 발생하는 나머지 수열을 결정하는 것)가 두 변수를 갖는 정수 선형 프로그래밍(integer linear programming)의 문제와 NC-동등임을 보여주었습니다; 만약 문제가 NC에 있거나, P-완전이면 다른 것도 마찬가지입니다.^[18] NC가 NL에 포함되므로, 심지어 비-결정적 튜링 기계에 대해, GCD 계산을 위한 공간-효율적인 알고리듬이 존재하는지 여부도 역시 알 수 없습니다.

비록 그 문제가 NC에 있는 것은 아니지만, 유클리드 알고리듬보다 점근적으로 더 빠른(asymptotically faster) 병렬 알고리듬이 존재합니다; 가장-빠른 알려진 결정론적 알고리듬은 Chor 및 Goldreich에 의해 것이며, 이것은 (CRCW-PRAM 모델에서) $n 1+ε$ 프로세서로 함께 $O (n /log n)$ 시간에서 문제를 해결할 수 있습니다.^[19] 무작위 알고리듬(randomized algorithm)은 $\exp \left(O\left({\sqrt {n\log n}}\right)\right)$ 프로세서에서 $O ((log n) 2)$ 시간 내에 그 문제를 해결할 수 있습니다.^{[clarification needed]} (이것은 초-다항식(superpolynomial)입니다).^[20]

Properties

a와 b의 모든 각 공통 약수는 gcd(a, b)의 약수입니다.
gcd(a, b)는, 여기서 a와 b는 둘 다 비-영이며, 형식 d = a⋅p + b⋅q에서 쓸 수 있는 가장-작은 양의 정수 d로 대안적으로 및 동등하게 정의될 수 있으며, 여기서 p와 q는 정수입니다. 이 표현은 베주의 항등식(Bézout's identity)이라고 불립니다. 이와 같은 숫자 p와 q는 확장된 유클리드 알고리듬(extended Euclidean algorithm)으로 계산될 수 있습니다.
a ≠ 0에 대해, gcd(a, 0) = |a|인데, 왜냐하면 임의의 숫자는 0의 약수이고, a의 최대 약수는 |a|입니다.^[2]^[5] 이것은 보통 유클리드 알고리듬에서 기본 경우로 사용됩니다.
만약 a가 곱 b⋅c를 나누고, gcd(a, b) = d이면, a/d는 c를 나눕니다.
만약 m이 비-음의 정수이면, gcd(m⋅a, m⋅b) = m⋅gcd(a, b)입니다.
만약 m이 임의의 정수이면, gcd(a + m⋅b, b) = gcd(a, b)입니다.
만약 m이 a와 b의 양의 공통 약수이면, gcd(a/m, b/m) = gcd(a, b)/m입니다.
gcd는 다음 의미에서 곱셈적 함수(multiplicative function)입니다: 만약 a₁와 a₂가 상대적으로 소수이면, gcd(a₁⋅a₂, b) = gcd(a₁, b)⋅gcd(a₂, b)입니다. 특히, gcd가 양의 정수 값 함수임을 회상하면 우리가 gcd(a, b⋅c) = 1임을 얻는 것과 gcd(a, b) = 1 및 gcd(a, c) = 1인 것은 필요충분 조건입니다.
gcd는 교환적(commutative) 함수: gcd(a, b) = gcd(b, a)입니다.
gcd는 결합적(associative) 함수: gcd(a, gcd(b, c)) = gcd(gcd(a, b), c)입니다.
만약 a₁, a₂, . . . , a_r의 어떤 것도 영이 아니면, gcd( a₁, a₂, . . . , a_r ) = gcd( gcd( a₁, a₂, . . . , a_r-1 ), a_r )입니다.^[21]^[22]
gcd(a, b)는 최소 공통 배수(least common multiple) lcm(a, b)와 밀접하게 관련됩니다: 우리는 다음을 가집니다:
gcd(a, b)⋅lcm(a, b) = |a⋅b|.

이 공식은 최소 공통 배수를 계산하기 위해 종종 사용됩니다: 우리는 먼저 유클리드의 알고리듬으로 gcd를 계산하고 그런-다음 주어진 숫자의 곱을 그들의 gcd로 나눕니다.

분배성(distributivity)의 다음 버전은 참을 유지시킵니다:
gcd(a, lcm(b, c)) = lcm(gcd(a, b), gcd(a, c))

lcm(a, gcd(b, c)) = gcd(lcm(a, b), lcm(a, c)).
만약 우리가 a = p₁^e₁ p₂^e₂ ⋅⋅⋅ p_m^e_m 및 b = p₁^f₁ p₂^f₂ ⋅⋅⋅ p_m^f_m의 고유한 소수 인수분해를 가지면, 여기서 e_i ≥ 0 및 f_i ≥ 0이며, a와 b의 gcd는 다음입니다:
gcd(a,b) = p₁^{min(e₁,f₁)} p₂^{min(e₂,f₂)} ⋅⋅⋅ p_m^min(e_m,f_m).
gcd(0, 0) = 0 및 lcm(0, 0) = 0을 정의하는 것이 때때로 유용한데, 왜냐하면 그때에 자연수(natural number)는 gcd가 충족되고 lcm이 결합 연산으로 완전(complete) 분배 격자(distributive lattice)가 되기 때문입니다.^[23] 그 정의의 확장은 아래 주어진 교환적 링에 대해 일반화와 역시 호환됩니다.
데카르트 좌표 시스템(Cartesian coordinate system)에서, gcd(a, b)는 점 (0, 0)와 (a, b)를 연결하는 직진 선분(line segment) 위에 정수 좌표를 갖는 점 사이의 선분의 숫자로 해석될 수 있습니다.
비-음의 정수 a와 b에 대해, 여기서 a와 b는 둘 다 영이 아니며, 밑수 n에서 유클리드 알고리듬을 고려함으로써 입증할 수 있습니다:^[24]
gcd(n^a − 1, n^b − 1) = n^gcd(a,b) − 1.
오일러의 토션트 함수(Euler's totient function)를 포함하는 항등식(identity):
$\gcd(a,b)=\sum _{k|a{\text{ and }}k|b}\varphi (k).$

Probabilities and expected value

1972년에, 제임스 니만(James E. Nymann)은 {1, ..., n}에서 독립적으로 및 균등하게 선택된, k 정수가, n이 무한대로 갈 때, 확률 1/ζ(k)와 서로소이며, 여기서 ζ는 리만 제타 함수(Riemann zeta function)를 참조합니다.^[25] (유도에 대해 서로소(coprime)를 참조하십시오.) 이 결과는 1987년에 k 무작위 정수가 최대 공통 약수 d를 가질 확률이 d^−k/ζ(k)임을 보여주기 위해 확장되었습니다.^[26]

이 정보를 사용하여, 최대 공통 약수 함수의 기댓값(expected value)은 k = 2일 때 존재하지 않는 것을 알 수 있습니다. 이 경우에서 gcd가 d와 같을 확률은 d⁻²/ζ(2)이고, ζ(2) = π²/6이므로 우리는 다음을 가집니다:

\mathrm {E} (\mathrm {2} )=\sum _{d=1}^{\infty }d{\frac {6}{\pi ^{2}d^{2}}}={\frac {6}{\pi ^{2}}}\sum _{d=1}^{\infty }{\frac {1}{d}}.

이 마지막 합은 조화 급수(harmonic series)이며, 이것은 발산합니다. 어쨌든, k ≥ 3일 때, 기댓값은 잘-정의되고 위의 논증에 의해, 그것은 다음입니다:

\mathrm {E} (k)=\sum _{d=1}^{\infty }d^{1-k}\zeta (k)^{-1}={\frac {\zeta (k-1)}{\zeta (k)}}.

k = 3에 대해, 이것은 1.3684과 근사적으로 같습니다. k = 4에 대해, 그것은 근사적으로 1.1106입니다.

In commutative rings

최대 공통 약수의 개념은, 비록 일반적으로 모든 각 원소의 쌍에 대해 하나씩 존재할 필요가 없을지라도, 임의의 교환적 링(commutative ring)의 원소에 대해 보다 일반적으로 정의될 수 있습니다.

만약 $R$ 이 교환적 링이고, $a$ 와 $b$ 가 $R$ 안에 있으면, $R$ 의 원소 $d$ 는, 만약 그것이 $a$ 와 $b$ 둘 다를 나누면 (즉, 만약 d·x = a 및 d·y = b를 만족하는 $R$ 안에 원소 $x$ 및 $y$ 가 있으면), $a$ 와 $b$ 의 공통 약수라고 불립니다. 만약 $d$ 가 $a$ 와 $b$ 의 공통 약수이고, $a$ 와 $b$ 의 모든 각 공통 약수가 $d$ 를 나누면, $d$ 는 $a$ 와 $b$ 의 최대 공통 약수라고 불립니다.

이 정의와 함께, 두 원소 $a$ 와 $b$ 는 여러 최대 공통 약수를 매우 잘 갖거나, 전혀 갖지 않을 수 있습니다. 만약 $R$ 이 정수 도메인(integral domain)이면, $a$ 와 $b$ 의 임의의 두 gcd는 결합 원소(associate elements)여야 하는데, 왜냐하면 정의에 의해 둘 중 하나가 다른 하나를 나누어야 하기 때문입니다; 실제로 만약 gcd가 존재하면, 그것의 결합 중 임의의 하나는 마찬가지로 gcd입니다. gcd의 존재는 임의의 정수 도메인에서 보장되지 않습니다. 어쨌든, 만약 $R$ 이 고유한 인수분해 도메인(unique factorization domain)이면, 임의의 두 원소는 gcd를 가지고, 보다 일반적으로 이것은 gcd 도메인(gcd domain)에서 참입니다. 만약 $R$ 이 유클리드 나눗셈이 알고리듬적으로 제공되는 유클리드 도메인(Euclidean domain)이면 (예를 들어, R = F[X]에 대한 경우에서 처럼, 여기서 $F$ 가 필드(field), 또는 $R$ 이 가우스 정수(Gaussian integer)의 링일 때), 최대 공통 약수는 나눗셈 절차에 기초한 유클리드 알고리듬의 형식을 사용하여 계산될 수 있습니다.

다음은 gcd를 가지지 않는 두 원소를 갖는 정수 도메인의 예제입니다:

R=\mathbb {Z} \left[{\sqrt {-3}}\,\,\right],\quad a=4=2\cdot 2=\left(1+{\sqrt {-3}}\,\,\right)\left(1-{\sqrt {-3}}\,\,\right),\quad b=\left(1+{\sqrt {-3}}\,\,\right)\cdot 2.

원소 2와 1 + √−3은 두 최고 공통 약수(maximal common divisor)입니다 (즉, 2의 배수인 임의의 공통 약수는 2와 결합적이며, 같은 것이 1 + √−3에 대해 유지되지만, 그들은 결합적이지 않으므로, $a$ 와 $b$ 의 최대 공통 약수가 아닙니다).

베주의 속성에 해당하면, 우리는, 임의의 교환 링에서, 형식 pa + qb의 원소의 모음을 고려할 수 있으며, 여기서 $p$ 와 $q$ 는 링에 걸쳐 있습니다. 이것은 $a$ 와 $b$ 에 의해 생성된 아이디얼(ideal)이고, 간단히 (a, b)로 표시됩니다. 그의 아이디얼의 모두가 주요인 링 (주요 아이디얼 도메인(principal ideal domain) 또는 PID)에서, 이 아이디얼은 일부 링 원소 d의 배수의 집합과 동일할 것입니다; 그때에 이 $d$ 는 $a$ 와 $b$ 의 최대 공통 약수입니다. 그러나 아이디얼 (a, b)는 심지어 $a$ 와 $b$ 의 최대 공통 약수가 아닐 때 유용할 수 있습니다. (실제로 에른스트 쿠머(Ernst Kummer)는, 비록 그가 링-이론적 용어로부터, 어떤 가설적, 또는 아이디얼, 링 원소 $d$ 의 배수의 집합으로 그것을 구상했을지라도, 페르마의 마지막 정리(Fermat's Last Theorem)의 취급에서 gcd에 대해 대체물로 이 아이디얼을 사용했습니다.

Notes

^ ^a ^b Long (1972, p. 33)
^ ^a ^b ^c Pettofrezzo & Byrkit (1970, p. 34)
^ Kelley, W. Michael (2004), The Complete Idiot's Guide to Algebra, Penguin, p. 142, ISBN 9781592571611.
^ Jones, Allyn (1999), Whole Numbers, Decimals, Percentages and Fractions Year 7, Pascal Press, p. 16, ISBN 9781864413786.
^ ^a ^b ^c Hardy & Wright (1979, p. 20)
^ Some authors present greatest common denominator as synonymous with greatest common divisor. This contradicts the common meaning of the words that are used, as denominator refers to fractions, and two fractions do not have any greatest common denominator (if two fractions have the same denominator, one obtains a greater common denominator by multiplying all numerators and denominators by the same integer).
^ Barlow, Peter; Peacock, George; Lardner, Dionysius; Airy, Sir George Biddell; Hamilton, H. P.; Levy, A.; De Morgan, Augustus; Mosley, Henry (1847), Encyclopaedia of Pure Mathematics, R. Griffin and Co., p. 589.
^ Some authors use $(a, b)$ ,^[1]^[2]^[5] but this notation is often ambiguous. Andrews (1994, p. 16) explains this as: "Many authors write (a,b) for $g.c.d.(a, b)$ . We do not, because we shall often use (a,b) to represent a point in the Euclidean plane."
^ Thomas H. Cormen, et al., Introduction to Algorithms (2nd edition, 2001) ISBN 0262032937, p. 852
^ Bernard L. Johnston, Fred Richman, Numbers and Symmetry: An Introduction to Algebra ISBN 084930301X, p. 38
^ Martyn R. Dixon, et al., An Introduction to Essential Algebraic Structures ISBN 1118497759, p. 59
^ e.g., Wolfram Alpha calculation and Maxima
^ Jonathan Katz, Yehuda Lindell, Introduction to Modern Cryptography ISBN 1351133012, 2020, section 9.1.1, p. 45
^ Gustavo Delfino, "Understanding the Least Common Multiple and Greatest Common Divisor", Wolfram Demonstrations Project, Published: February 1, 2013.
^ Slavin, Keith R. (2008). "Q-Binomials and the Greatest Common Divisor". INTEGERS: The Electronic Journal of Combinatorial Number Theory. 8. University of West Georgia, Charles University in Prague: A5. Retrieved 2008-05-26.
^ Schramm, Wolfgang (2008). "The Fourier transform of functions of the greatest common divisor". INTEGERS: The Electronic Journal of Combinatorial Number Theory. 8. University of West Georgia, Charles University in Prague: A50. Retrieved 2008-11-25.
^ Knuth, Donald E. (1997). The Art of Computer Programming. Vol. 2: Seminumerical Algorithms (3rd ed.). Addison-Wesley Professional. ISBN 0-201-89684-2.
^ Shallcross, D.; Pan, V.; Lin-Kriz, Y. (1993). "The NC equivalence of planar integer linear programming and Euclidean GCD". 34th IEEE Symp. Foundations of Computer Science. pp. 557–564. {{cite book}}: External link in |chapterurl= (help); Unknown parameter |chapterurl= ignored (|chapter-url= suggested) (help)
^ Chor, B.; Goldreich, O. (1990). "An improved parallel algorithm for integer GCD". Algorithmica. 5 (1–4): 1–10. doi:10.1007/BF01840374.
^ Adleman, L. M.; Kompella, K. (1988). "Using smoothness to achieve parallelism". 20th Annual ACM Symposium on Theory of Computing. New York. pp. 528–538. doi:10.1145/62212.62264. ISBN 0-89791-264-0.{{cite book}}: CS1 maint: location missing publisher (link)
^ Long (1972, p. 40)
^ Pettofrezzo & Byrkit (1970, p. 41)
^ Müller-Hoissen, Folkert; Walther, Hans-Otto (2012), "Dov Tamari (formerly Bernhard Teitler)", in Müller-Hoissen, Folkert; Pallo, Jean Marcel; Stasheff, Jim (eds.), Associahedra, Tamari Lattices and Related Structures: Tamari Memorial Festschrift, Progress in Mathematics, vol. 299, Birkhäuser, pp. 1–40, ISBN 9783034804059. Footnote 27, p. 9: "For example, the natural numbers with gcd (greatest common divisor) as meet and lcm (least common multiple) as join operation determine a (complete distributive) lattice." Including these definitions for 0 is necessary for this result: if one instead omits 0 from the set of natural numbers, the resulting lattice is not complete.
^ Knuth, Donald E.; Graham, R. L.; Patashnik, O. (March 1994). Concrete Mathematics: A Foundation for Computer Science. Addison-Wesley. ISBN 0-201-55802-5.
^ Nymann, J. E. (1972). "On the probability that k positive integers are relatively prime". Journal of Number Theory. 4 (5): 469–473. doi:10.1016/0022-314X(72)90038-8.
^ Chidambaraswamy, J.; Sitarmachandrarao, R. (1987). "On the probability that the values of m polynomials have a given g.c.d." Journal of Number Theory. 26 (3): 237–245. doi:10.1016/0022-314X(87)90081-3.

References

Andrews, George E. (1994) [1971], Number Theory, Dover, ISBN 9780486682525
Hardy, G. H.; Wright, E. M. (1979), An Introduction to the Theory of Numbers (Fifth ed.), Oxford: Oxford University Press, ISBN 978-0-19-853171-5
Long, Calvin T. (1972), Elementary Introduction to Number Theory (2nd ed.), Lexington: D. C. Heath and Company, LCCN 77171950
Pettofrezzo, Anthony J.; Byrkit, Donald R. (1970), Elements of Number Theory, Englewood Cliffs: Prentice Hall, LCCN 71081766

External links

Greatest Common Measure: The Last 2500 Years, by Alexander Stepanov

[Long_1972_33-1] Long (1972, p. 33)

[Pettofrezzo_1970_34-2] Pettofrezzo & Byrkit (1970, p. 34)

[3] Kelley, W. Michael (2004), The Complete Idiot's Guide to Algebra, Penguin, p. 142, ISBN 9781592571611.

[4] Jones, Allyn (1999), Whole Numbers, Decimals, Percentages and Fractions Year 7, Pascal Press, p. 16, ISBN 9781864413786.

[Hardy&Wright_1979_20-5] Hardy & Wright (1979, p. 20)

[6] Some authors present greatest common denominator as synonymous with greatest common divisor. This contradicts the common meaning of the words that are used, as denominator refers to fractions, and two fractions do not have any greatest common denominator (if two fractions have the same denominator, one obtains a greater common denominator by multiplying all numerators and denominators by the same integer).

[7] Barlow, Peter; Peacock, George; Lardner, Dionysius; Airy, Sir George Biddell; Hamilton, H. P.; Levy, A.; De Morgan, Augustus; Mosley, Henry (1847), Encyclopaedia of Pure Mathematics, R. Griffin and Co., p. 589.

[8] Some authors use $(a, b)$ ,^[1]^[2]^[5] but this notation is often ambiguous. Andrews (1994, p. 16) explains this as: "Many authors write (a,b) for $g.c.d.(a, b)$ . We do not, because we shall often use (a,b) to represent a point in the Euclidean plane."

[9] Thomas H. Cormen, et al., Introduction to Algorithms (2nd edition, 2001) ISBN 0262032937, p. 852

[10] Bernard L. Johnston, Fred Richman, Numbers and Symmetry: An Introduction to Algebra ISBN 084930301X, p. 38

[11] Martyn R. Dixon, et al., An Introduction to Essential Algebraic Structures ISBN 1118497759, p. 59

[12] .g., Wolfram Alpha calculation and Maxima

[13] Jonathan Katz, Yehuda Lindell, Introduction to Modern Cryptography ISBN 1351133012, 2020, section 9.1.1, p. 45

[14] Gustavo Delfino, "Understanding the Least Common Multiple and Greatest Common Divisor", Wolfram Demonstrations Project, Published: February 1, 2013.

[15] Slavin, Keith R. (2008). "Q-Binomials and the Greatest Common Divisor". INTEGERS: The Electronic Journal of Combinatorial Number Theory. 8. University of West Georgia, Charles University in Prague: A5. Retrieved 2008-05-26.

[16] Schramm, Wolfgang (2008). "The Fourier transform of functions of the greatest common divisor". INTEGERS: The Electronic Journal of Combinatorial Number Theory. 8. University of West Georgia, Charles University in Prague: A50. Retrieved 2008-11-25.

[17] Knuth, Donald E. (1997). The Art of Computer Programming. Vol. 2: Seminumerical Algorithms (3rd ed.). Addison-Wesley Professional. ISBN 0-201-89684-2.

[18] Shallcross, D.; Pan, V.; Lin-Kriz, Y. (1993). "The NC equivalence of planar integer linear programming and Euclidean GCD". 34th IEEE Symp. Foundations of Computer Science. pp. 557–564. {{cite book}}: External link in |chapterurl= (help); Unknown parameter |chapterurl= ignored (|chapter-url= suggested) (help)

[19] Chor, B.; Goldreich, O. (1990). "An improved parallel algorithm for integer GCD". Algorithmica. 5 (1–4): 1–10. doi:10.1007/BF01840374.

[20] Adleman, L. M.; Kompella, K. (1988). "Using smoothness to achieve parallelism". 20th Annual ACM Symposium on Theory of Computing. New York. pp. 528–538. doi:10.1145/62212.62264. ISBN 0-89791-264-0.{{cite book}}: CS1 maint: location missing publisher (link)

[21] Long (1972, p. 40)

[22] Pettofrezzo & Byrkit (1970, p. 41)

[23] Müller-Hoissen, Folkert; Walther, Hans-Otto (2012), "Dov Tamari (formerly Bernhard Teitler)", in Müller-Hoissen, Folkert; Pallo, Jean Marcel; Stasheff, Jim (eds.), Associahedra, Tamari Lattices and Related Structures: Tamari Memorial Festschrift, Progress in Mathematics, vol. 299, Birkhäuser, pp. 1–40, ISBN 9783034804059. Footnote 27, p. 9: "For example, the natural numbers with gcd (greatest common divisor) as meet and lcm (least common multiple) as join operation determine a (complete distributive) lattice." Including these definitions for 0 is necessary for this result: if one instead omits 0 from the set of natural numbers, the resulting lattice is not complete.

[24] Knuth, Donald E.; Graham, R. L.; Patashnik, O. (March 1994). Concrete Mathematics: A Foundation for Computer Science. Addison-Wesley. ISBN 0-201-55802-5.

[nymann-25] Nymann, J. E. (1972). "On the probability that k positive integers are relatively prime". Journal of Number Theory. 4 (5): 469–473. doi:10.1016/0022-314X(72)90038-8.

[chid-26] Chidambaraswamy, J.; Sitarmachandrarao, R. (1987). "On the probability that the values of m polynomials have a given g.c.d." Journal of Number Theory. 26 (3): 237–245. doi:10.1016/0022-314X(87)90081-3.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]