1차 선형 디오판토스 방정식(Linear first-order Diophantine equation)

디오판토스는 고대 그리스의 수학자로, 이집트 알렉산드리아 출신이며 정수론과 방정식을 연구하였다고 알려져 있습니다. 그의 이름을 따 만들어진 디오판토스 방정식은 정수론을 공부하면 꼭 한 번쯤은 들어봤을 것입니다. 디오판토스 방정식은 정수해만을 다루며, 해법이 아주 어렵지 않아 사실 중고등학교 수학 정도만으로도 해를 찾는 것이 가능합니다. 그리고 여러 매체에서 그것의 응용을 재미난 수수께끼로 둔갑시켜 사용되고는 합니다.

 

[그림 1] 툼레이더4 마지막 계시록(Last Revelation)의 마지막 챕터 호루스 신전(Temple of Horus). 여기서 디오판토스 방정식을 제대로 풀어내지 못하면 괴물이 등장해서 라라를 위협한다. 물론 마지막 챕터라 주인장같은 고수는 탄약을 넉넉히 쟁여두기 때문에 괴물은 위협이 되지 못하며 수학 공부를 해왔기 때문에 바로 해결했다. 재미삼아 한 번 틀려보고 괴물을 상대해봤다.

 

라라 크로프트를 주인공으로 하는 <툼레이더(Tomb raider)> 시리즈는 제가 매우 좋아하는 게임 중 하나입니다. 제가 어렸을 시절 툼레이더 클래식(1,2,3,4,5(연대기)) 를 즐겨 했었던 기억이 있는데, 당시 너무 어려워서 끝까지 깨지 못했습니다. 툼레이더 시리즈는 고도의 컨트롤 피지컬과 경로 기억성, 귀류법적 사고(모순막기) 등을 요하는 게임이라 청소년이 클리어하기는 사실 생각보다 굉장히 어려운 게임이기 때문입니다.

 

그런데 수능이 끝나고 하나씩 깨봤었던 기억이 남는데, 그 중 두번째로 재밌었던 시리즈가 4편인 마지막 계시록(Last Revelation)입니다. 이 시리즈는 제가 얼마 전인 대학교 3학년 무렵에 클리어했는데, 가장 마지막 챕터인 '호루스 신전(Temple of Horus)'에서 머리를 써서 수수께끼를 풀어야 합니다.^[각주:1] 그런데 이것의 원리가 바로 디오판토스 방정식입니다.

 

[그림 1,2] 왼쪽 사진을 보면 벽에 4개의 줄무늬가 그려져 있다. 이는 물 4L를 저울에 정확히 맞추기를 요하는 수수께끼이다. 오른쪽 사진에는 물주머니 2개를 가지고 있음을 보여주는 인벤토리 창이다. 보이는 것과 같이 정확히 4L를 맞추어야 한다.

 

주인공(나)이 할 수 있는 것은 다음과 같습니다.

 

1) 5L 물주머니(Large waterskin)과 3L 물주머니(Small Waterskin)를 가지고 있다.
2) 항아리 저울에 정확히 4L의 물을 넣어야 한다.
3) 물주머니에 자유롭게 물을 넣을 수 있고, 물을 버릴 수도 있다. 그리고 두 물주머니에 있는 물을 서로에게 옮겨 담을 수 있다.

Q1) 이때 어떤 방법을 통해서 정확히 4L의 물을 만들어낼 수 있는가?
Q2) 이때 어떤 방법을 통해서 정확히 1L의 물을 만들어낼 수 있는가?

 

 

이는 사실 간단한 정수론의 수학문제입니다. 오늘은 이것이 변수 2개인 1차 디오판토스 방정식에 해당함을 설명하고, 해를 찾는 법에 대해 다루겠습니다.

---

1. 1차 디오판토스 방정식

 

1) 도입

 

정의($N.T$) 1-8) 1차 디오판토스 방정식
변수가 2개인 1차 디오판토스 방정식은
$$ax+by=c$$ 의 형태이다. 여기서 변수는 $x,y\in\mathbb{Z}$ 로 정수해만을 고려하고, $a,b\neq 0$ 이다. 이 방정식의 해는 해가 없거나 무수히 많다.

 

디오판토스 방정식은 중학교 2학년 1학기 수학에서 잠깐 등장합니다. 물론 이런 이름을 쓰지는 않고, 일부 정수해만을 노가다로 대입해서 찾습니다. 하지만 우리가 하려고 하는 작업은 모든 정수해를 표현하는 것입니다.

 

또한 앞서 소개했던 툼레이더에서 등장하는 수수께끼는 다음과 같이 1차 디오판토스 방정식으로 바꾸어 말할 수 있습니다.

 

$$5x+3y=4$$

이를 만족하는 $x,y\in\mathbb{Z}$ 를 찾는 것이 목표입니다. 여기서 $x,y$ 는 각각 5L, 3L 물주머니의 용기를 채우거나 비우는 횟수에 의미합니다.^[각주:2] 

 

해가 존재한다고 가정할 때, 가장 기본적인 방법은 물론 몇 번 때려 맞추어 넣는 것입니다. $5,3,4$ 는 비교적 작은 숫자에 해당하고, $x,y$ 중 하나가 $0$ 이라면 $\gcd (5,4)=\gcd (3,4)=1$ 이므로 해를 찾을 수 없을 것입니다. 그러니 $x,y\neq 0$ 일 것이며, 또 $x=y=1$ 인 경우 $5+3=8>4$ 이니 둘 중 하나는 음수라는 점을 알 수 있습니다. 이 과정에서 노가다를 통해 해를 구해보면 $(x,y)=(2,-2)$^[각주:3] 와 $(x,y)=(5,-7)$ 이라는 해를 찾을 수 있습니다.

 

[그림 4] 결국 이것은 일차함수와 정수 격자점의 교점을 찾는 일이다.

 

또한, 기하학적 방법을 사용해 보자면 $5x+3y=4$ 는 결국 일차함수, 직선에 해당할 뿐입니다. 이 직선을 그리고 나서 정수 격자점을 그려서 그들의 교점에 해당하는 순서쌍을 찾으면 직선은 무한히 길기 때문에 그러한 순서쌍도 무한히 많이 발생함을 알 수 있습니다. 즉 해가 무수히 많다는 것이죠.

 

 

2) 특수해와 일반해의 연결

 

위에서 우리가 찾은 $(x,y)=(2,-2)$ 를 통해, 미분방정식에서 해를 찾았던 것처럼, 일반해 꼴을 만들어낼 수 있는 방법이 있습니다. 정수론을 배울 때 선형대수학을 보통 같이 배우기는 하지만, 이러한 특수해와 일반해의 관계를 일반적으로 선형대수학에서 밝히는 방법이 있기는 합니다.

 

 

정리($N.T$) 1.10) 1차 선형 디오판토스 방정식의 일반해와 특수해 관계
1차 선형 디오판토스 방정식 $ax+by=c$ 의 한 해를 $(u,k)$ 라 하자. 그러면 임의의 $t\in\mathbb{Z}$ 에 대하여 $x=u+bt$, $y=k-at$ 도 방정식의 해가 된다.

증명) $x=u+bt$, $y=k-at$ 를 방정식에 대입하면

$$\begin{align*}
ax+by= c&=a(u+bt)+b(k-at)
\\\\&=(au+kb)+abt-bat
\\\\&=au+kb
\end{align*}$$
가정에 의해 $au+kb=c$ 가 성립한다. 따라서 $x=u+bt$ 와 $y=k-at$ 도 방정식의 해이다. $_\blacksquare$

 

 

3) 언제 해를 찾을 수 있는가?

 

1차 선형 디오판토스 방정식의 정수해가 언제나 존재한다고 볼 수는 없습니다. 다음의 예를 봅시다.

 

$$6x+9y=5$$

 

이것은 아무리 노가다를 해도 정수해를 찾을 수 없습니다. 그렇다면 정수해가 존재할 필요충분조건이 무엇인지를 떠올리는 것이 자연스럽습니다. 다음 정리가 그것을 말해줍니다.

 

 

정리($N.T$) 1.11) 1차 선형 디오판토스 방정식의 해가 존재할 조건
1차 선형 디오판토스 방정식 $ax+by=c$ 의 정수해 $(x,y)$ 가 존재할 필요충분조건은 $g\mid c$ 인 것이다. 이때 $g:=\gcd (a,b)$ 에 해당한다.

증명) $\Longrightarrow$ : 정수 $(x,y)$ 가 존재하여 $ax+by=c$ 가 성립한다고 하자. $\gcd(a,b)=g$ 이므로 $g\mid a $ 이고 $g\mid b$ 이다. 그러면 $a=mg$, $b=ng$ 를 만족하는 $m,n\in\mathbb{Z}$ 가 존재한다. 이를 대입하면 $mgx+ngb=g(mx+nb)=c$ 가 성립한다. 이때 $m,n,x,b\in\mathbb{Z}$ 이고 정수는 덧셈과 뺄셈에 대해 닫혀있기 때문에 $mx+nb\in\mathbb{Z}$ 이다. 따라서 $g\mid c$ 이다.

$\Longleftarrow$ : $g\mid c$ 이라 가정하면 $d\in\mathbb{Z}$ 에 대하여 $c=gd$ 이다. 베주 항등식에 의하면 $a,b\in \mathbb{Z}-\{ 0\}$ 일 때 $g=\gcd(a,b)$ 이면 $g=ax+by$ 가 성립하는 $x,y$ 가 존재한다. 이러한 $(x,y)=(u,k)$ 라 하자. 그러면 $au+kb=g$ 가 된다. 이 식의 양변에 $d$ 를 곱하면 

$$d(au+kb)= dg= c$$
가 된다. 그러면 $(au,kb)=(x,y)$ 라 했을 때 이것이 $ax+by=c$ 의 정수해에 해당함을 알 수 있다. $_\blacksquare$

 

 

---

예제 1) 다음의 디오판토스 방정식이 해를 갖는지 아닌지 위의 정리를 이용하여 판별하여라.

 

1) $6x+9y=15$

 

2) $8x+12y=20$

 

3) $7x+14y=5$

 

4) $5x+10y=3$

 

 

Sol) 1) $\gcd(6,9)=3\mid 15$ 이므로 해가 존재한다.

 

2) $\gcd(8,12)=4\mid 20$ 이므로 해가 존재한다.

 

3) $\gcd(7,14)\not\mid 5$ 이므로 해가 존재하지 않는다.

 

4) $\gcd(5,10)=5\not\mid 3$ 이므로 해가 존재하지 않는다. $_\blacksquare$

---

정리($N.T$) 1.12)
1차 선형 디오판토스 방정식 $ax+by=c$ 의 한 특수해를 $(x,y)=(u,k)$ 이라 하고 $\gcd(a,b)=g\mid c$ 라 하자. 이 방정식의 다른 모든 해를 포함하는 일반해는, $t\in\mathbb{Z}$ 에 대하여
$$x=u+\left( \frac{b}{g} \right)t\;\;,\;\;y=k-\left( \frac{a}{g} \right)t$$ 에 해당한다.

따름정리($N.T$) 1.12.1)
1차 선형 디오판토스 방정식 $ax+by=c$ 의 한 특수해를 $(x,y)=(u,k)$ 라 하고 $a,b$ 가 서로소, 즉 $\gcd(a,b)=1$ 이라고 하자. 그러면 이 방정식의 다른 모든 해를 포함하는 일반해는, $t\in\mathbb{Z}$ 에 대하여 $x=u+bt\;\;,\;\;y=k-at$ 이다.

증명) $(x',y')$ 가 방정식의 임의의 해라고 하자. 그러면 $ax'+by'=au+bk=c$ 가 성립한다. 첫번째 등식으로부터
$a(u-x')=b(k-y')$ 이다. 양변을 $\gcd(a,b)=g$ 로 나누어보면

$$\displaystyle\frac{a}{g}(u-x')=\displaystyle\frac{b}{g}(k-y')\;\;\;\;\;\cdots \;\;\;(1)$$
이므로, $\displaystyle\frac{a}{g}\mid \left\{ \displaystyle \frac{b}{g}(k-y') \right\}$ 가 성립한다. 그러면 정리($N.T$) 1.3) 에 의하여 $\gcd\left( \displaystyle \frac{a}{g},\displaystyle \frac{b}{g} \right)=1$ 이므로 유클리드 보조정리에 의하여 $\displaystyle \frac{a}{g}\mid (k-y')$ 임을 알 수 있다. 고로 $t\in\mathbb{Z}$ 에 대하여 $\displaystyle\frac{a}{g}t=k-y'$ 이므로 $y'=k-\displaystyle\frac{a}{g}t$ 가 성립한다.

이제 이를 $(1)$ 에 대입해보자. 그러면

$$\displaystyle\frac{a}{g}(u-x')=\displaystyle\frac{b}{g}\left( \displaystyle \frac{a}{g}t \right)$$
가 되고, 양변을 $\displaystyle\frac{a}{g}\neq 0$ 으로 나누면 $x'-u=\displaystyle\frac{b}{g}t$ 가 된다. 따라서 $x'=u+\displaystyle\frac{b}{g}t$ 를 얻는다. $_\blacksquare$


따름정리의 증명) $g=1$ 일 때에 해당한다. $_\blacksquare$

 

 

 

---

2. 물주머니 문제의 해결은?

 

물주머니 문제를 마무리해봅시다. $5x+3y=4$ 는 $\gcd(5,3)=1\mid 4$ 이므로 해가 존재합니다. 해로 가장 간단한 것은 $(x,y)=(2,-2)$ 에 해당합니다. $x,y>0$ 인 경우 물주머니를 채운다는 뜻이고, $x,y <0$ 의 의미는 물주머니를 비운다(물을 버린다)는 의미에 해당합니다. 일단 두 숫자를 분석하기 이전에, 단순히 문장으로 해결 과정을 적어 보면 다음과 같습니다. 여기서 $R=(\mathrm{Large}, \mathrm{small})$ 은 그 단계가 끝날 때 각각 두 주머니에 남아 있는 물의 양을 뜻합니다.

 

1) $5\mathrm{L}$ 주머니를 가득 채웁니다. $R=(5,0)$
2) $5\mathrm{L}$ 주머니의 물을 $3\mathrm{L}$ 주머니로 옮깁니다 (이때 $5\mathrm{L}$ 주머니에는 $2\mathrm{L}$ 가 남습니다). $R=(2,3)$
3) $3\mathrm{L}$ 주머니를 비웁니다. $R=(2,0)$
4) $5\mathrm{L}$ 주머니에 남은 $2\mathrm{L}$ 를 $3\mathrm{L}$ 주머니로 옮깁니다. $R=(0,2)$
5) $5\mathrm{L}$주머니를 다시 가득 채웁니다. $R=(5,2)$
6) $5\mathrm{L}$ 주머니의 물을 $3\mathrm{L}$ 주머니에 있는 $2\mathrm{L}$ 위로 채워넣습니다 ($3\mathrm{L}$ 주머니가 가득 찰 때까지 $1\mathrm{L}$ 옮기면 $5\mathrm{L}$ 주머니에는 정확히 $4\mathrm{L}$ 가 남습니다). $R=(4,3)$

 

 

이때 $5$ 에 붙어있는 $x=2 >0$ 이므로 이는 $5\mathrm{L}$ 물주머니에 물을 총 2번 채워야 함을 뜻하고, $y=-2 <0$ 이므로 $3\mathrm{L}$ 의 물주머니에 물을 총 2번 버려야 함을 뜻합니다. 앞의 주석에서 말했듯이 중간에 서로의 물주머니에 물을 옮겨 담는 행위들은 디오판토스 방정식에 반영된 것은 아닙니다.

 

그런데 위 과정을 보면 납득이 잘 되지 않는 부분이 존재할 수 있습니다. 분명 $5\mathrm{L}$ 의 물주머니에는 1)번과 5)번에서 총 2번 물을 채우는데, $3\mathrm{L}$ 의 물주머니에서 물을 버리는 과정은 3)에 한 번만 존재하는 것처럼 보이기 때문입니다. 모순처럼 보이는 이 관계를 어떻게 설명할 수 있을까요?

 

이 비밀의 실타리를 풀어내는 핵심은 처음 물주머니가 모두 비어있기 때문에 처음에 $R=(0,0)$ 으로 시작한다는 점이고, 따라서 끝날 때도 $4\mathrm{L}$ 만 남겨서 $R=(4,0)$ 으로 끝나야 한다는 것입니다. 실제 게임에서 굳이 $3\mathrm{L}$ 의 작은 물주머니 물을 바닥에 버려야만 하는 것은 아니지만, 수학적으로 볼 때 $R=(4,0)$ 을 만들어야 하므로 마지막 과정 6) 뒤에서 작은 물주머니의 물을 비워야 하기 때문에, 작은 물주머니의 물도 총 2번 버려야 정확히 $4\mathrm{L}$ 의 물만 남는다는 사실을 알 수 있습니다.

 

[그림 4,5] 피라미드에서 결국 탈출하지 못하는 라라. 그것을 지켜보는 본크로이. 본크로이는 부적(Amulet) 으로 인해 세트(Seth)에 빙의되었었으나 라라가 세트를 가두면서 다시 멀쩡해진다. 라라는 이 장면에서 '더 이상 세트는 없어, 이미 세트는 죽었어(No more Seth)'라는 말을 남기고 피라미드에 갇혀 실종된다.

 

게임에서는 실제로 과제가 연달아 세 번 나옵니다. 첫 문제는 $2\mathrm{L}$, 두번째 문제는 $4\mathrm{L}$, 세번째 문제는 $1\mathrm{L}$ 를 만들어야 합니다. 그러면 호루스(Horus) 신을 부활시킬 수 있습니다. 그러나 부활하자마자 허무하게 세트(Seth)가 그를 다시 죽여버리기 때문에.. 세트를 피해서 요리저리 동굴을 빠져나가는 것으로 게임이 종료됩니다. 그러나 피라미드에 갇힌 라라는 행방불명되고, 마지막 탈출 과정에서 그녀의 스승 본 크로이(Von croy)는 그녀를 구하지 않습니다. 속편 연대기(Chronicles)에서 라라의 동료들이 그녀와의 추억을 회상함으로서 게임이 시작되게 됩니다.

 

 

 

 

 

[참고문헌]

Introduction to Number Theory - William W. Adams, Larry Joel Goldstein

 

 

 

 

 

1. 이 수수께끼를 풀지 못하면 괴물이 나와 주인공을 괴롭히고, 그 괴물을 죽이고 재도전할 수 있습니다. 그리고 이를 풀어야만 보스를 만날 수 있습니다. [본문으로]
2. 따라서 '어떤 순서'로 용기들을 채우고 비우는지의 의미까지는 미지수 $x,y$ 가 내포하고 있지 않습니다. 이러한 순서에 관한 감각은 스스로 깨우쳐야(?) 합니다. [본문으로]
3. 이것이 실제 물 문제에 대한 가장 빠른 해법이라고 볼 수 있습니다. 여기서 변수 $x,y$ 의 의미에 대해 보충 설명이 필요한데, 뒤에서 마무리하도록 하겠습니다. [본문으로]