최대 공약수

수학에서, 둘 이상의 정수의 최대공약수(GCD)는 모두 0이 아니며, 각각의 정수를 나누는 가장 큰 양의 정수이다.2개의 정수 x, y에 대해 x와 y의 ${\displaystyle 최대공약수}$는${\displaystyle }$gcd${\displaystyle (x,}$ $)\display\gcd(x,y$로 표시됩니다.예를 들어 8과 12의 GCD는 4입니다.${\displaystyle 즉,}$ ${\displaystyle \gcd }$(8,$=4${$displaystyle\gcd(8,12$)=$4$^[1][2]입니다.

"가장 큰 공통 약수"라는 이름에서 형용사 "가장 큰"은 "가장 높은"으로, "divisor"는 "factor"로 대체될 수 있으며, 다른 이름에 가장 높은 공통 계수(^[3][4][5][6]hcf) 등이 포함되도록 할 수 있다.역사적으로 동일한 개념의 다른 이름에는 가장 일반적인 ^[7]측정값이 포함되어 있습니다.

이 개념은 다항식(다항식 최대공약수 참조) 및 기타 가환환(아래 § 가환환 참조)으로 확장될 수 있습니다.

개요

정의.

0이 아닌 두 정수 a와 b의 최대공약수(GCD)는 d가 a와 b의 약수인 가장 큰 양의 정수 d이다. 즉, a = de와 b = df, d가 가장 큰 정수인 정수 e와 f가 있다.a와 b의 GCD는 일반적으로 gcd(a, b)^[8]로 표기된다.

이 정의는 a와 b 중 하나가 0인 경우에도 적용됩니다.이 경우, GCD는 0이 아닌 정수의 절대값이다: gcd(a, 0) = gcd(0, a) = a. 이 경우는 유클리드 알고리즘의 종료 단계로서 중요하다.

0 × n = 0이므로 위의 정의는 gcd(0, 0)의 정의에 사용할 수 없으며, 따라서 0은 최대 제수가 없다.그러나 최대값이 약수 관계에서 이해되는 경우 0은 그 자체의 최대 약수이므로 gcd(0, 0)는 일반적으로 0으로 정의됩니다.이를 통해 GCD, 특히 Bézout의 정체성, 즉 gcd(a, b)가 {a,^[9][10][11] b}와 동일한 이상을 생성한다.이 규약은 많은 컴퓨터 대수 ^[12]체계에 따른다.그러나 일부 저자는 gcd(0, 0)를 ^[13]정의하지 않은 상태로 둡니다.

a와 b의 GCD는 나눗셈의 전순서 관계에서 가장 큰 양의 공약수이다.즉, a와 b의 공통 제수가 정확히 GCD의 제수라는 것을 의미합니다.이것은 일반적으로 유클리드의 보조정리, 산술의 기본정리 또는 유클리드 알고리즘을 사용하여 증명된다.이것은 GCD 개념의 일반화에 사용되는 "가장 위대한"의 의미이다.

예

숫자 54는 여러 가지 다른 방법으로 두 정수의 곱으로 표현할 수 있습니다.

$({displaystyle 54\times 1=27\times 2=18\times 3=9\times 6})$

따라서 54의 전체 제수는${\displaystyle }$1,${\displaystyle 2}$, ${\displaystyle 3}$,${\displaystyle }$6,${\displaystyle 9}$, ${\displaystyle 18,}$ ${\displaystyle 27,}$ ${\displaystyle 54}$({$display$1,$2, 3, 9, 18, 27, 54$입니다. 마찬가지로 24의 제수는${\displaystyle }$1,${\displaystyle 2}$, ${\displaystyle 3}$,$4$,${\displaystyle 6}$, 8,$({display style$1,$2, 3$, 4,$6,$ 8,$12,$ 24$\})$입니다.이 두 개의 숫자는 다음과 같습니다.

$(\displaystyle 1,2,3,6).$

이 중 최대값은 6이므로 최대공약수이다.

$\displaystyle \gcd(54,24)=6.}$

두 숫자의 모든 제수를 이런 식으로 계산하는 것은 특히 많은 제수가 있는 큰 숫자의 경우 효율적이지 않습니다.보다 효율적인 방법은 ① 계산에서 설명합니다.

코프라임 번호

두 숫자는 최대공약수가 ^[14]1일 경우 상대적으로 소수, 즉 공약수라고 불립니다.예를 들어, 9와 28은 공존합니다.

기하학적 뷰

예를 들어 24x60의 직사각형 영역은 1x1의 정사각형, 2x2의 정사각형, 3x3의 정사각형, 4x4의 정사각형, 6x6의 정사각형 또는 12x12의 정사각형 그리드로 분할할 수 있습니다.따라서 12는 24와 60의 최대 공약수이다.따라서 24x60 직사각형 영역은 한 모서리를 따라 두 개의 정사각형(24/12 = 2)이 있고 다른 모서리를 따라 다섯 개의 정사각형(60/12 = 5)이 있는 12x12 정사각형의 그리드로 분할할 수 있습니다.

적용들

분수 감소

최대공약수는 분수를 최소항으로 ^[15]줄이는 데 유용합니다.예를 들어 gcd(42, 56) = 14 입니다.

${\displaystyle {\frac {42} {56)}=paramfrac {3\cdot 14}{4\cdot 14}=paramfrac {3}{4}.}$

최소공배수

둘 다 0이 아닌 두 정수의 최소공배수는 다음 관계를 사용하여 최대공약수로 계산할 수 있다.

${\displaystyle \operatorname {lcm}(a,b)=param frac {a\cdot b}{\operatorname {gcd}(a,b)}}.}$

계산

소인수 분해 사용

최대공약수는 두 숫자의 소인수를 결정하고 인자를 비교하여 계산할 수 있습니다.예를 들어, gcd(48, 180)를 계산하기 위해, 우리는 소인수분해 48 = 2⁴ · 3¹ · 3 및 180² = 2² · 3¹ · 5를 구한다. 그러면^min(4,2) GCD는 Ven 도표와 같이 2 · 3^min(1,2)0 · 5^min(0,1)1 = 12가² 된다.대응하는^max(4,2) LCM은 2 · 3^max(1,2) · 5^max(0,1) = 2⁴ · 3² · 5¹ = 720이다.

^[16]

실제로는 소수 인수분해를 계산하는 데 시간이 너무 오래 걸리기 때문에 이 방법은 작은 숫자에 대해서만 가능합니다.

유클리드의 알고리즘

최대공약수를 계산하기 위해 유클리드에 의해 도입된 방법은 a > b라는 두 양의 정수 a와 b가 주어졌을 때 a와 b의 공약수는 a - b와 b의 공약수와 같다는 사실에 기초한다.

그래서, 두 양의 정수의 최대공약수를 계산하는 유클리드의 방법은 큰 수를 숫자의 차이로 대체하고, 두 숫자가 같아질 때까지 이것을 반복하는 것이다: 그것이 그들의 최대공약수이다.

예를 들어 gcd(48,18)를 계산하려면 다음과 같이 진행됩니다.

$\displaystyle \displaystyle \gcd(48,18)\to \gcd(48,18)=\gcd(30,18)=\gcd(12,18)=\to \gcd(12,18)=\to \displaystyle \gcd(12,18)\to \gcd(6,18)\to\displaystyle\gcdisplaystyle\end { aligned}}$

따라서 gcd(48, 18) = 6입니다.

하나의 숫자가 다른 숫자보다 훨씬 클 경우 이 방법은 매우 느릴 수 있습니다.따라서 다음 변종이 일반적으로 선호됩니다.

유클리드 알고리즘

보다 효율적인 방법은 유클리드 알고리즘으로, 두 숫자 a와 b의 차이가 a의 나머지 유클리드 나눗셈(나머지 나눗셈이라고도 함)으로 대체되는 변형이다.

이 나머지를 mod b로 나타내면 알고리즘은 쌍이 (d, 0)이 될 때까지 (a, b)를 (b, mod b)로 반복적으로 치환한다.여기서 d는 최대공약수이다.

예를 들어 gcd(48,18)를 계산하려면 다음과 같이 계산합니다.

$\displaystyle {displaystyle}\gcd(48,18)\to\gcd(18,48 scdbmod {1}8)=\gcd(12,18 scdbmod {1}2)=\gcd(12,6),\to \gcd(6,18)={1}\to\to\to \gcdisplaystyland}\end { aligned}}$

다시 gcd(48, 18) = 6이 됩니다.

레머의 GCD 알고리즘

레머의 알고리즘은 유클리드의 알고리즘에 의해 생성된 초기 지분은 처음 몇 자리 숫자만을 기반으로 결정될 수 있다는 관찰에 기초한다; 이것은 컴퓨터 단어보다 큰 숫자에 유용하다.본질적으로, 한 두 개의 컴퓨터 워드를 형성하는 첫 번째 숫자를 추출하고, 원래의 숫자로 얻을 수 있는 것과 같은 지수를 보장한다면, 이 작은 숫자에 대해 유클리드의 알고리즘을 실행합니다.몫은 원래 숫자를 줄이기 위해 작은 2x2 변환 행렬(단일 단어 정수의 행렬)로 수집됩니다.이 프로세스는 바이너리 알고리즘(아래 참조)이 보다 효율적일 때까지 반복됩니다.

이 알고리즘은 매우 큰 수의 연산 수를 줄이고 대부분의 연산에 하드웨어 계산을 사용할 수 있기 때문에 속도를 향상시킵니다.사실, 대부분의 인용문들은 매우 작기 때문에, 유클리드 알고리즘의 상당한 수의 단계들이 단일 단어 정수의 2x2 행렬로 수집될 수 있다.레머의 알고리즘이 너무 큰 상수를 만나면, 큰 수의 유클리드 나눗셈을 가진 유클리드 알고리즘의 반복으로 돌아가야 한다.

이진 GCD 알고리즘

바이너리 GCD 알고리즘에서는 뺄셈과 2로 나누기만을 사용합니다.방법은 다음과 같습니다.a와 b를 음이 아닌 두 정수라고 하자.정수 d를 0으로 합니다.5가지 가능성이 있습니다.

• a = b.

gcd(a, a) = a로서 바람직한 GCD는 a × 2이다^d(다른 경우에는 a와 b가 변화하고, 다음 단계에서는 d가 a와 b를 모두 2로 나눈 횟수를 기록하므로 초기 쌍의 GCD는 a와^d 2의 곱이다).

• a와 b는 둘 다 짝수이다.

그럼 2는 공약수입니다.a와 b를 모두 2로 나누고 d를 1로 증가시켜 2가 공약수인 횟수를 기록하고 계속 진행합니다.

• 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는 짝수이므로, GCD를 변경하지 않고, 쌍(a, b)을 작은 수(c/2, b)로 치환해 처리를 계속할 수 있다.

위의 각 단계는 a와 b 중 적어도 하나를 감소시키고 음이 아닌 상태로 두므로 한정된 횟수만 반복할 수 있다.따라서 이 공정은 결국 a = b, 즉 중지 사례가 됩니다.그러면 GCD는 x 2입니다^d.

예: (a, b, d) = (48, 18, 0) → (24, 9, 1) → (12, 9, 1) → (3, 9, 1) → (3, 3, 1) 원래 GCD는 2 = 2¹ 및 a = 3의^d 곱 6이다.

바이너리 GCD 알고리즘은 바이너리 컴퓨터에 특히 쉽게 구현할 수 있습니다.계산의 복잡성은

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

계산의 복잡성은 보통 입력의 길이 n의 관점에서 주어진다.여기서 이 길이는 n $=$ ${\displaystyle \log }$ ${\displaystyle a}$+ log${\displaystyle \mathrm{bb}}$, {\$displaystyle$ n=\$log$ a$+\log$ b$,}$ 입니다.복잡도는 다음과 같습니다.

${\displaystyle O}$ ${\displaystyle (}$ ${\displaystyle {n\mathrm{}}^{}}$2$$) { $displaystyle$O ( $n^$ {2$}$)$$。

기타 방법

a와 b가 모두 0이 아닌 경우 a와 b의 최대공약수는 a와 b의 최소공배수(LCM)를 사용하여 계산할 수 있습니다.

${\displaystyle gcd}$ ${\displaystyle (a}$ ,${\displaystyle b}$ ) ${\displaystyle =}$ ${\displaystyle \frac{a}{}}$ ${\displaystyle \frac{\cdot \cdot }{b}}$ ${\displaystyle \frac{\mathrm{lcm}（}{}}$ ${\displaystyle \frac{a}{}}$,$$b ){ $displaystyle \gcd ( a$ , b ) =$scfrac { a$ \ $cdot$ b $}{$ \ $operatorname${ $lcm$} ($a$ , b )$\}$ ,

그러나 더 일반적으로 LCM은 GCD에서 계산된다.

Thomae의 함수 f를 사용하여

$(\displaystyle \gcd(a,b)=af\leftflac {b}{a}}\right),}$

이는 a와 b의 유리수 또는 환산 가능한 실수로 일반화된다.

Keith Slavin은 홀수 a : 1에 대해 다음을 보여주었다.

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

복합 ^[17]b에 대해 평가할 수 있는 함수입니다.볼프강 슈람이 보여준 것은

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

는 모든 양의 정수 a에 대한 변수 b의 전체 함수입니다. 여기서_d c(k)는 라마누잔의 [18]합입니다.

복잡성

최대공약수 연산의 계산 복잡성은 널리 ^[19]연구되어 왔다.곱셈과 나눗셈에 유클리드 알고리즘과 기본 알고리즘을 사용하는 경우, 최대 n비트의 두 정수의 최대공약수${\displaystyle }$계산은 O${\displaystyle {}^{}{n\mathrm{}}^{}}$ 2$).\displaystyle$ O$(n^{2})$가 됩니다.} 즉$$, 최대공약수의 계산은 정수까지 곱셈과 같은 복잡도를 가진다$.$

그러나 고속 곱셈 알고리즘을 사용하면 복잡도를 개선하기 위해 유클리드 알고리즘을 수정할 수 있지만 최대 공약수의 계산은 곱셈보다 느려진다.보다 정확하게는 n비트의 2개의 정수를 곱하는 데 T(n)의 시간이 걸리는 경우, 최대공약수의 가장 빠른 알고리즘은 $복잡도{\displaystyle }$O${\displaystyle (T}$ (${\displaystyle n)}$ ${\displaystyle \log )}$ n ${\displaystyle ).}$ $(\displaystyle$ O$\left(T(n)\log$ n$\right)$가 됩니다.} 이는$$ 가장 빨리 알려진 알고리즘의 ${\displaystyle 복잡도}$가 O${\displaystyle (n}$ (${\displaystyle \log {}^{}}$ ${\displaystyle {n\mathrm{}}^{}}$ )$2$ .\$display$ style $O\left$(n$,\log$ n$)^{2}\right임$을 의미합니다$.$$}$

이전의 복잡도는 일반적인 계산 모델, 특히 멀티테이프 튜링 기계와 랜덤 액세스 기계에 유효하다.

따라서 최대공약수의 연산은 준선형 시간에 풀 수 있는 문제의 종류에 속합니다.즉, 대응하는 결정문제는 다항시간에 풀 수 있는 문제의 클래스 P에 속합니다.GCD 문제는 NC에 있는 것으로 알려져 있지 않기 때문에 효율적으로 병렬화할 수 있는 방법이 없습니다.또한 P-complete도 알려져 있지 않습니다.이는 GCD 계산을 효율적으로 병렬화하는 것이 불가능하다는 것을 의미합니다.Shallcross 등에서는 관련 문제(EUGCD, 유클리드 알고리즘 중 발생하는 나머지 시퀀스 결정)가 두 변수의 정수 선형 프로그래밍 문제와 동등하다는 것을 보여주었다. 두 문제 중 하나가 NC에 있거나 P-완전인 경우,^[20] 다른 문제도 마찬가지이다.NC는 NL을 포함하고 있기 때문에, 비결정적인 튜링 머신에서도 GCD를 계산하기 위한 공간 효율적인 알고리즘이 존재하는지 여부도 알 수 없다.

이 문제는 NC에 있는 것으로 알려져 있지 않지만 병렬 알고리즘은 유클리드 알고리즘보다 점근적으로 빠른 것으로 알려져 있습니다.가장 빠른 결정론적 알고리즘은 Chor와 Goldreich에 의한 것입니다.이 알고리즘은 (CRCW-PRAM 모델에서) n개의 ^[21]프로세서를^1+ε 사용하여 O(n/log n) 시간 내에 문제를 해결할 수 있습니다.랜덤화 알고리즘은 exp ${\displaystyle (}$ ( ${\displaystyle O}$( ${\displaystyle \sqrt{n}}$ log${\displaystyle \sqrt{n}}$n${\displaystyle }$)$$\ $displaystyle \ exp$ \ left ( $O$\ $left$( { \ $sqrt { n$ \ $log$ n} } \$right )$프로세서$$^{[clarification needed]}(이것은 슈퍼 다항식)\^[22] right )의 O ( ( log ²n )시간 내에 문제를 해결할 수 있습니다.

특성.

• a와 b의 모든 공통수는 gcd(a, b)의 제수이다.
• 여기서 a와 b가 모두 0이 아닌 gcd(a, b)는 d = a440p + b440q 형식으로 쓸 수 있는 최소 양의 정수 d로 대체 및 동등하게 정의할 수 있다. 여기서 p와 q는 정수이다.이 표현은 베주우트의 정체성이라고 불립니다.이와 같은 숫자 p와 q는 확장 유클리드 알고리즘으로 계산할 수 있다.
• gcd(a, 0) = a는 0의 제수이며, a의 최대 제수는 ^[2][5]a이기 때문에 θ 0의 경우이다.이것은 보통 유클리드 알고리즘에서 베이스 케이스로 사용됩니다.
• 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)이다.gcd(a mod b,b) = gcd(a,b)이다.
• m이 a와 b의 양의 공약수이면 gcd(a/m, b/m) = gcd(a, b)/m이다.
• GCD는 교환 함수이다: gcd(a, b) = gcd(b, a)
• GCD는 연관 함수이다: gcd(a, gcd(b, c) = gcd(gcd(a, b), c).따라서 gcd(a, b, c, ...)를 사용하여 여러 인수의 GCD를 나타낼 수 있습니다.
• GCD는 다음 의미에서 곱셈 함수이다. a와₂ a가 상대적으로 소수일 경우₁ gcd(a₁⋅a₂, b) = gcd(a₁, b)gcd(a₂, b)이다.
• gcd(a, b)는 최소공통 배수 lcm(a, b)와 밀접하게 관련되어 있습니다.

  gcd(a, b)sqlcm(a, b) = aqlb.

이 공식은 종종 최소공배수를 계산하는데 사용된다: 먼저 유클리드의 알고리즘으로 GCD를 계산한 다음 주어진 숫자의 곱을 GCD로 나눈다.

• 다음 버전의 배포는 true를 유지합니다.

  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 = p1e1 p2e2 ⋅ pmem 및 b = p1f12f2 p ⋅ p p , p , p = p ⋅ pmfm ⋅ p a p a p의 고유한 소인수 분해가 있을 경우i a와 b의i GCD는 다음과 같습니다.

  gcd(a,b) = p₁^{min(e₁,f₁)}₂^{min(e₂,f₂)} p ⋅ p ⋅ p_m^min(e_m,f_m) 。

• gcd(0, 0) = 0 및 lcm(0, 0) = 0을 정의하면 자연수가 GCD가 충족되고 LCM이 결합 ^[23]연산인 완전한 분포 격자가 되기 때문에 때때로 유용합니다.이 정의의 확장은 아래에 제시된 가환환의 일반화와도 호환된다.
• 데카르트 좌표계에서 gcd(a, b)는 점(0, 0) 및 (a, b)을 연결하는 직선 세그먼트 상의 적분 좌표를 가진 점 사이의 세그먼트 수로 해석할 수 있다.
• a와 b가 모두 0이 아닌 음이 아닌 정수 a와 b의 경우, 기저 ^[24]n의 유클리드 알고리즘을 고려함으로써 증명할 수 있다.

  gcd(n^a - 1, n^b - 1) = n^gcd(a,b) - 1.

• 오일러의 전체 함수와 관련된 항등식:

  $\displaystyle \gcd(a,b)=\sum _{k a420text{ 및 }}k b}\varphi(k).}$

• ${\displaystyle \sum _{}^{}}$ ${\displaystyle \underset{}{\overset{}{k}}}$= ${\displaystyle \underset{}{\overset{}{}}}$ ${\displaystyle n\gcd }$( ${\displaystyle k}$, ${\displaystyle n\mathrm{}}$) = ${\displaystyle n\underset{}{}}$、 ${\displaystyle n\mathrm{}\underset{}{}}$、 n${\displaystyle }$、 1 +${\displaystyle {}_{}}$+ ${\displaystyle \frac{p}{}}$ ( ${\displaystyle n_{}}$) ($1$ -${\displaystyle }$1${\displaystyle }$p$$){$displaystyle$ \$sum _$ { k$$=$1 }$ $\ gcd$( k ,$n$ )$=$n \$displaystyle$ _ $n }$ \ $left$ ( 1 + \ $nu$ _ { $p$（ n （ n ） （ n ） ） { p } { $p$} { $p$} { p }

확률과 기대치

1972년 제임스 E.Nymann은 {1, ..., n}에서 독립적으로 균일하게 선택되는 k개의 정수가 n이 무한대로 갈 때 확률 1/θ(k)와 공수임을 보여주었다. 여기서 θ는 리만 제타 ^[25]함수를 의미한다.(파생에 대해서는, 「공시」를 참조해 주세요).이 결과는 1987년에 k개의 랜덤 정수가 최대 공약수 d를 가질 확률이 d/θ(k)^[26]임을^−k 보여주기 위해 확장되었다.

이 정보를 사용하여, 최대공약수 함수의 기대값은 k = 2일 때 존재하지 않는 것으로 볼 수 있다. 이 경우 GCD가 d와 같을 확률은⁻² d/drp(2)이고, θ²(2) = θ/6이므로 우리는 다음과 같이 된다.

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

이 마지막 합계는 분산되는 조화 급수입니다.단, k ≤ 3일 경우 기대치는 명확하게 정의되며 위의 인수에 의해

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

k = 3의 경우 이는 약 1.3684와 같습니다.k = 4의 경우 약 1.1106입니다.

가환환 내

이 섹션은 어떠한 출처도 인용하지 않습니다. 신뢰할 수 있는 출처에 인용문을 추가하여 이 섹션의 개선에 도움을 주십시오. 소스되지 않은 자재는 제거될 수 있습니다. (2014년 10월) (이 템플릿 메시지 삭제 방법 및 시기에 대해 알아보기)

최대공약수의 개념은 일반적으로 임의의 교환환의 요소에 대해 정의될 수 있지만, 일반적으로 모든 요소 쌍에 대해 존재할 필요는 없습니다.

R이 교환환이고, a와 b가 R에 있으면, R의 원소 d는 a와 b를 둘 다 나누면 a와 b의 공약수라고 불린다(즉, R에 원소 x와 y가 존재하면 d·x = a와 d·y = b가 된다).만약 d가 a와 b의 공약수이고, a와 b의 모든 공약수가 d를 나눈다면, d는 a와 b의 최대 공약수라고 불립니다.

이 정의에서는 두 요소 a와 b가 여러 개의 가장 큰 공통수를 갖거나 전혀 갖지 않을 수 있습니다.R이 통합 도메인인 경우 정의상 한쪽이 다른 쪽을 분할해야 하기 때문에 a와 b의 두 GCD는 반드시 관련 요소여야 합니다. GCD가 존재한다면 그 중 어느 한쪽도 GCD입니다.GCD의 존재는 임의의 통합 도메인에서 보증되지 않습니다.단, R이 하나의 인수분해 도메인일 경우 임의의 2개의 요소가 GCD를 가지며, 보다 일반적으로는 GCD 도메인에서 해당됩니다.만약 R이 유클리드 나눗셈이 알고리즘적으로 주어지는 유클리드 영역이라면(예를 들어 R = F[X]가 필드이거나 R이 가우스 정수의 고리일 때처럼), 최대공약수는 나눗셈 절차에 기초한 유클리드 알고리즘의 형태를 사용하여 계산할 수 있다.

다음으로 GCD가 없는2개의 요소를 가진 통합 도메인의 예를 나타냅니다.

$\displaystyle R=\mathbb {Z} \left[{\displayrt {-3}},\right],\cdot 2=\left(1+{\cdot {-3}},\right)\left(1-{\displayrt {-3},\right},\right},\right},\left)$

요소 2와 1 + δ-3은 2개의 최대공약수입니다(2의 배수인 모든 공약수는 2에 관련지어지며, 1 + δ-3은 동일하지만 관련지어져 있지 않기 때문에 a와 b의 최대공약수는 없습니다.

Bézout 특성에 대응하여 임의의 교환환에서 pa + qb 형식의 요소의 컬렉션을 고려할 수 있습니다.여기서 p와 q는 링 전체에 걸쳐 있습니다.이것은 a와 b에 의해 생성된 이상이며, 간단히 (a, b)로 표시됩니다.이상이 모두 주(주 이상 영역 또는 PID)인 링에서, 이 이상은 일부 링 요소 d의 배수 집합과 동일할 것입니다. 그러면 이 d는 a와 b의 최대 공약수입니다.그러나 이상(a, b)은 a와 b의 최대공약수가 없을 때에도 유용할 수 있다. (실제로, 에른스트 쿠머는 이 이상을 페르마의 마지막 정리에 대한 그의 치료에서 GCD의 대체물로 사용했다, 비록 그는 그것을 고리-고리가론일 때, 그는 그것을 어떤 가설, 혹은 이상적인 고리 원소의 배수의 집합으로 상상했지만)

「 」를 참조해 주세요.

• 베주트 도메인
• 최소공통분모
• 유니터리 제수

메모들

레퍼런스

• 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

추가 정보

• 도널드 크누트.The Art of Computer Programming, 제2권: 세미네머ical Algorithms, 제3판.애디슨 웨슬리, 1997년ISBN 0-201-89684-2.섹션 4.5.2: 최대공약수, 333–356페이지.
• 토마스 H. 코먼, 찰스 E. 리저슨, 로널드 L. 리베스트, 클리포드 스타인.알고리즘 소개, 제2판MIT Press and McGraw-Hill, 2001.ISBN 0-262-03293-7.섹션 31.2: 최대 공약수, 페이지 856–862.
• 손더스 맥 레인과 개럿 버크호프입니다현대 대수학 조사 제4판맥밀런 출판사, 1977년ISBN 0-02-310070-2. 1~7: "유클리드 알고리즘"