[대수학&정수론]유클리드 호제법의 증명

※이 글을 읽기 전에 알아야 할 기호

​

gcd : '최대공약수'의 기호입니다.

표기 예시를 들어보자면,

​

gcd(x,y)는 x와 y의 최대공약수

gcd(l,m,n)은 l,m,n의 최대공약수

​

p.s.최소공배수는 lcm이고 쓰는 법은 같아요~

​

​

​

​

​

​

유클리드 호제법이란?​

​

​

​

뭔가 이름만 들어도 여러모로 머리가 아픈 유클리드 호제법!

​

유클리드 호제법은 두 다항식 또는 자연수 사이의 최대공약수를 구할 때 자주 등장하는 유용한 녀석이에요!

​

​

(물론 수학 교육 과정에는 없습니다 쿨럭)

​

​

​

​

​

​

​

정수론 공부나 KMO 준비를 하시는 분들은 다들 한 번씩 접해보셨을 편리한 도구인데요!

​

일단 증명은 아래로 미루고 결과를 먼저 보도록 합시다앗!

​

​

​

​

"a>b인 두 양의 정수 a,b에 대하여,

a=qb+r(나머지 r은 0 이상 b 미만,q는 몫)

이라 하면,

gcd(a,b)=gcd(b,r)

(a,b의 최대공약수=b,r의 최대공약수)이다."

​

​

​

​

'흐음 저게 어디가 유용하다는 거지..?'

​

싶으신 분들을 위해 예시를 몇가지 들어볼까요?

​

​

​

'1071과 1029 사이의 최대공약수는 21이다.'

​

이 상황에서 간단한 계산식 두 세 번이면

이를 계산할 수 있게 해주는 것이 바로

유클리드 호제법!!

​

​

​

정말 탐나지 않나요옷!

​

​

​

바로 증명 들어갑니다앗ㄱㄱ

​

​

​

​

​

유클리드 호제법의 증명 ​

​

일단 a>b인 두 양의 정수 a,b를 잡아줍시다!

​

여기서 구하고 싶은건 바로 최대공약수니까

얘도 G로 잡아주도록 할게요!

​

​

​

​

​

따라서 이렇게 되면 a,b는 당연히

G의 배수가 되겠지요?

그러면 요렇게 되겠네요!

​

​

여기서 대문자인 A와 B는 몫입니다!

최대공약수 G로 나누니까 나머지는 없구요!

​

​

​

​

여기서 중요한 게 뭐냐면,

​

'A와 B는 서로소'

​

라는 사실이에요.

​

​

​

만약 A와 B가 서로소가 아니라면,

G는 더 이상 최대공약수가 아니니까요!

사실 당연한 말!

​

(최대공약수는 모든 공통 약수를 가져가야 하기 때문에, 남은 것에 공통 약수가 있을리는 없죠)

​

​

​

​

자아 이 정도 해두면 좋습니다!

​

다음 과정으로 넘어가볼까요?

​

​

​

​

a>b이기 때문에,

b로 a를 나눌 수 있으니까

​

계산식을 써주면 몫 q와 나머지 r이 나오네요!

​

​

​

​

이제 여기에 a=AG,b=BG를 대입해도

식이 성립하겠군요!

​

그러면 바로 대입 ㄱㄱ

​

​

​

​

이건 뭐 그냥 대입만 했으니까 별 거 없네요.

​

이제 식에 변형을 좀 줘봅시다.

​

​

​

​

​

자 이거는 아주 쉽게 이해하실 거에요!

​

1.qBG 이항

2.G로 묶기

​

가 되었네요!

​

​

​

​

​

근데 제가 아까 b=BG라고 했죠?

​

​

​

이렇게 되면 아래와 같아지겠군요!

아까 b의 정의에 따르면,

​

둘 사이에는 G라는 공통의 약수가 생기게 되는 것을 어렵지 않게 알 수 있군요!

​

​

​

​

​

​

자아 근데 유클리드 호제법을 증명하기 위해서는

​

b와 r에 있는 G 저 친구가

'최대공약수'가 되어야 하겠네요!

​

​

​

​

그래야지만 a,b의 최대공약수 G가

b,r의 최대공약수와 같아지니까요!

​

결국 그게 유클리드 호제법이죠?

​

​

​

​

자 그렇게 되면,

이 두 녀석이 서로소임을 증명하기만 하면

​

우리가 원하는 유클리드 호제법이 증명되는 겁니다!

​

​

​

​

​

​

​

근데 잘 생각해보시면,

​

1. 서로소가 아니다.

2. 서로소이다.

​

두가지 중 하나의 결과가 맞는 것 아니겠어요?

​

​

​

​

​

​

​

그러니까 우리는 2가 맞는 사실을 보이려면,

​

1) 2가 맞다.

2)1이 틀렸다.

​

둘 중 하나만 증명해도 결국 증명된 거 아니겠어요!

​

​

​

​

​

​

1과 2중 하나만 정답이라는 것인데,

​

1이 틀렸다면 당연히 정답은 2겠죠!

​

​

​

​

​

​

​

따라서 우리는 1번,

​

즉 '서로소가 아니다' 라는 사실이 틀렸음을 보이면 된다는 것이지요.

​

​

​

​

​

​

​

​

그렇다면 '서로소가 아니다' 라는 사실이 틀렸음을 알기 위해서는

​

서로소가 아니게 가정을 했을 때

'모순'이 발생한다면,

​

즉 논리적으로 안 들어맞는 개소리가 생긴다면,

​

곧 그 가정이 틀린 가정임을 알려주는 거 아니겠어요?

​

​

​

​

​

​

​

자 이제 그럼 그 놈의 모순이란 걸 보여보도록 합시다.

​

​

(참고로 이런 식의 논리 흐름을 통해 명제를 증명하는 것을 '귀류법' 이라고 합니다.

자주 쓰이는 중요한 개념이에요!)

​

​

​

​

​

​

​

두 수가 서로소가 아니라고 했으니,

1보다 큰 최대공약수인 t가 존재한다는 것이겠지요!

​

(물론 m,n은 당연히 몫입니다~)

​

​

​

​

​

​

그럼 이제 B를 대입해 보시면,

당연히 이렇게 나오겠네요!

​

​

​

​

​

​

​

이 식을 조금 변형시켜본다면,

자아 근데 여기서 모순이 발생합니다앗!!

​

​

​

​

​

​

​

우리가 A와 B는 서로소라고 했던 것 기억나시나요?

​

까먹으신 거 아니겠지!!

위에 진한 글씨로 강조했는데!

​

​

근데 결과는 서로소가 아니라고 나오네?

엥???

​

​

​

​

​

​

​

요것이 바로 모순입니다.

​

결과가 개소리니까 가정도 개소리가 되는 것이고,

​

따라서 우리는 유클리드 호제법을 증명해냈습니다! 짝짝

​

​

​

​

​

​

​

이제 증명도 했겠다, 위에 든 예시를 직접 계산해보며 사용법 감을 익혀보죠!

​

​

​

​

​

​

​

​

​

유클리드 호제법 사용 예시

​

아까 제가 1071과 1029 사이의 최대공약수가

21이라고 했던 사실 기억나시나요?

​

요것을 한 번 직접 계산해보자구요!

​

​

​

​

​

a=qb+r이라고 했었죠? 그럼 똑같이

​

1071=1×1029+42

​

여기서 a,b의 최대공약수,

즉 1071과 1029의 최대공약수는,

​

b,r의 최대공약수인,

1029와 42의 최대공약수와 동일합니다!

​

​

​

​

​

​

따라서 1029와 42 사이에 또 같은 방법을 취해주더라도,

​

새로 만들어지는 b,r의 최대공약수가 결국

gcd(a,b)와 동일해지겠죠!

​

​

​

​

​

​

따라서 또 한 번 적용해주면,

​

1029=24×42+21

​

그러면 gcd(b,r)=gcd(42,21)이 결국 답이 되네요!

​

(헷갈리실 까봐 적는 것인데 24는 그냥 몫이에요!

하던대로 나눠서 계산해보시면 됩니다.

유클리드 호제법에서 딱히 중요한 부분 아니에욧)

​

​

​

​

그러면 42와 21의 최대공약수는

너무 쉽게도 21입니다!

​

계산 끝!

​

​

​

​

​

​

​

​

"a>b인 두 양의 정수 a,b에 대하여,

a=qb+r(나머지 r은 0 이상 b 미만,q는 몫)

이라 하면,

gcd(a,b)=gcd(b,r)

(a,b의 최대공약수=b,r의 최대공약수)이다."​

​

​

어떠신가요? 이제 이 말이 좀 눈에 들어오시나요?

​

(참고로 나머지 r의 조건은 당연한 거에요!

나머지가 나눈 수보다 크면 덜 나눠진 거잖아요!)

​

​

​

​

​

​

​

​

​

​

지금까지 장문 봐가면서 이해하려 노력하신

독자 분들께 박수를 보냅니다.

​

오늘도 수학 지식이 더 풍부해지셨습니다앗!

​

저는 이만! 열공~

​

​

​

​

​