[기초 정수론] 09. 최대공약수

1. 최대공약수 정의

정수 c가 존재하여 b=ac를 만족할 때 b는 0이 아닌 정수 a로 나누어진다고 표현하고 a|b라고 쓴다. b가 a로 나누어지지 않는 경우 a ∤ b로 쓴다. 

 1) a는 b의 약수(divisor)

 2) a는 b의 인수(factor)

 3) b는 a의 배수(multiple)

*a|b가 쓰일 경우, 자연적으로 a는 0이 아니다라는 뜻이 내포되어 있다. 

*a가 b의 약수인 경우, 당연히 b는 -a로 나누어진다. (∵ b=ac이면 b=(-a)(-c)) 따라서 정수의 약수는 항상 쌍으로 나타난다.)

 

2. 약수의 기본 성질

정수 a, b, c에 대해 다음이 성립한다. 

(a) a|0, 1|a, a|a

(b) a|1이면 a=±1이다. 그 역도 성립한다. 

(c) a|b이고 c|d이면 ac|bd이다. 

(d) a|b이고 b|c이면 a|c이다. 

(e) a|b이고 b|a이면 a= ±b이다. 그 역도 성립한다. 

(f) a|b이고 b≠0 이면 |a|≤|b|이다. 

(g) a|b이고 a|c이면 임의의 정수 x, y에 대해 a|(bx+cy)이다. 

 

Proof

 

(f), (g)를 증명해보자. 나머지는 독자들에게 맡기겠다. a|b이면 b=ac를 만족하는 정수 c가 존재한다. 또한 b ≠0이므로 c≠0이다. 절대값을 취함으로써, |b|=|ac|=|a||c|. c ≠0이므로, |c|≥1이고 |b|=|a||c| ≥|a|.

(g)를 보면, a|b와 a|c를 통해 b=ar, c=as를 만족하는 적당한 정수 r,s가 있음을 알 수 있다. 어떤 x,y의 선택에 대해

bx+cy=arx+asy=a(rx+sy)

이고 rx+ry는 정수이므로 위에서 a|(bx+cy)를 얻을 수 있다. 

 

2. 공약수

1) a, b가 임의의 정수일 때, d|a, d|b을 만족할 때 d를 a, b의 공약수(common divisor)라 한다. 

2) 1은 모든 정수의 약수이고, a, b의 공약수이므로 공약수 집합은 공집합이 아니다. 

3) 모든 정수는 0을 나누므로, 만약 a=b=0이면 모든 정수는 a, b의 공약수가 될 수 있다. 이 경우 a와 b의 양의 공약수는 무한하다. 

4) 그러나 적어도 a, b 둘 중에 하나는 0이 아니면, 유한한 수의 양의 공약수만이 존재한다. 이 중에서, 가장 큰 수를 a, b의 최대공약수라 한다. 

5) a, b를 적어도 둘 중 하나는 0이 아닌 정수라 하자. a, b의 최대공약수(greatest common divisior)는 gcd(a,b)로 쓰고 다음을 만족하는 양의 정수 d이다. 

(a) d|a, d|b

(b) c|a 이고 c|b이면 c ≤d.

 

3. 선형 조합으로 표현할 수 있는 최대공약수

1)

적어도 하나는 0이 아닌 주어진 정수 a,b에 대해,

gcd(a,b)=ax+by

를 만족하는 x,y가 존재한다. 

 

Proof

a와 b의 선형조합으로 표현되는 양의 정수를 원소로 가지는 집합 S를 보자. 

S={au+bv | au+bv > 0; u,v 정수}

먼저 S가 공집합이 아님을 주목하자. 예를 들어, a≠0이면 |a| = au+b*0은 u를 1 또는 -1로 택할 때 S에 속함을 알 수 있다. 

정렬성의 원리에 의해, S는 가장 작은 원소 d를 가진다. 그러므로 S의 정의에 의해 d=ax+by를 만족하는 정수 x,y가 존재한다. 이제 d=gcd(a,b)임을 보이자. 나눗셈 정리를 이용하면, a=qd+r, 0 ≤r<d를 만족하는 정수 q,r을 얻을 수 있다. 그러면 r은 다음과 같이 표현될 수 있다. 

r=a-qd=a-q(ax+by)

=a(1-qx)+b(-qy)

r이 양이면, 위의 표현은 r이 S의 원소임을 뜻하고 이것은 d가 S의 가장 작은 원소라는데 모순이다. 그러므로 r=0이고 따라서 a=qd이다, 즉 d|a. 비슷한 과정으로 d|b 결국 d는 a, b의 공약수이다. 

이제 c를 a, b의 임의의 양의 공약수라 하면, c|(ax+by)이고 c|d. c=|c| ≤|d|=d 따라서, d는 a, b의 모든 공약수보다 크다. 위의 얘기들을 종합해 보면, d=gcd(a,b)임을 알 수 있다. 

 

2)

a, b가 둘 중 하나는 0이 아닌 주어진 정수라 하면, 집합

T={ax+by| x, y는 정수}

는 정확히 정수 d=gcd(a,b)의 배수로 이루어진 집합이다. 

 

Proof

모든 정수 x, y에 대해 d|a, d|b이므로 d|(ax+by)임을 알 수 있다. 그러므로 T의 모든 원소는 d의 배수이다. 역으로, 적당한 원소 x0, y0에 대해 d=ax0+by0로 표현할 수 있고 d의 임의의 배수 nd는 

nd=n(ax0+by0)=a(nx0)+b(ny0)

로 표현된다. 그러므로, nd는 a, b의 선형 조합이고 정의에 의해 T의 원소이다. 

 

4. 서로소

1) 둘 중 하나는 0이 아닌 두 정수 a,b에 대해 gcd(a, b)=1인 경우 서로소(relatively prime)라 한다. 

 

2) a, b를 둘 중 하나는 0이 아닌 정수라 하자. a, b가 서로소이면 x, y가 존재하여 1=ax+by이다. 역도 성립한다. 

 

Proof

a, b는 서로소 즉, gcd(a,b)=1이라 하자. 그러면 1=ax+by를 만족하는 정수 x,y가 존재한다. 역을 증명하기 위해, ax+by=1을 만족하는 적당한 정수 x, y가 존재한다고 하고 d=gcd(a,b)라 하자. d|a, d|b이므로, d|(ax+by) 또는 d|1이다. d는 양의 정수이므로, 마지막 나눗셈 조건에 의해서 d=1이다. 

 

3)

gcd(a,b)=d이면, gcd(a/d, b/d)=1이다. 

Proof

a/d, b/d는 분수 형태를 취하고 있지만 d가 a, b의 공약수이므로 실제로 둘 다 정수임을 알 수 있다. gcd(a, b)=d임을 알고 있으므로, d=ax+by를 만족하는  x, y를 찾을 수 있다. 양변을 d로 나눔으로써

을 얻고 (a/d), (b/d)가 정수이므로, 이 정리는 적절하다. 따라서 a/d, b/d는 서로소이다. 

 

4) 

a|c, b|c 그리고 gcd(a,b)=1이면 ab|c이다. 

 

Proof

a|c, b|c이므로 c=ar=bs를 만족하는 r,s를 찾을 수 있다. gcd(a,b)=1로부터 1=ax+by를 만족하는 적당한 정수 x,y를 찾을 수 있다. 양변에 c를 곱함으로써, 

c=c*1=c(ax+by)=acs+bcy

우변을 적절히 치환함으로써

c=a(bs)x+b)ar)y=ab(sx+ry)

이고 따라서 ab|c이다. 

 

5. 유클리드 보조정리

1)

a|bc이고 gcd(a,b)=1이면 a|c이다. 

 

Proof

1=ax+by, x, y는 정수라 하자. 양변에 c를 곱하면

c=1*c=(ax+by)c=acx+bcy

을 얻고 a|ac이고, a|bc이므로 a|(acx+bcy) 다시 쓰면 a|c이다. 

 

 

2)

a, b를 둘 중 하나는 0이 아닌 정수라 하자. 양의 정수 d에 대해 d=gcd(a, b)와 아래 명제는 필요충분조건이다. 

(a) d|a, d|b

(b) c|a, c|b이면 c|d이다. 

 

Proof

일단 d=gcd(a,b)라 하자. 당연히 d|a, d|b이므로 (a)는 성립한다. 적당한 정수 x,y에 의해 d=ax+by로 표현된다. 그러므로, c|a이고 c|b이면 c|(ax+by) 또는 c|d이다. 간단히 말해, (b)도 참이다. 역을 증명하자, d가 주어진 조건 (a), (b)를 만족하는 정수라 하자. a,b의 임의의 공약수 c에 대해 (b)로부터 c|d이다. 따라서 d≥c이고, 결론적으로 d는 a,b의 최대 공약수이다.