| 특수함수 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. 개요
最大公約數 · 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 과정에서 소인수분해와 연계하여 더 심화된 과정으로 최소공배수와 같이 또 나온다. 최대공약수·최소공배수는 약분과 통분, 분모가 다른 분수의 계산, 분수의 곱셈·나눗셈, 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)]
- [math(\gcd\left(a,b\right)=\gcd\left(\left|a\right|,\left|b\right|\right))]
- [math(\gcd\left(a,0\right)=\left|a\right|)]
- [math(d=\gcd\left(a,b\right))]라 하면, [math(\gcd\left(\frac{a}{d},\frac{b}{d}\right)=1)]
- 임의의 정수 [math(k)]에 대하여, [math(\gcd\left(a,b\right)=\gcd\left(a+kb,b\right))]
- 베주 항등식: 임의의 양의 정수 [math(a,b)]에 대해서, [math(ax+by=\gcd\left(a,b\right))]를 만족하는 정수 [math(x,y)]가 존재한다.[5]
4. 증명
- [math(1\mid a,1\mid b)]이므로, 두 수의 최대공약수는 1보다 크거나 같다. 즉, [math(\gcd\left(a,b\right)\geq1)].
- [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))]
- 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(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(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=\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)]가 최대공약수임을 보인다.
5. 관련 문서
[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번 성질 참조