정의
유클리드 호제법이란 두 정수 사이에 최대공약수(GCD)를 보다 효과적으로 구하는 것으로, 인류 최초의 알고리즘이라 한다.
두 개 자연수 $A, B$가 있고 $A\ \%\ B = r$이면 다음과 같다. (단, $A > B$)
$GCD(A,B) = GCD(B,r)$
이 때, $A\ \%\ B = r$에 의해 다음과 같은 식이 기본적으로 유도된다.
$A = Bq + r$
증명
두 자연수 $A,B (A > B)$의 최대공약수를 $G$라 하자. $G$는 공약수이므로 두 서로소 $a, b$에 대해 다음 식이 성립한다.
$A = aG, B = bG$
위의 식을 사용하여 $A = Bq + r$에 대입하면 다음과 같다.
$aG = bGq + r$
$r = aG - bGq$
$ r = (a - bq)G$
$A = aG, B = bG$에서 $a, b$가 서로소라면 $G$가 최대공약수이기 때문에 $b, a - bq$가 서로소임을 증명하면 된다.
이를 증명하기 위해서는 가정에 모순을 확인하는 귀류법을 사용하여 해결할 수 있다.
$b$와 $a - bq$가 서로소가 아니라면 두 수는 공약수 $k$를 가지기 때문에 다음과 같이 나타낼 수 있다.
$a - bq = mk$
$b = nk$
위 식의 항을 옮기고 대입하여 정리하는 과정은 다음과 같다.
$a = mk + bq$
$a = mk + nkq$
$a = (m+nq)k$
따라서 다음과 같은 식을 확인할 수 있다.
$a = (m+nq)k$
$b = nk$
하지만 $a$와 $b$는 서로소이나 공약수 $k$를 가지므로 거짓 명제이다.
따라서 $a-bq$와 $b$는 서로소이다.
Reference
[1] https://baeharam.github.io/posts/algorithm/extended-euclidean/
'Computer Science > 사이버 보안' 카테고리의 다른 글
가우스 소거법의 이해 (2) | 2020.03.05 |
---|---|
중국인의 나머지 정리 (0) | 2020.03.04 |
군, 환, 체 (Group, Ring, Field) (0) | 2020.03.04 |
유클리드 알고리즘 확장에 대한 증명 (0) | 2020.03.04 |
기약 잉여계, 완전 잉여계, 오일러 정의 (0) | 2020.03.04 |