2. 유클리드, 확장 유클리드

관련 코드는 github에서 찾아볼 수 있다.

이 주제는 이미 좋은 자료가 있습니다. https://casterian.net/archives/601

이 글은 유클리드 알고리즘은 이미 어느 정도 숙지한 독자를 위해 작성하였다. 유클리드 알고리즘 관련 자료 역시 많다.

글의 핵심 목적은 유클리드 알고리즘의 핵심 아이디어 2개를 짚고, 확장 유클리드 알고리즘도 사실 별반 다를 거 없다는 것을 주장하는 것이다.

앞쪽 내용인만큼 제대로 이해해야 뒤 내용을 이해할 수 있으니, 시간을 많이 투자해보자. 

유클리드 알고리즘은 자연수 $a, b$가 주어졌을 때, $\text{gcd}(a, b)$를 구하는 방법이다. 결국 핵심 아이디어는

• 아이디어 1. 몫, 나머지를 구하여 $a = bq + r$로 쓰자. 이때 $\text{gcd}(a, b) = \text{gcd}(b, r)$이다. 
• Why? $g|a$, $g|b$가 성립한다고 가정하면 $g|(a-bq)=r$이므로, $g|b$, $g|r$.
• 반대로 $g|b$, $g|r$이 성립한다고 가정하면 $g|(bq+r)=a$이므로, $g|a$, $g|b$. 
• 즉, $g$가 $a, b$의 공약수인 것과 $g$가 $b, r$의 공약수인 것은 완전히 동치이다. 그러니 최대공약수 역시 동일.

• 아이디어 2. 위 사실은 문제를 $(a, b)$에서 $(b, r)$로 "축소"하는 방법을 제시해준다. 즉, $\text{gcd}(a, b)$를 구하는 문제를 $\text{gcd}(b, r)$을 구하는 문제로 축소.
• 얼마나 줄어들까? $a \ge b$를 가정하자. 그러면 $q \ge 1$이며 $2r \le (q+1)r = rq + r \le bq + r = a$이므로 $2r \le a$.
• 그러므로, $br \le (1/2) ab$임을 얻는다. 즉, 문제를 정의하는 두 인자의 곱이 적어도 반 이상은 감소한다.

두 아이디어를 합치면, 로그 시간을 거쳐서 최대공약수를 얻는 방법이 완성된다.

$(a, b)$를 $(b, r)$로 변환하는 과정을 거치면, 로그 시간 이내에 $(g, 0)$ 형태의 순서쌍을 얻는 것이 보장되기 때문이다.

이 시점에서 $\text{gcd}(a, b) = g$를 얻고, 알고리즘을 종료시키면 된다. 여기서부터는 구현의 문제다.

• Example. $\text{gcd}(576, 204)$를 구한다고 가정하자. 다음 과정을 거친다.
• $576 = 204 \times 2 + 168$이므로, $(576, 204)$에서 $(204, 168)$로 문제를 축소
• $204 = 168 \times 1 + 36$이므로, $(204, 168)$에서 $(168, 36)$으로 문제를 축소
• $168 = 36 \times 4 + 24$이므로, $(168, 36)$에서 $(36, 24)$로 문제를 축소
• $36 = 24 \times 1 + 12$이므로, $(36, 24)$에서 $(24, 12)$로 문제를 축소
• $24 = 12 \times 2 + 0$이므로, $(24, 12)$에서 $(12, 0)$으로 문제를 축소. 답은 이제 $12$. 

아이디어 1, 2는 CP/PS의 많은 정수론 문제에서 사용되는 아이디어다. 이를 유클리드 알고리즘의 활용에서 다룬다.

확장 유클리드 알고리즘은 자연수 $a, n$이 주어졌고 $\text{gcd}(a, n) = 1$일 때, $ax \equiv 1 \pmod{n}$인 $x$를 찾는 알고리즘이다.

(엄밀하게 말하자면, 자연수 $a, b$에 대하여 $ax + by = \text{gcd}(a, b)$인 $x, y$를 찾는 알고리즘이다. 사실상 똑같은 말)

이 문제를 바라보는 가장 정석적인 방법은 변수를 하나 추가하는 것이다.

• $ax \equiv 1 \pmod{n}$이라는 것은, 정수 $y$가 있어 $ax + ny = 1$이라는 것과 동치이다.
• 그러니 사실 우리는 $ax + ny = 1$을 만족하는 정수 순서쌍 $(x, y)$를 찾으면 된다. 
• 여기서 우리가 $\text{gcd}(a, n) = 1$이라는 조건을 추가한 이유도 알 수 있다. 위 식의 좌변이 무조건 $\text{gcd}(a, n)$의 배수이기 때문.

목표는 이제 $\text{gcd}(a, b) = 1$을 가정하고 $ax + by = 1$을 푸는 것이다. 문제를 바라보는 새로운 시각을 얻었으니, 위 아이디어 1, 2를 적용해보자.

• 아이디어 1. 몫, 나머지를 구하여 $a = bq+r$로 쓰자. $a, b$에 대한 문제를 $b, r$에 대한 문제로 바꿀 수 있는가?
• 가능하다. $ax + by = 1$은 $(bq+r)x + by = 1$과 동치이며, 정리하면 $b(qx+y) + rx = 1$로 쓸 수 있다.
• 그러니, $bx'+ry'=1$인 정수 순서쌍 $(x', y')$을 구하면, $qx + y = x'$, $x = y'$을 풀어 $ax + by = 1$인 $(x, y)$를 얻는다.
• 위 식을 다시 정리하면, 결국 $x = y'$, $y = x' - qy'$이므로, 이 순서쌍 $(x, y)$는 정수 순서쌍이다. 
• 이는 $(b, r)$에 대한 문제를 풀면, 빠르게 $(a, b)$에 대한 문제를 풀 수 있음을 의미한다.

• 아이디어 2. 역시 아이디어 1은 문제 축소의 의미를 담는다. 기존 유클리드 알고리즘에서 한 논의가 그대로 성립한다.
• 결과적으로, 위 과정을 로그번 거치면 결국 $(1, 0)$에 대한 문제를 해결하는 것으로 문제가 환원된다. 이는 $x=1, y=0$이라는 해가 있다.

두 아이디어를 합치면, 로그 시간을 거쳐서 조건을 만족하는 $x$를 찾을 수 있다. 이를 modular inverse라고 부르며, 이는 유일하게 존재한다.

알고리즘을 설명하는 과정에서 $ax + by = 1$을 만족하는 정수 순서쌍 $(x, y)$가 존재함까지 증명했음을 참고하자. 

나아가면, $ax + by = \text{gcd}(a, b)$인 $x, y$가 존재함을 얻는다. 이를 Bezout's Identity라고 한다.

• Example. $3x \equiv 1 \pmod{7}$을 만족하는 $x$를 구해보자.
• $3x + 7y = 1$인 정수 순서쌍 $(x, y)$를 찾으면 충분하다. 
• 이는 $3(x+2y) + y = 1$과 같다. 그러니 이제 $3a + b = 1$인 정수 순서쌍 $(a, b)$를 찾자.
• 이는 $1(3a+b) + 0a = 1$과 같다. 이제 $3a + b = 1$, $a = 0$을 풀어 $a = 0, b = 1$을 얻는다.
• 다시 위로 돌아가서, $3(x+2y) + y = 1$을 $3a + b = 1$로 변환한 것을 생각해보자.
• 우리의 목표는 이제 $x + 2y = 0$, $y=1$. 이를 풀면 $x= -2$와 $y = 1$을 얻는다.
• 실제로 $3(-2) \equiv 1 \pmod{7}$임을 쉽게 확인할 수 있다.

구현 노트.

• $ax+by=1$이면, 각 정수 $t$에 대하여 $a(x+bt) + b(y-at) = 1$이 성립한다. 즉 $(x+bt, y-at)$ 역시 해.
• $t$를 잘 잡아서, $x+bt$가 $0$ 이상 $b$ 미만이 되도록 할 수 있다. overflow 방지를 위해 필요한 작업이다.
• 즉, 해를 재귀적으로 계산하는 과정에서, 해가 지나치게 크거나 작아지지 않도록 하는 과정이 필수적이다. 
• 위 Example을 보면 느낌이 오겠지만, 이 알고리즘은 재귀적으로 작성하는 것이 정신건강에 좋다.

더 나아가면, 아무런 가정 없이도 $ax \equiv b \pmod{n}$과 같은 식을 해결할 수 있다.

• 마찬가지 아이디어로, $ax + ny = b$라는 식을 해결하는 것으로 문제를 바꾸자.
• $g = \text{gcd}(a, n)$을 유클리드 알고리즘으로 구하자. 위 식의 좌변 $ax+ny$는 무조건 $g$의 배수임을 알 수 있다.
• 그러니, $b$가 $g$의 배수가 아니라면 해가 없음을 바로 알 수 있다. 
• 이제 $g|b$를 가정하고, 식을 $(a/g)x + (n/g)y = (b/g)$로 써보자. 이제 $\text{gcd}(a/g, n/g) = 1$이다.
• 확장 유클리드 알고리즘으로, $(a/g)x' + (n/g)y' = 1$인 정수 순서쌍 $(x', y')$을 찾을 수 있다.
• 이제 $x = (b/g)x'$, $y = (b/g) y'$을 선택하면 $ax + ny = b$임을 알 수 있다.
• 또한, $(x, y)$가 해라면 $(x + n/g \cdot t, y - a/g \cdot t)$ 역시 각 정수 $t$에 대하여 해임을 알 수 있다.
• 즉, $x \equiv \text{something} \pmod{n/g}$ 형태의 해를 얻는다. 자세한 디테일은 github 참고.

• Example. $12x \equiv 18 \pmod{54}$를 해결해보자.
• $12x + 54y = 18$을 해결하면 충분하다. $\text{gcd}(12, 54) = 6$임을 유클리드 알고리즘으로 계산한다.
• $18$은 $6$의 배수이니, 해가 존재한다. 식을 $6$으로 나누어주자. $2x + 9y = 3$을 얻을 수 있다.
• 이제 $\text{gcd}(2, 9) = 1$이니, $2x' + 9y' = 1$인 $x', y'$를 확장 유클리드 알고리즘으로 찾을 수 있다.
• $x'=5$, $y'=-1$을 찾았다고 하자. 이제 이 값을 $3$배 해주면 $x = 15$, $y = -3$을 얻는다.
• 이제 $x \equiv 15 \pmod{9}$, 또는 $x \equiv 6 \pmod{9}$가 답이 된다. 끝!  

사실 위 논의에서 일부 엄밀한 수학적 논의를 생략했다. 내용을 추가할 겸 간략하게 설명한다.

• 우리는 이미 확장 유클리드 알고리즘으로 $\text{gcd}(x, y) = 1$이면 $ax+by=1$인 정수 $a, b$가 존재함을 안다. (엄밀하게 증명한 것은 아니나, 나름 합리적으로 유도했다. "수학자들의 증명"을 원하면 당연히 정수론 책 참고.) 이를 통해 $\text{gcd}(a, b)=1$, $a|c$, $b|c$가 성립하면 $ab|c$가 성립함도 증명할 수 있다. 또한, $a|bc$이고 $\text{gcd}(a,b)=1$이면 $a|c$가 성립함도 증명할 수 있다. 특히, $g=\text{gcd}(a, b)$라면 $\text{gcd}(a/g, b/g)=1$이니 $a|bc$에서 $(a/g)|(b/g)c$를 얻고, 즉 $(a/g)|c$임 역시 얻을 수 있다. 즉, $a/\text{gcd}(a,b)$가 $c$의 약수가 되어야 한다. 이 "증명할 수 있다"라는 부분을 자세히 알고 싶다면 정수론 책 참고 or 댓글로 질문. 이 정도 내용은 알아야 정수론 문제 해결에 지장이 없을 것이라고 생각하여 추가한다.

• modular inverse는 유일한가? $x, y$가 모두 $\pmod{n}$에 대한 $a$의 modular inverse라고 하자. 그러면 가정 상 $\text{gcd}(a, n)=1$이고 $n|(ax-1)$, $n|(ay-1)$이니 두 식을 빼면 $n|a(x-y)$를 얻는다. 한편, $a|bc$이고 $\text{gcd}(a, b)=1$이면 $a|c$임이 알려져 있다. 그러므로 $n|(x-y)$를 얻고 $x \equiv y \pmod{n}$이 성립한다. 즉, modular inverse는 ($n$으로 나눈 나머지를 보았을 때) 유일함을 얻는다. 증명 끝.
• $ax \equiv b \pmod{n}$의 해는 정말 저게 다인가? $ax+ny=b$를 생각할 때, $(x, y)$가 해라면 $(x + n/g \cdot t, y - a/g \cdot t)$가 해임은 직접 대입을 통해서 자명하게 얻을 수 있다. 이것들만이 해라는 것 역시 보여야 한다. 만약 $ax+ny = ax'+ny'=b$라면, $a(x-x')=n(y'-y)$가 된다. 여기서 $x-x'$이 $n/g$의 배수, $y-y'$이 $a/g$의 배수임을 증명할 수 있다. 즉, 해가 되려면 $(x + n/g \cdot t, y - a/g \cdot t)$ 형태를 가져야 한다. 증명 끝.