강의실/정보영재

유클리드 호제법은 2개의 자연수 또는 정수의 최대 공약수를 구하는 알고리즘의 하나 입니다.

정보올림피아드에서 2개의 최대 공약수를 구하는 문제가 종종 나오는데...

이때 유클리드 호제법을 이용해서 문제를 풀어 나가면 훨씬 빠르고 유용하게 사용할 수 있습니다.

예를 들면 131 과 109 의 최대 공약수를 구하는 문제같은 경우 131이 3의 배수인지 아닌지 판단 하고 109가 3의 배수인지 아닌지 판단 하는 것보다는 다음과 같이 구하면 훨씬 수월하게 풀릴것 같네요.

131 % 109 = 22 이므로

22 와 109 의 최대공약수와 동일 하고...

109 % 22 = 21 

따라서 22와 21의 최대 공약수와 동일 하기 때문에 최대공약수는 1이 나오게 됩니다.

131이 소수인지 아닌지 판단 하는 것보다 이렇게 판단하는 것이 훨씬 덜 고민이 되는 방향이 아닐까요?

이것보다 더 큰 소수가 나올때 더 유용할것 같네요.


그러면 유클리드 호제법의 정의에 대해 알아 보겠습니다.


유클리드 호제법의 정의는 a와 b의 두수가 있다고 하면 

a와 b의 최대공약수는 b와 a를 b로 나눈 나머지 r의 최대 공약수와 같다는 성질을 이용한 것입니다.


이 원리는 기원전 300년 경에 쓰인 유클리드의 원론에 기록되어 있다고 하는데요.


오늘은 유클리드 호제법에 대해 증명을 해 보도록 하겠습니다.

a 와 b 의 두 수가 있고 a를 b로 나눈 나머지 r 이 있다고 하면 어떤수를 q라고 가정하면

a = q * b + r 과 같이 표현을 할 수가 있습니다. 

이때 0 <= r < b 입니다.


여기서 a,b 의 두수의 최소 공배수 k 가 있다고 하면

a = mk, b = nk 로 나타낼수 있는데요 이때 m과 n은 서로 소입니다.

그러면 다음과 같이 표현할 수 있겠네요. 어떤 수를 q라고 하면

mk = q * nk + r

r = mk - qnk = (m-qn) * k 로 표현 할 수 있습니다.

즉 r은 a와 b의 최대 공약수인 k를 가슴에 품고 있다는 것입니다

즉 (m-qn)을 l 이라고 가정하면 r = l * k 가 되는 것입니다.

여기서 b=nk의 n 과 m-qn 이 서로소인것을 증명하면 됩니다.(a 와 b의 최대공약수는 b와 r의 최대공약수가 같음을 증명하기 때문에)


만약에 서로소가 아니라고 가정을 하면

n=xG, m-qn = yG 와 같이 공통인 G(G는 1이 아닌수) 가 있다고 하면

m - qn = m - q*xG = yG

m=yG + qxG =(y+qx)*G 와 같이 나타낼수 있습니다.

따라서 m은 G의 배수이고 n도 G의 배수가 됩니다.

m - qn 을 계산하면 m과 n의 공약수 G의 값으로 계산을 하면 G의 배수의 값이 남을수가 없게 됩니다. 

따라서 n과 m-gn 이 서로소가 될수 밖에 없습니다.


따라서 a와 b의 최대공약수는 b와 r의 최대공약수와 같습니다.


이것을 c언어의 재귀함수 방법으로 프로그래밍을 하면 다음과 같습니다.


long long gcd(long long a,long long b)

{

      if(b==0) return a;

      return gcd(b,a%b); //여기서 r = a % b 입니다.

}



이 장소를 Daum지도에서 확인해보세요.
인천 서구 당하동 1028-2 장원프라자 502호 | 원당컴퓨터학원
도움말 Daum 지도
  • 휴식같은 친구 2018.11.09 22:21 신고    

    어렵네요.
    이런 어려운 문제를 알고리즘으로 풀다니 대단하네요.

  • Deborah 2018.11.09 22:27 신고    

    전 잘 모르겠네요. 한참을 봤습니다.
    알리고즘으로 풀어나가는 것을 보니 참 좋은데요.
    새로운 것을 배웁니다.

  • 유하v 2018.11.10 02:01 신고    

    봐도봐도 어렵네요ㅜ

  • 버블프라이스 2018.11.10 02:52 신고    

    저도 어렵네요..
    유클리드 호제법 증명 글 참고만 하고 갑니다^^
    따뜻한 주말 보내시길 바래요

  • *저녁노을* 2018.11.10 04:56 신고    

    와...이런걸 어캐 풀어용? ㅎㅎ
    정말 어렵네요

  • 핑구야 날자 2018.11.10 06:53 신고    

    유클리드 호제법은 처음 듣는 내용이네요 그래서 그런지 좀 어렵지만 잘 배우고 갑니다

  • 청결원 2018.11.10 07:06 신고    

    즐거운 주말이네요~
    주말 잘 보내시고 포스팅 잘 보고 갑니다

  • 공수래공수거 2018.11.10 11:32 신고    

    조금 어려운 내용입니다. ㅎ
    즐거운 주말 되시기 바랍니다.

  • 행복사냥이 2018.11.10 22:37 신고    

    어렵네요. 잘 보고 갑니다.^^

  • 유하v 2018.11.11 18:11 신고    

    컴퓨터 알고리즘을 공부하는 학생들에게 큰 도움이 될것 같네요!

  • 핑구야 날자 2018.11.12 06:45 신고    

    유클리드 호제법 처음 들어보는데요 덕분에 잘 알고 갑니다