4. 정수론: 최대공약수 (Number Theory: Great Common Divisor)

정수론이란, 정수의 성질을 연구하는 학문이다. 정수론은 주로 현대 암호학에 응용된다.

물통 채우기

$(a\leq b)$인 $a$리터 물병과 $b$리터 물병을 이용해 $m$리터 물통을 채워야 하는 문제를 생각해보자.

• $m|a$: $a$는 $m$으로 나누어 떨어진다.
• $\text{iff (if and only if)}$: 필요충분조건

$$ \text{Def 1.} m|a \text{, iff } \exists k \in \mathbb{Z}, a=km $$

$a =km$이 성립하는 정수 $k$가 존재할 때, $a$는 $m$으로 나누어 떨어지고 $m|a$처럼 나타낼 수 있다.

$$\text{Theorem 1. if } m|a \text{ and } m|b \text{, then } m|\text{any possible result with a and b jug} $$

상태 기계 설계^{State Machine Modeling}

두 물병에 든 물의 양을 $(x,y)$꼴의 상태로 나타내는 모델을 생각해보자.

이 기계에서, 우리는 세 가지 변화를 취할 수 있다.

1. (가득) 비우기: $(x,y)$ -> $(0,y)$ 혹은 $(x,0)$
2. (가득) 채우기: $(x,y)$ -> $(a,y)$ 혹은 $(x,b)$
3. 옮겨담기: $(x,y)$ -> $(0,x+y)$, $(x+y, 0)$, $(x+y-b, b)$ 혹은 $(a, x+y-a)$

예시: $a=3, b=5$인 경우

$m|a, m|b$인 $m$은 1이 유일하다. 1로는 어떤 값이든 만들 수 있다.

$$(0,0) \rightarrow (0,5) \rightarrow (3,2) \rightarrow (0,2) \rightarrow (2,0) \rightarrow (2,5) \rightarrow(3,4) $$

4리터의 물을 얻는데 성공했다!

귀납법으로 $\text{Theorem 1}$ 증명하기

귀납법을 사용하기 위해, 가설을 $P(n)$꼴로 만들어준다.

$$P(n): \text{ for any }n\geq0 \text{, }m|a \text{ and } m|b. \text{If (x,y) is the state after }n\text{ transitions, then }m|x \text{ and }m|y. $$

$P(0)$은 어떤 수든 0을 나눌 수 있으므로 참이다.

$P(n+1)$에서, 가능한 상태는 다음과 같다. ($n$번의 변화 이후 상태가 $(x,y)$이므로.)

$$(0,y), (x,0), (a,y), (x,b), (0,x+y), (x+y, 0), (x+y-b, b), (a, x+y-a)$$

$P(n)$이 참이라면 $m|a, m|b$ 뿐 아니라 $m|x, m|y$이므로, $a,b,x,y$의 조합으로 이루어진 위의 모든 상태도 $m$으로 나눌 수 있다. 그러므로 귀납 명제가 증명되었다!

$a=33, b=55$인 경우

$m|a, m|b$를 만족하는 $m$은 1과 11이 있다. 그러므로 이 물병들을 활용하여 4는 만들 수 없다.

최대공약수^{Greater Commer Divisor}

어떤 두 정수 $a,b$에 대한 최대공약수는 두 정수 $a$와 $b$ 모두를 나누어떨어지게 하는 수 $N$중, 가장 큰 수를 의미한다. 최대공약수는 $\text{gcd}(a,b)$와 같이 나타낸다.

만약 두 정수 $a,b$의 최대공약수가 1이면, 두 수는 서로소^{relatively prime}라고 한다.

선형 결합

$$\text{Theorem 2. Any linear combination of }a\text{ and }b, L=sa+tb \text{ with }(0\leq L \leq b) \text{can be reached } (a\leq b) $$

예를들어, $4 = 3s+5t$라고 할 때, $(0\leq L \leq b)$ 이므로 이 선형 결합을 만족시키는 $s$와 $t$가 존재한다.

또한, $s$의 부호를 바꾸고 싶을 때는 아래와 같은 공식을 활용할 수 있다.

$$\begin{align*}L &= sa + tb\\
&=(s+m\cdot b)a + (t-m\cdot a)b\\ \end{align*}
\\ \exists s', t', L=s'a+t'b, \text{ where }s'>0 $$

아래 알고리즘을 통해 이를 증명해보자.

물통 채우기 알고리즘

$L$리터 물통을 $a,b$리터 물통으로 채우는 알고리즘을 만들어보자. (이때, $0<L<b$라 가정하고)

• $a$ 물통을 채운다.
• $a$물통을 $b$물통에 붓는다.
• $b$물통이 꽉 차면 버린다.

이 과정을 반복하면 $L$리터의 물을 얻을 수 있다.

예를들어, $a=3, b=5, L=4$일 때,

(0,0)->(3,0)->(0,3)->(3,3)->(1,5)->(1,0)->(0,1)->(3,1)->(0,4)

위 과정을 통해 4리터의 물을 얻을 수 있다.

알고리즘 증명

$r$이 알고리즘 시행 이후 $b$ 물병에 남은 물이고, $u$는 $b$ 물병을 비운 횟수이다.

$$0\leq r \leq b, 0<L<b, L=s'a+t'b$$
$$r=s'a-ub\\
\begin{align*}r&=s'a+t'b-t'b-ub\\
&=L-t'b-ub\\
&=L-(t'+u)b\end{align*}$$

이 식에서 $(t'+u) \neq 0$는 있을 수 없다. 이 경우, $r<0$ 혹은 $r>b$로 불가능한 식이 되어버린다.

결국 $(t'+u)=0$으로, $r=L$이 성립된다.

유클리드의 알고리즘

어떤 정수 $b$를 정수 $a$로 나누면 $b=q\cdot a + r$로 나타낼 수 있다.

$q$는 quotient이라 하고, $r$은 remainder라 한다.

유클리드의 알고리즘은 아래와 같다.

$$\text{gcd}(a,b) = \text{gcd}(\text{rem}(b, a),a) = b-q\cdot a$$

즉,

$$\begin{align*}\text{gcd}(105, 224) &= \text{gcd}(14, 105)\\
&=\text{gcd}(7, 14)\\
&=\text{gcd}(0,7)\\
&=7 \end{align*}$$

증명

유클리드 알고리즘을 $n$회 재귀한 후의 상태를 $\text{gcd}(x,y)$라 하자. $x,y$는 모두 $a,b$의 선형 결합이다.

$P(0)$이면, $x=a, y=b$로 base case는 성립한다.

$P(n+1) = \text{gcd}(\text{rem}(y,x), x)$가 되는데, x는 당연히 a,b의 선형 결합이고, $\text{rem}(y,x)=y-q\cdot x$로 역시 $x,y$의 선형 결합이다.

그러므로 유클리드 알고리즘 $n$회 이후의 모든 $x,y$는 $a,b$의 선형 결합이다.

확장된 유클리드 알고리즘

$a,b$의 최대공약수는 $ax+by=\text{gcd}(a,b)$와 같이 $a,b$의 선형 결합으로 나타낼 수 있다. 확장된 유클리드 알고리즘은 최대공약수 뿐 아니라 이 선형 방정식도 알아낸다.

먼저 초깃값을 설정한다. $x_0 = 1, x_1 = 0, y_0 = 0, y_1 = 1, r_0 = a, r_1 = b$이다.

각 변수는 다음과 같이 갱신된다.

$$ q_i = \lfloor r_{i-1} / r_i \rfloor\\
r_i = r_{i-2}-r_{i-1}\cdot q_{i-1} = r_{i-2} \mod r_{i-1}\\
x_i = x_{i-2}-x_{i-1}\cdot q_{i-1}\\
y_i = y_{i-2}-y_{i-1}\cdot q_{i-1}$$

이제, $r$에 $a,b$ 값을 대입하고 반복하다 보면 $r$이 0이 된다. $r$이 0이 되기 이전 루프의 $x,y,r$이 $ax+by=r$에 들어간다.