정수론(1) 최대공약수의 새로운 정의

1. 시작하기 전에…

시작하기 전에, 기본 정수론 용어를 몇가지 정의하고 넘어가고자 한다.

$\mathbb{Z}$를 정수환이라고 정의한다. 즉 $a, b\in \mathbb{Z}$인 $a$와 $b$의 덧셈과 곱셈의 결과 $c$는 여전히 $\mathbb{Z}$의 원소라는 것이다. 즉 $\mathbb{Z}$가 정수환이라는 것은, 정수를 원소로 하며, 덧셈과 곱셈에 닫혀있다는 것이다. 그리고 이 글에서 특별한 표기가 없는 경우, 모든 수는 $\mathbb{Z}$의 원소로 간주하면 된다.
$a$가 $b$를 나눈다는 것, 즉 $a$가 $b$의 약수라는 것은, $a |b$라고 표현하기로 한다. 즉 $a |b$라는 것은, $\exists c \in \mathbb{Z} \ \ st. \ b=ac$이다.

2. 최대공약수의 새로운 정의

최대공약수라는 것은, 두 수의 공통된 약수 중, 가장 큰 것으로 정의한다. 즉 $d$가 $a$와 $b$의 최대공약수라고 한다면, $d=max\{f: f|a,f|b\}$ 를 만족한다는 것이다. 그리고 이를 $d=gcd(a,b)$, 특별한 표기가 없으면, $(a,b)$로 표기하고자 한다.
우리는 여기서 만족하지 않고, 최대공약수의 새로운 정의를 도출하고자 한다. 새로운 정의는 다음과 같다.
$d=min\{f: f=am+bn\}$
최대공약수인데, 정의에 min이 들어간다니, 조금 이상하게 느껴질 수 있다. 그래도 몇가지 예를 통해 받아들일 수는 있을 것이다.

$gcd(9, 75)$ => $3=75\times1-8\times9$
$gcd(7, 6)$ => $1=7\times1-6\times1$

위와 같이 최대공약수의 새로운 정의가 성립하는 것을 볼 수 있다.

3. 새로운 정의의 증명 과정

$d=min\{f: f=am+bn\}$
$d$가 $a$와 $b$의 최대공약수가 된다는 것을 증명하기 위해선, 다음 세가지 주장을 증명할 필요가 있다.

주장 1. $\mathbb{S}=\{am+bn\}$이 $\mathbb{Z}$의 부분군이다.
주장 2. 부분군 $\mathbb{S}\subseteq\mathbb{Z}$은 $\{0\}$이거나, $d\mathbb{Z}$꼴이다.
주장 3. $d=min\{f: f=am+bn\}=(a,b)$이다.

즉, 1과 2를 통해 $\mathbb{S}=\{am+bn\}$가 $a$와 $b$의 공약수의 집합임을 증명하고, 3을 통해 min을 취하는게 왜 올바른지 증명할 것이다.

4. 증명을 위해 필요한 도구들

Well Ordering Principle(최소원 법칙)
$\emptyset\ne\mathbb{A}\subseteq\mathbb{Z_{>k}}$이면, $\exists!a\in A \ st. \ \forall b \in A, \ b \geq a $
즉, 공집합이 아닌 정수환의 부분군은 최소 원소를 가지고 있다는 의미.
아르키메데스 원리
$a>0, \ a,b\in \mathbb{R}$일때, $\exists n\in\mathbb{Z} \ st. \ na>b$
실수(정수)를 계속 더하다 보면, 결국 더 커진다는 의미.
나눗셈 정리
$a\in\mathbb{Z}, \ b\in\mathbb{Z_{>0}}$일때, $\exists!q,r\in\mathbb{Z} \ st. 0\leq r \lt b \ and \ a=bq + r$

1과 2는, 그냥 사실로써 받아들여야 한다. 직관적으로도 받아들이기 어렵지 않다.
다만, 3, 나눗셈정리는, 1과 2를 통해 증명해볼 수 있다. 간단하게 내용을 설명하자면, 먼저 아르키메데스 원리를 통해 $\mathbb{S}=\{a-bq\}$가 공집합이 아님을 증명한다. 그다음, 공집합이 아니므로, 최소원의 법칙을 통해 최소원, $r$이 존재함을 알 수 있다. 마지막으로 귀류법을 통해 $0\leq r \lt b$임을 증명하면 끝난다.

5. 주장 1의 증명

어떤 집합이 $\mathbb{Z}$의 부분군임을 증명하려면, 덧셉에 대해 갇혀있고, 역원과 항등원이 존재함을 보이면 된다. 이는 어렵지 않으니 생략하고자 한다.

6. 주장 2의 증명

$\mathbb{S}$가 $\{0\}$인 경우는 자명하므로 생략.
그러므로, $\mathbb{S}\neq\{0\}$인 $\mathbb{S}$에 대해 $\mathbb{S}\cap \mathbb{Z_{>0}}$과 $\mathbb{S}\cap \mathbb{Z_{>0}}$에 대해 생각해보자.
$\mathbb{S}\cap \mathbb{Z_{>0}}=\emptyset$이면, $\mathbb{S}$가 부분군이므로, $\mathbb{S}\cap \mathbb{Z_{>0}}=\emptyset$이 되며 모순이 발생한다. 따라서 $\mathbb{S}$는 공집합이 아니다. 공집합이 아니므로, 최소원 $d$가 존재한다. 그러면 마지막으로 $\forall a\in \mathbb{S}, \ \exists q \ st. \ a=dq$를 증명하면 된다. 이는 $a=dq+r \ (0 \geq r \gt d)$일때 $r=0$임을 증명하면 충분하다. $r\neq0$이면, $d$가 최소원임에 모순이 발생하므로, $a=dq$이다. 끝.

7. 주장 3의 증명

주장 3을 증명하기 전에, 한가지 먼저 증명해볼 것이 있다. $d|a, \ d|b \to d|am+bn$이 성립한다는 것이다. 이는 $a=dx, \ b=dy$라 두면, $d|d(xm+yn)$임을 통해 쉽게 알 수 있다.
주장 3의 핵심 아이디어는, 위에서 증명한 나눗셈 정리를 사용하는 것이다. $a=bq + r \ (0\leq r \lt b)$일때, $(a,b)=(b,r)$를 증명해 볼 것이다. $e=(a,b)$ $d=(b,r)$이라 할 때, $d=e$를 증명하려면, $d|e$, $e|d$임을 증명하면 충분하다. 즉, $d|r$, $e|a$를 증명하면 되는 것이다. 우선, $d|a$, $d|b$이므로, $d|am+bn$이 성립한다. $m=1$, $n=-q$를 대입하면, $d|a-bq=r$이다. $e|d$도 동일하게 증명하면 된다.
따라서, 우리는 $a=bq + r \ (0\leq r \lt b)$일때, $(a,b)=(b,r)$임을 알게 되었다. 그렇다면, 이를 활용해서 증명을 끝내보자.
$a=bq+r$
$b=rq_1+r_1$
$r=r_1q_2+r_2$
…
…
…
$r_{n-1}=r_nq_{n+1}+r_{n+1}$, $r_{n+1}=0$
위와 같이 나눗셈 정리를 활용하면 나머지가 $0$이 될 때까지 식을 전개할 수 있다. 한편,
$(a,b)=(b,r)=(r,r_1) \ … \ = (r_n,r_{n+1})=(r_n,0)=r_n$이 됨을 알 수 있다. 따라서, 주장 3을 증명 끝냈고, 왜 min이 필요한지 충분히 설명이 되었다고 생각한다.

확장 1. 유클리드 알고리즘

최대 공약수의 새로운 정의의 장점은, 공식을 알고리즘화하기 쉽다는 점이다.

  
def euclid(a, b):
    if a%b == 0:
        return b
    else:
        return euclid(b, a%b)
        

재귀함수를 사용하면 엄청 간단하게 구현할 수 있다.
간단함 뿐만 아니라, 소인수분해를 통해 최대공약수를 계산하는 것보다 훨씬 빠르다. 유클리드 알고리즘의 시간복잡도는 $\mathbb{O}(log{min(a,b)})$이다. 이는 여기에서 확인해볼 수 있다. 한편, 소인수분해 알고리즘의 시간복잡도는 일반적으로 $\mathbb{O}(\sqrt{n})$이라고 한다…

확장 2. 선형 방정식

한편, 유클리드 알고리즘을 변형하여, $am+bn=(a,b)$의 $m$, $n$의 해까지 구해주는 알고리즘이 존재한다. 이를 확장된 유클리드 알고리즘이라고 부르며, 다음과 같이 구현할 수 있다.

  
def exeuclid(a, b, sp, spp, tp, tpp):
    if b==0:
        return f'gcd={a}, m={tpp}, n={spp}'
    s = spp - sp*int(a/b)
    t = tpp - tp*int(a/b)
    return exeuclid(b, a%b, s, sp, t, tp)


print(exeuclid(a, b, 1, 0, 0, 1))

이러한 알고리즘을 활용하거나, 직접 유클리드 알고리즘을 역으로 거슬러 올라가면서 $m$과 $n$의 값을 구할 수 있다.
한편, $am+bn=(a,b)$의 해는 유일할까? 그렇지 않다. 일반 해는 다음과 같다. $(x_1 + k\times \frac{b}{(a,b)}, y_1 - k\times \frac{a}{(a,b)})$
($x_1$과 $y_1$은 $am+bn=(a,b)$의 해) 또한, 이를 통해 우변이 $(a, b)$의 배수가 아닌 경우, 해가 존재하지 않음을 도출해볼 수 있을 것이다.