#!if 넘어옴1 != null
''''''{{{#!if 넘어옴2 != null
, ''''''}}}{{{#!if 넘어옴3 != null
, ''''''}}}{{{#!if 넘어옴4 != null
, ''''''}}}{{{#!if 넘어옴5 != null
, ''''''}}}{{{#!if 넘어옴6 != null
, ''''''}}}{{{#!if 넘어옴7 != null
, ''''''}}}{{{#!if 넘어옴8 != null
, ''''''}}}{{{#!if 넘어옴9 != null
, ''''''}}}{{{#!if 넘어옴10 != null
, ''''''}}}은(는) 여기로 연결됩니다. #!if 설명 == null && 리스트 == null
{{{#!if 설명1 == null
다른 뜻에 대한 내용은 아래 문서를}}}{{{#!if 설명1 != null
{{{#!html RADWIMPS의 노래}}}에 대한 내용은 [[最大公約数]] 문서{{{#!if (문단1 == null) == (앵커1 == null)
를}}}{{{#!if 문단1 != null & 앵커1 == null
의 [[最大公約数#s-|]]번 문단을}}}{{{#!if 문단1 == null & 앵커1 != null
의 [[最大公約数#|]] 부분을}}}}}}{{{#!if 설명2 != null
, {{{#!html }}}에 대한 내용은 [[]] 문서{{{#!if (문단2 == null) == (앵커2 == null)
를}}}{{{#!if 문단2 != null & 앵커2 == null
의 [[#s-|]]번 문단을}}}{{{#!if 문단2 == null & 앵커2 != null
의 [[#|]] 부분을}}}}}}{{{#!if 설명3 != null
, {{{#!html }}}에 대한 내용은 [[]] 문서{{{#!if (문단3 == null) == (앵커3 == null)
를}}}{{{#!if 문단3 != null & 앵커3 == null
의 [[#s-|]]번 문단을}}}{{{#!if 문단3 == null & 앵커3 != null
의 [[#|]] 부분을}}}}}}{{{#!if 설명4 != null
, {{{#!html }}}에 대한 내용은 [[]] 문서{{{#!if (문단4 == null) == (앵커4 == null)
를}}}{{{#!if 문단4 != null & 앵커4 == null
의 [[#s-|]]번 문단을}}}{{{#!if 문단4 == null & 앵커4 != null
의 [[#|]] 부분을}}}}}}{{{#!if 설명5 != null
, {{{#!html }}}에 대한 내용은 [[]] 문서{{{#!if (문단5 == null) == (앵커5 == null)
를}}}{{{#!if 문단5 != null & 앵커5 == null
의 [[#s-|]]번 문단을}}}{{{#!if 문단5 == null & 앵커5 != null
의 [[#|]] 부분을}}}}}}{{{#!if 설명6 != null
, {{{#!html }}}에 대한 내용은 [[]] 문서{{{#!if (문단6 == null) == (앵커6 == null)
를}}}{{{#!if 문단6 != null & 앵커6 == null
의 [[#s-|]]번 문단을}}}{{{#!if 문단6 == null & 앵커6 != null
의 [[#|]] 부분을}}}}}}{{{#!if 설명7 != null
, {{{#!html }}}에 대한 내용은 [[]] 문서{{{#!if (문단7 == null) == (앵커7 == null)
를}}}{{{#!if 문단7 != null & 앵커7 == null
의 [[#s-|]]번 문단을}}}{{{#!if 문단7 == null & 앵커7 != null
의 [[#|]] 부분을}}}}}}{{{#!if 설명8 != null
, {{{#!html }}}에 대한 내용은 [[]] 문서{{{#!if (문단8 == null) == (앵커8 == null)
를}}}{{{#!if 문단8 != null & 앵커8 == null
의 [[#s-|]]번 문단을}}}{{{#!if 문단8 == null & 앵커8 != null
의 [[#|]] 부분을}}}}}}{{{#!if 설명9 != null
, {{{#!html }}}에 대한 내용은 [[]] 문서{{{#!if (문단9 == null) == (앵커9 == null)
를}}}{{{#!if 문단9 != null & 앵커9 == null
의 [[#s-|]]번 문단을}}}{{{#!if 문단9 == null & 앵커9 != null
의 [[#|]] 부분을}}}}}}{{{#!if 설명10 != null
, {{{#!html }}}에 대한 내용은 [[]] 문서{{{#!if (문단10 == null) == (앵커10 == null)
를}}}{{{#!if 문단10 != null & 앵커10 == null
의 [[#s-|]]번 문단을}}}{{{#!if 문단10 == null & 앵커10 != null
의 [[#|]] 부분을}}}}}}#!if 설명 == null
{{{#!if 리스트 != null
다른 뜻에 대한 내용은 아래 문서를}}} 참고하십시오.#!if 리스트 != null
{{{#!if 문서명1 != null
* {{{#!if 설명1 != null
RADWIMPS의 노래: }}}[[最大公約数]] {{{#!if 문단1 != null & 앵커1 == null
문서의 [[最大公約数#s-|]]번 문단}}}{{{#!if 문단1 == null & 앵커1 != null
문서의 [[最大公約数#|]] 부분}}}}}}{{{#!if 문서명2 != null
* {{{#!if 설명2 != null
: }}}[[]] {{{#!if 문단2 != null & 앵커2 == null
문서의 [[#s-|]]번 문단}}}{{{#!if 문단2 == null & 앵커2 != null
문서의 [[#|]] 부분}}}}}}{{{#!if 문서명3 != null
* {{{#!if 설명3 != null
: }}}[[]] {{{#!if 문단3 != null & 앵커3 == null
문서의 [[#s-|]]번 문단}}}{{{#!if 문단3 == null & 앵커3 != null
문서의 [[#|]] 부분}}}}}}{{{#!if 문서명4 != null
* {{{#!if 설명4 != null
: }}}[[]] {{{#!if 문단4 != null & 앵커4 == null
문서의 [[#s-|]]번 문단}}}{{{#!if 문단4 == null & 앵커4 != null
문서의 [[#|]] 부분}}}}}}{{{#!if 문서명5 != null
* {{{#!if 설명5 != null
: }}}[[]] {{{#!if 문단5 != null & 앵커5 == null
문서의 [[#s-|]]번 문단}}}{{{#!if 문단5 == null & 앵커5 != null
문서의 [[#|]] 부분}}}}}}{{{#!if 문서명6 != null
* {{{#!if 설명6 != null
: }}}[[]] {{{#!if 문단6 != null & 앵커6 == null
문서의 [[#s-|]]번 문단}}}{{{#!if 문단6 == null & 앵커6 != null
문서의 [[#|]] 부분}}}}}}{{{#!if 문서명7 != null
* {{{#!if 설명7 != null
: }}}[[]] {{{#!if 문단7 != null & 앵커7 == null
문서의 [[#s-|]]번 문단}}}{{{#!if 문단7 == null & 앵커7 != null
문서의 [[#|]] 부분}}}}}}{{{#!if 문서명8 != null
* {{{#!if 설명8 != null
: }}}[[]] {{{#!if 문단8 != null & 앵커8 == null
문서의 [[#s-|]]번 문단}}}{{{#!if 문단8 == null & 앵커8 != null
문서의 [[#|]] 부분}}}}}}{{{#!if 문서명9 != null
* {{{#!if 설명9 != null
: }}}[[]] {{{#!if 문단9 != null & 앵커9 == null
문서의 [[#s-|]]번 문단}}}{{{#!if 문단9 == null & 앵커9 != null
문서의 [[#|]] 부분}}}}}}{{{#!if 문서명10 != null
* {{{#!if 설명10 != null
: }}}[[]] {{{#!if 문단10 != null & 앵커10 == null
문서의 [[#s-|]]번 문단}}}{{{#!if 문단10 == null & 앵커10 != null
문서의 [[#|]] 부분}}}}}}| 특수함수 Special Functions | ||
| {{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin: -5px -1px -11px; word-break: keep-all" | <colbgcolor=#383B3D><colcolor=#fff> 적분 | 오차함수(error function)(가우스 함수 · 가우스 적분 함수) · 베타 함수(불완전 베타 함수) · 감마 함수(불완전 감마 함수 · 로그 감마 함수) · 타원 적분 · 야코비 타원 함수 · 지수 적분 함수 · 로그 적분 함수 · 삼각 적분 함수 · 쌍곡선 적분 함수 · 프레넬 적분 함수 · 구데르만 함수 |
| 미분방정식 | 르장드르 함수[math(^\ast)] (구면 조화 함수) · 베셀 함수 · 에르미트 함수 · 라게르 함수 · 에어리 함수 | |
| 역함수 | 브링 근호 · 람베르트 W 함수 · 역삼각함수 | |
| 급수 | 제타 함수 · 후르비츠 제타 함수 · 세타 함수 · 초기하함수 · 폴리로그함수 · 폴리감마 함수 · 바이어슈트라스 타원 함수 | |
| 정수론 | 소수 계량 함수 · 소인수 계량 함수 · 뫼비우스 함수 · 최대공약수 · 최소공배수 · 약수 함수 · 오일러 피 함수 · 폰 망골트 함수 · 체비쇼프 함수 · 바쁜 비버 함수 | |
| 기타 | 헤비사이드 계단함수 · 부호 함수 · 테트레이션(무한 지수 탑 함수) · 지시함수 · 바닥함수 / 천장함수 · 허수지수함수 · 혹 함수 | |
| [math(^\ast)] 특수함수가 아니라 특정 조건을 만족시키는 다항함수이지만, 편의상 이곳에 기술했다. | ||
| 정수론 Number Theory | |||
| {{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin: -5px -1px -11px" | 공리 | ||
| 페아노 공리계 · 정렬 원리 · 수학적 귀납법 · 아르키메데스 성질 | |||
| 산술 | |||
| 나눗셈 | 약수·배수 | 배수 · 약수(소인수) · 소인수분해(목록 · 알고리즘) · 공배수 · 공약수 · 최소공배수 · 최대공약수 | |
| 약수들의 합에 따른 수의 분류 | 완전수 · 부족수 · 과잉수 · 친화수 · 사교수 · 혼약수 · 반완전수 · 불가촉 수 · 괴짜수 | ||
| 정리 | 베주 항등식 · 산술의 기본정리 · 나눗셈 정리 | ||
| 기타 | 유클리드 호제법 · 서로소 | ||
| 디오판토스 방정식 | 페르마의 마지막 정리 · 피타고라스 세 쌍 · 과일 분수방정식 문제 · 버치-스위너턴다이어 추측(미해결) | ||
| 모듈러 연산 | |||
| 모듈러 역원 · 2차 잉여 · 기약잉여계 · 완전잉여계 · 중국인의 나머지 정리 · 합동식 · 페르마의 소정리 · 오일러 정리 · 윌슨의 정리 | |||
| 소수론 | |||
| 수의 분류 | 소수 · 합성수 · 메르센 소수 · 쌍둥이 소수(사촌 소수 · 섹시 소수) · 페르마 소수 · 레퓨닛 수 | ||
| 분야 | 대수적 정수론(국소체) · 해석적 정수론 | ||
| 산술함수 | 뫼비우스 함수 · 소수 계량 함수 · 소인수 계량 함수 · 약수 함수 · 오일러 파이 함수 · 폰 망골트 함수 · 체비쇼프 함수 · 소수생성다항식 | ||
| 정리 | 그린 타오 정리 · 페르마의 두 제곱수 정리 · 디리클레 정리 · 소피 제르맹의 정리 · 리만 가설(미해결) · 골드바흐 추측(미해결)(천의 정리) · 폴리냑 추측(미해결) · 소수 정리 | ||
| 기타 | 에라토스테네스의 체 · 윌런스의 공식 | ||
| 중학교 수학 용어 | ||
| {{{#!wiki style="margin: -0px -10px -5px; min-height: 26px" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin:-6px -2px -12px" | <colbgcolor=#2667a9><colcolor=white> ㄱ | <colbgcolor=#fff,#191919>각뿔대 · 거듭제곱 · 결합법칙 · 계급 · 계급의 크기 · 계수 · 교각 · 교선 · 교점 · 교환법칙 · 그래프 · 근 · 근의 공식 · 근호 · 기울기 · 꼬인 위치 · 꼭짓점 |
| ㄴ | 내각 · 내심 · 내접 · 내접원 | |
| ㄷ | 다면체 · 다항식 · 단항식 · 닮음 · 닮음비 · 대각 · 대변 · 대입 · 대푯값 · 도수 · 도수분포다각형 · 도수분포표 · 동류항 · 동위각 · 두 점 사이의 거리 · 등식 | |
| ㅁ | 맞꼭지각 · 무게중심 · 무리수 · 무한소수 · 미지수 · 밑 | |
| ㅂ | 반비례 · 방정식 · 변량 · 변수 · 부등식 · 부채꼴 · 분모의 유리화 · 분배법칙 · 분산 | |
| ㅅ | 사건 · 사분위수 · 사인 · 산점도 · 산포도 · 삼각비 · 삼각형의 닮음 조건 · 삼각형의 합동 조건 · 상관관계 · 상대도수 · 상수항 · 상자그림 · 서로소 · 소수 · 소인수 · 소인수분해 · 수선의 발 · 수직선 · 수직이등분선 · 순서쌍 · 순환마디 · 순환소수 · 실수 | |
| ㅇ | 양수 · 양의 유리수 · 양의 정수 · 엇각 · 역수 · 연립방정식 · 완전제곱식 · 외각 · 외심 · 외접 · 외접원 · 원뿔대 · 원점 · 원주각 · 유리수 · 유한소수 · 음수 · 음의 유리수 · 음의 정수 · 이차방정식 · 이차함수 · 이항 · 인수 · 인수분해 · 일차방정식 · 일차부등식 · 일차식 · 일차함수 | |
| ㅈ | 작도 · 전개 · 절댓값 · 접선 · 접점 · 접한다 · 정다면체 · 정비례 · 정수 · 제1사분면 · 제2사분면 · 제3사분면 · 제4사분면 · 제곱근 · 좌표 · 좌표축 · 좌표평면 · 줄기와 잎 그림 · 중근 · 중선 · 중심각 · 중앙값 · 중점 · 증명 · 지수 · 직교 · 직선의 방정식 | |
| ㅊ | 차수 · 최댓값 · 최빈값 · 최솟값 · 축 | |
| ㅋ | 코사인 | |
| ㅌ | 탄젠트 | |
| ㅍ | 편차 · 평각 · 평행이동 · 포물선 · 표준편차 · 피타고라스 정리 | |
| ㅎ | 할선 · 함수 · 함숫값 · 합성수 · 항 · 항등식 · 해 · 현 · 호 · 확률 · 활꼴 · 회전체 · 회전축 · 히스토그램 | |
| 기타 | x좌표 · y좌표 · x축 · y축 · x절편 · y절편 |
1. 개요
最大公約數 · greatest common divisor(factor), GCD정수의 성질 중 하나. 초등학교 5학년 때 배우기 시작하며, 약수(divisor or factor)에 대해서 먼저 배운 뒤, 바로 배우게 될 것이다. 먼저 공약수(common divisor or common factor)란, 한자 뜻에서 알 수 있듯이 두 수, 혹은 그 이상의 여러 수의 공통인 약수라는 뜻이다. 최대공약수는 말 그대로 공약수 중 가장 큰 것을 가리킨다. 두 수 [math(a,\,b)]의 최대공약수를 수학적 기호로 표시하면 [math(\gcd{}(a,\,b))]이며,[1] 더욱 줄여서 [math((a,\,b))]로 표기하기도 한다.[2] 특히, [math(\gcd\,(a,\,b)=1)]일 경우 두 수 [math(a,\,b)]가 서로소(relatively prime, coprime)라고 한다. 이후 중1로 입학해서 소인수분해와 연계하여 더 심화된 과정으로 최소공배수와 같이 3개 이상의 수로 또 나온다. 최대공약수와 최소공배수는 뒤에서 배우게 될 약분과 통분, 분모가 다른 분수의 계산, 분수의 곱셈·나눗셈, 6학년 때 배우는 비의 성질, 비례식의 성질, 비례배분, 중1 입학하면 분수ㆍ소수ㆍ자연수ㆍ정수ㆍ유리수의 (혼합)계산, 제곱근, 일(이)차함수, 일(이)차방정식ㆍ연립방정식ㆍ(연립)부등식의 풀이, 제곱근처럼 다양한 방면에서 쓰인다.
가끔 최소공약수라고 잘못 부르는 경우가 있는데, 최소공약수는 무조건 1이므로 논할 가치도 없다. 반대로 최대공배수도 결국 무한으로 발산하므로 논할 가치 자체가 없다.
2. 찾는 법
예시로 두 수 12, 18의 공약수 및 최대공약수를 찾고 싶다고 하자. 간단하게, 두 수의 약수를 모두 나열한다.12: 1, 2, 3, 4, 6, 12
18: 1, 2, 3, 6, 9, 18
여기서 위아랫줄 모두 같이 있는 숫자가 공약수가 된다. 즉, 이 경우에는 1, 2, 3, 6이 공약수가 된다. 최대공약수는, 찾은 공약수 중 가장 큰 것, 즉 이 경우에는 6이 최대공약수가 된다. 같은 방법으로 세 수 이상의 최대공약수도 구할 수 있다.18: 1, 2, 3, 6, 9, 18
하지만 두 수의 약수를 찾는 게 어렵다면 어떻게 될까? 2015와 246의 최대공약수를 약수를 나열하는 방법으로 찾으려면 한참이 걸릴 것이다.[3] 이 문제를 해결하기 위한 방법이 바로 유클리드 호제법. 기원전에 발견된 이 방법은 놀랍게도 인류 최초의 알고리즘이라고 한다. 자세한 것은 항목 참조.
최소공배수 [math(\mathrm{lcm})]를 이용하는 방법도 있다. 최소공배수와 다음과 같은 관계가 성립한다:
[math(\gcd(a,\,b) = \dfrac{|ab|}{\mathrm{lcm}(a,\,b)})]
단, 최대공약수도 최소공배수도 모를 경우 순환논법이 될 수 있음을 주의해야 한다.세 수 이상의 최대공약수를 구하려면 다음과 같이 함수를 계속 취해주면 된다.
세 수 [math(a,\,b,\,c)]에 대해서
[math(\gcd(a,\, b,\, c) = \gcd(\gcd(a,\, b),\, c) \equiv \dfrac{| abc |}{\mathrm{lcm}\left( \frac{| ab |}{\mathrm{lcm}(a,\,b)},\, c \right)})]
이 성립한다.
[math(\gcd(a,\, b,\, c) = \gcd(\gcd(a,\, b),\, c) \equiv \dfrac{| abc |}{\mathrm{lcm}\left( \frac{| ab |}{\mathrm{lcm}(a,\,b)},\, c \right)})]
이 성립한다.
해석적인 방법[4]으로는 이렇게 된다.
[math(\displaystyle \gcd(x,\,y) = \int_{n|x} \int_{1}^{x} e^{\frac{2}{x}i \pi ty} \frac{c_n(t)}{n}\ \mathrm{d}\lfloor t \rfloor \mathrm{d}\lfloor n \rfloor)]
여기서 [math(c_n(t))]는 라마누잔합 함수이다.3. 성질
두 정수 [math(a,b)]에 대해서,- [math(\gcd\left(a,b\right)\geq1)]
{{{#!folding [증명]
[math(1\mid a,1\mid b)]이므로, 두 수의 최대공약수는 1보다 크거나 같다. 즉, [math(\gcd\left(a,b\right)\geq1)].
}}} - [math(\gcd\left(a,b\right)=\gcd\left(\left|a\right|,\left|b\right|\right))]
{{{#!folding [증명]
[math(x\mid a)]와 [math(x\mid -a)]는 동치이다. 그런데 [math(\left|a\right|)]는 [math(a)] 또는 [math(-a)]이므로 [math(a)]와 [math(\left|a\right|)]는 같은 약수를 갖는다. 마찬가지로, [math(b)]와 [math(\left|b\right|)]는 같은 약수를 갖는다. 따라서, [math(x)]가 [math(a)]와 [math(b)]의 공약수라는 것은 [math(\left|a\right|)]와 [math(\left|b\right|)]의 공약수라는 사실과 동치이다. [math(\therefore\gcd\left(a,b\right)=\gcd\left(\left|a\right|,\left|b\right|\right))]
}}} - [math(\gcd\left(a,0\right)=\left|a\right|)]
{{{#!folding [증명]
2번으로 부터, [math(\gcd\left(a,0\right)=\gcd\left(\left|a\right|,0\right))]이다. [math(\left|a\right|\cdot0=0)]이므로, [math(\left|a\right|\mid0)]. 또한, [math(\left|a\right|\mid\left|a\right|)]이므로, [math(\left|a\right|)]는 [math(\left|a\right|)]와 0의 공약수이다. 그러므로 [math(\left|a\right|\leq\gcd\left(\left|a\right|,0\right))]이다. 그런데 [math(\gcd\left(\left|a\right|,0\right)\mid\left|a\right|)]이므로, [math(\gcd\left(\left|a\right|,0\right)\leq\left|a\right|)]. 위 두 부등식으로 부터 [math(\gcd\left(\left|a\right|,0\right)=\left|a\right|)]. 다시 한번 2번으로 부터, [math(\gcd\left(a,0\right)=\gcd\left(\left|a\right|,0\right)=\left|a\right|)].
}}} - [math(d=\gcd\left(a,b\right))]라 하면, [math(\gcd\left(\frac{a}{d},\frac{b}{d}\right)=1)]
{{{#!folding [증명]
[math(a=dm, b=dn)]라 하면, [math(\gcd\left(\frac{a}{d},\frac{b}{d}\right)=\gcd\left(m,n\right))]이다. 양의 정수 [math(p)]가 [math(p\mid m,p\mid n)]를 만족한다고 하자. 그러면 [math(m=pe,n=pf)]를 만족하는 정수 [math(e,f.)]가 존재한다. 따라서, [math(a=dpe,b=dpf)]이고 [math(dp)]는 [math(a,b)]의 공약수이다. 한편, [math(d)]는 최대공약수이므로, [math(d\geq dp)]. 따라서 [math(p\leq1)]이고 [math(p=1)]일 수밖에 없다. 이로써 보이고자 하는 바가 증명되었다.
}}} - 임의의 정수 [math(k)]에 대하여, [math(\gcd\left(a,b\right)=\gcd\left(a+kb,b\right))]
{{{#!folding [증명]
만약 [math(x)]가 [math(a,b)]의 공약수라면, [math(x\mid a,x\mid b)]이다. 따라서 [math(x\mid kb)]이고, [math(x\mid a+kb)]이다. 따라서 [math(x)]는 [math(a+kb)]와 [math(b)]의 공약수이다.
역으로, [math(x)]가 [math(a+kb)]와 [math(b)]의 공약수라면, [math(x\mid a+kb, x\mid b)]이다. 따라서 [math(x\mid kb)]이고, [math(x\mid\left(\left(a+kb\right)-kb\right)=a)]이다. 즉, [math(x)]는 [math(a,b)]의 공약수이다. 따라서 [math(a,b)]와 [math(a+kb,b)]는 같은 공약수 집합을 가지므로 최대공약수도 같아야 한다.
}}} - 베주 항등식: 임의의 양의 정수 [math(a,b)]에 대해서, [math(ax+by=\gcd\left(a,b\right))]를 만족하는 정수 [math(x,y)]가 존재한다.[5]
{{{#!folding [증명]
집합 [math(A=\left\{ax+by>0|x,y\in Z\right\})]를 생각하자. 집합 [math(A)]는 자연수의 부분집합이고 공집합이 아니므로 well-ordering 원리에 의해 가장 작은 원소가 존재한다. 이를 [math(d)]라 하면 적당한 정수 [math(x,y)]에 대해 [math(d=ax+by)]이다. 여기서 [math(d)]가 최대공약수임을 보이면 증명이 끝난다.
[math(d>0)]이므로, 나눗셈 정리에 의하여 [math(a=qd+r,\,0\leq r<d)]인 정수 [math(q,r)]가 존재한다. 그러면 [math(r=a-qd=a-q\left(ax+by\right)=a\left(1-qx\right)-b\left(qy\right))]이므로 [math(r>0)]이면 [math(r\in A)]이고, [math(r<d)]가 되어 [math(d)]가 가장 작은 원소라는 사실에 모순된다. 따라서 [math(r=0)]이고, [math(d\mid a)]이다. 마찬가지로 [math(d\mid b)]이다. 즉, [math(d\mid\gcd\left(a,b\right))].
한편 [math(e)]가 [math(a,b)]의 공약수라면 [math(e\mid\left(ax+by\right))]이고,[6] [math(ax+by=d)]이므로 [math(e\mid d)], 즉 [math(e\leq d)]이다. 이는 곧 [math(d)]가 최대공약수임을 보인다.
}}}
4. 관련 문서
[1] 영어(Greatest Common Divisor)의 약자에서 나온 기호.[2] 다만 [math((a,\,b))]은 순서쌍이나 개구간 표현과 겹치므로 사용에 주의할 필요가 있다. 사실 정수론은 실해석학과 분야를 달리 하므로 혼동되는 경우가 거의 없다. 해석학과 정수론의 콜라보인 해석적 정수론에서는 혼동할 여지는 있지만...[3] 이 점 때문에 특수함수에 속한다. 참고로 최대공약수/최소공배수는 교과과정상 가장 처음으로 접하는 특수함수이다. 참고로 [math(2015=5×13×31, \ 246=2×3×41)]이라 두 수는 서로소이다.[4] 복소수까지 범위가 확장된다.[5] 자세한 증명과 내용은 베주 항등식 문서에서 볼 수 있다. 만약 a와 b가 서로소이면, [math(ax+by=1)]를 만족하는 정수 [math(x,y)]가 존재함을 의미한다. 역도 성립한다.[6] 5번 성질 참조