유클리드 알고리즘 관련 정리

GitHub - hijkl2e/problem_solving: 알고리즘 문제 해결

유클리드 알고리즘은 프로그래밍 초심자에게도 익숙한 알고리즘이다.

많은 프로그래밍 교재에서 while 문의 예제로 유클리드 알고리즘을 사용한다.

하지만 유클리드 알고리즘의 정당성 및 시간 복잡도 증명은 거의 다루지 않는다.

교재의 목적과 부합하지 않게 다소 복잡한 면이 있기 때문이다.

 

본 문서에서는 유클리드 알고리즘과 관련된 정리들의 증명을 다루었다.

나의 학습 목적으로 작성하였기 때문에 친절하지는 않다.

(자연어를 사용하지 않고 기호로만 수식을 작성하는 것은 올바르지 못한 습관이다.)

 

이 문서의 순서는 다음과 같다.

• Theorem 1에서는 gcd(a,b)를 ax+by의 꼴로 표현할 수 있음을 증명한다.
• Theorem 2에서는 유클리드 알고리즘의 정당성을 증명한다.
• Theorem 3-5에서는 유클리드 알고리즘의 시간 복잡도를 증명한다.
• Theorem 6에서는 확장 유클리드 알고리즘의 정당성을 증명한다.
• Theorem 7에서는 선형 디오판토스 방정식의 일반해를 증명한다.

Theorem 1-3은 CLRS 3판을 참고하였으나 나의 기호에 맞게 일부 내용을 추가하거나 삭제하였다.

Theorem 4-7은 직접 증명하였기 때문에 올바르지 않은 부분이 있을 수 있다(제보 부탁드립니다).

 

유클리드 아저씨와 함께 재미있는 정수론 공부를 시작해보기를 바란다.

 

끝