최대공약수

1. 개요

2. 찾는 법

3. 성질

1. [math(\gcd\left(a,b\right)\geq1)]
   {{{#!folding [증명]
   [math(1\mid a,1\mid b)]이므로, 두 수의 최대공약수는 1보다 크거나 같다. 즉, [math(\gcd\left(a,b\right)\geq1)].
   }}}
2. [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))]
   }}}
3. [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|)].
   }}}
4. [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)]일 수밖에 없다. 이로써 보이고자 하는 바가 증명되었다.
   }}}
5. 임의의 정수 [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)]는 같은 공약수 집합을 가지므로 최대공약수도 같아야 한다.
   }}}
6. 베주 항등식: 임의의 양의 정수 [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. 관련 문서

• 약수
• 나눗셈 정리
• 유클리드 호제법
• 최소공배수
• 공약수
• 공배수