Mathematics/Major

[정수론] 두 수의 최대공약수, 서로소 구하기(유클리드 알고리듬 +c언어 소스)

uwang 2012. 4. 28. 03:23

정수론은 1학년 2학기때 들었던 전공과목이다.....

그때 사실 교수님의 목소리가 들리지않아서...........ㅠ.......책보고 따로 공부해서 중간기말을 쳤던기억이........

그리고 학점은.....하늘나라롴ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ1~2학년때는 정말 열심히 놀았던 기억이난다ㅠㅠ..

정수론의 대충 간단한 내용들은 알지만 증명과 그 뒷부분에서 멘붕ㅋ...다음학기나 내년에 청강한번 해야겠다ㅠㅠ

시험기간이나 과제할때 알고리즘 트레이닝 사이트인 '더블릿'을 들어가서 한두문제씩 풀며 스트레스를 푼다 ㅠㅠ

뭔가 풀때마다 기분이 좋아지니깤ㅋㅋㅋㅋㅋㅋㅋㅋ..............(사실 그래서 그럴때 문제풀때는 옥상에서 어려운건 안본닼...그건 시간날때..)

더블릿 문제중 최대공약수와 서로소 문제들이 있길래 포스팅 하게되었다. 이걸 이용하면 코딩이 훨씬 간단해진다.

이걸 모른다면....1부터 하나하나 대입하는ㅋ.........방법도있지만....비효율적이다.

컴퓨터과학과 2학년전공중에 수치계산이란 과목이 있는데 거기서도 정수론이 조금 나온다. 그리고 그걸 이용해서 c프로그래밍도하고..나름 재밌게 들었던 과목이였다..

서론이 길었고 일단 포스팅을 하자면....

 

최대공약수란 두 수의 공통된 약수(=공약수)들중 최대의 공약수를 최대공약수라 한다.

내가 8과 10의 최대공약수를 구하고 싶다고 가정하자

8의 약수는 1, 2, 4, 8이 존재한다.

10의 약수는 1, 2, 5, 10이 존재한다.

 그렇다면 이 둘의 공약수는 1과 2라는 것을 알수 있다.

공약수중에서 최대값은 2이므로 최대공약수는 2라는 것을 알수있다.

이들중 최대공약수가 1인 두 수도 존재한다. 이 것을 서로소라한다.

예를들면 4와 7은 서로소이다.

4의 약수는 1, 2, 4이고 7의 약수는 1, 7이다. 이들의 공약수는 1이고 최대공약수도 1이다.

최대공약수는 영어로 greatest common divisor인데 이들의 약자인 gcd를 따서 gcd(a,b)라고 쓴다.

그리고 다음을 만족하는 양의정수를 d라 한다. 

ex) 4와 7의 최대공약수는 1이다. => gcd(4,7) = 1

 

최대공약수를 구하기 위해서 저렇게 일일히 두 수 각각의 약수를 구해서 최대공약수를 찾아도 되지만,

수가 커질경우에 저런 방법을 이용해서 최대공약수를 찾는데 시간이 꽤 소요되며 비효율적이다.

그래서 쓸수 있는 방법이 유클리드 알고리듬(Euclidean Algorithm)이다.

유클리드 알고리듬은 나눗셈의 정리를 이용해서 최대공약수를 찾는 방법인데 나눗셈의 정리의 증명은 다음번에 포스팅을.....ㅠ

나눗셈의 정리를 간단하게 보자면,

주어진정수 a, b에 대해 , b>0. 다음을 만족하는 유일한 정수 q,r이 존재한다.

이다. q는 목, r은 나머지이다.

나머지가 존재하지 않을때에는

a = qb + 0이므로 a = qb이다.

즉, a = qb를 만족할 때 a는 0이 아닌 정수 b로 나누어진다라고 표현하고 

라고 쓴다. r이 0이 아닐경우에는 a는 정수 b로 나누어지지 않으므로

라고 쓴다.

 

유클리드 알고리듬은 이걸 이용해서 최대 공약수를 구하는 것이다.

에서 r1 = 0 이라면 b | a이므로 g(a,b) = b (a와 b의 최대공약수가 b) 이다.

r1이 0이 아니라면 b를 r1으로 나눔으로써 정수 q2, r2를 얻을수 있는 나눗셈의 정리와 같은 식이 존재할 것이다.

예를들면, 정수 10이 있다고 하자 10을 4으로 나누었을때 몫은 2이고 나머지는 2이다.

즉, 10 = 2 *4 +2 이다. 여기서 a=10, q1=2, b=4, r1=2이다.

그렇다면 4를 2로 나눌수도 있다.   4 = 2*2 +0과 같이 쓸수있다.

즉,

이 식과 같은 말이다.

이와 같이 나머지가 0이 나올때까지 반복할수 있다.

여기서  이  와 같다는것이 유클리드 알고리듬이다.( a와 b의 최대공약수는 rn이라는 것)

이것들은

라는 것을 r이 0이 되기 전까지 반복해준 것이다.

증명은 다음 나눗셈정리를 포스팅할때 적겠다.....

일단 유클리드 알고리듬이란 이런것이고,

예로 유클리드알고리듬을 이용해 12378과 3054의 최대공약수를 구해보자면, 

12378 = 4* 3054 + 162

3054 = 18*162 + 138

162 = 1*138 + 24

138 = 5*24 + 18

24 = 1*18 + 6

18 = 3*6 + 0 이므로

12378과 3054의 최대공약수는 6임을 알수 있다.

최대공약수를 구할수 있다면 두 수가 서로소임을 알수도 있다.

유클리드 알고리듬을 이용해 최대공약수가 1인 것들은 서로소이기 때문이다.

 

유클리드 알고리듬을 이용해 c소스를 간단하게 짜보자면

 다음과 같다.

 

이걸 실행시켜보면,

1) 서로소일경우

2) 서로소가 아닐경우 (최대공약수도 출력해줌)