합동방정식(congruence equation)

이번 주제는 정수론에서 합동에 대한 개념을 바탕으로 합동방정식의 해를 찾는 일입니다. 이 작업은 일차적으로 정수론에서  1차 선형 디오판토스 방정식에 대해 알고 있어야만 이해할 수 있습니다.

 

하지만 합동방정식을 조금 더 풍부하게 이해하기 위해서는 선형대수학의 방정식 논리를 알고 있는 것이 좋기는 합니다. 일반적인 연립방정식과 다른 점은 합동방정식이 미분방정식에서처럼 해의 개수가 단 하나로 떨어지지 않는다는 점입니다. 이는 동치류가 품고 있는 무수히 많은 원소들이 모두 해가 될 수 있다는 사실에 기반하고 있습니다. 또한 해의 꼴을 보면, 디오판토스 방정식처럼 합동방정식은 선형대수학에서 연립방정식의 해의 논리와 유사한 점이 많습니다. 방정식은 근본적으로 대수적인 관점이 녹아 들어있기 때문입니다. 

 

 

만일 선형대수학이나 미분방정식에서 그러한 경험이 전무하다면, 정수론에서의 합동 개념만을 정확히 장착하는 것이 요구됩니다. 그렇기만 하다면 문제가 없을 것입니다.

---

1. 선형합동식

 

1) 정의

 

정의($N.T$) 3-6) 선형합동식
$ax\equiv b\;(\text{mod}\; n)$ 의 형태를 갖는 선형방정식을 '선형합동식(linear congruence)'라 한다. 이 방정식의 해 $x$ 는 정수이며, 일반적으로 단 하나의 정수가 아니라 정수들의 집합(동치류)이다.

 

방정식을 보면 정수 $a,b,n$ 이 주어졌을 때 $x$ 의 값을 찾는 것이 목표라 할 수 있습니다. 식을 간단하게 정리하면 $ax=kn+b\;\;(k\in\mathbb{Z})$ 가 되어야 함을 알 수 있고, 이때 $k$ 는 임의의 정수가 다 들어갈 수 있으니 그에 따라 $x$ 의 값도 무수히 많을 것임을 예상할 수 있습니다.

 

방정식의 해가 무수히 많은 경우를 우리는 예전부터 종종 봐았습니다. 예컨대 선형대수학에서 연립일차방정식^[각주:1] 을 풀 때 행렬(또는 일차변환)이 가역이면 단 하나의 해가 발생하지만, 가역이 아닐 때는 해가 없을 수도 있고 무수히 많을 수도 있습니다. 또한 미분방정식을 풀 때 두 해를 선형결합으로 쓰는 행위는 곧 해가 무수히 많기 때문에 그것들을 임의의 기저로 삼아 표현하는 방법이 존재함을 알고 있을 것입니다.

 

정수론의 합동방정식에서 해가 무수히 많다는 개념은 미분방정식에서의 그것과 유사합니다. 예를 들어 $5x\equiv 3 \;(\text{mod}\; 2)$ 인 경우를 생각해봅시다. $5x=2k+3$ 으로 간소화할 수 있습니다. $k=1,2,3,4$ 만을 생각해보면, 

 

$$\begin{align*}

5x=2k+3\;\;(k=1,2,3,4,5,6) \;\;&\Longrightarrow \;\; 5x=5,7,9,11,13,15
\\\\&\Longrightarrow x=1,\frac{7}{5},\frac{9}{5},\frac{11}{5},\frac{13}{5},3

\end{align*}$$

 

와 같이 특정 $k$ 값에 대해서만 정수해가 발생함을 알 수 있습니다. 여기서는 $k=1,6$ 일 때가 $x=1,3$ 으로 정수해가 발생하고 이 사이의 $k=2,3,4,5$ 일 때는 정수해가 없음을 알 수 있습니다. 그리고 이를 반복하면 모든 해는 $x=\cdots -7, -2, 3, 8, 13, 18\cdots$ 으로 무수히 많으면서 동시에 $5$ 만큼의 간격을 두고 있다는 것을 알 수 있습니다. 이를 종합하면,

 

$$\cdots, -7\equiv -2\equiv 3\equiv 8\equiv 13\equiv 18\equiv \cdots $$

 

가 되어, 최종적으로 해는 $x\equiv 3 \;(\text{mod}\; 5)$ 와 같이 간결하게 쓰게 됩니다.

---

예제 1) 여태까지 한 내용을 바탕으로 하여 $4x\equiv 3 \;(\text{mod}\; 2)$ 의 해가 존재하는지 찾아보라.

 

 

Sol) $k\in\mathbb{Z}$ 에 대하여  $4x=2k+3$ 을 만족해야 하므로 $4x=\cdots, 5, 7, 9, 13, 15,\cdots $ 으로 홀수가 등장하고 있다. 그러면 임의의 홀수도 $4$ 를 약수로 가지지 않기 때문에, 즉 임의의 홀수는 $4$ 의 배수가 아니기 때문에 정수해 $x$ 는 존재하지 않는다. $_\blacksquare$

---

이를 통해 모든 선형합동식이 해를 가지지는 않는다는 것을 알 수 있습니다. 또다른 예시로 $2x\equiv 1 \;(\text{mod}\; 6)$ 의 경우 또한, $2x=6k+1\;\;(k\in\mathbb{Z})$ 로부터 $2x=\cdots, 7, 9, 11, 13,\cdots$ 가 되어버리니 해가 존재하지 않습니다.

 

해가 존재하지 않게 되는 이유를 먼저 탐구해봅시다. 근본적인 까닭은 $ax=kn+b$ 으로 정리하게 되었을 때 $kn+b$ 가 $a$ 의 배수가 아니었기 때문입니다. 즉 $a\not\mid (kn+b)$ 가 되었기 때문이죠. 곧 $x=\displaystyle \frac{nk+b}{a}$ 에서 분모는 분자의 약수가 되어야 합니다. 이렇게 보면 꽤나 복잡한데, 사실 $ax=kn+b$ 는 1차 선형 디오판토스 방정식에 해당합니다. 따라서 그 논리를 사용하면 합동식의 해가 언제 존재하는지 다음과 같이 결과를 이끌어낼 수 있게 됩니다.

 

 

정리($N.T$) 3.11) 합동방정식의 해가 존재할 조건
선형합동식 $ax\equiv b\;(\text{mod}\; n)$ 의 해 $x\in\mathbb{Z}$ 가 존재할 필요충분조건은 $\gcd(a,n):=g\mid b$ 인 것이다. 이때 해는 동치류로 표현되며, (디오판토스 방정식에서처럼) 무수히 많다.

증명) 선형합동식 $ax\equiv b \;(\text{mod}\; n)$ 는 $ax+(-kn)=b$ 와 동치이다. 이것은 1차 선형 디오판토스 방정식이고, 여기서 $a,n$ 을 변수라고 생각해서 $\gcd(a,n)=g$ 라고 하면 정리($N.T$) 1.11) 에 의해 이것의 해가 존재할 필요충분조건은 $\gcd(a,n)=g\mid b$ 인 것이다. $_\blacksquare$

 

 

정리($N.T$) 3.12) 합동방정식의 합동이 아닌 해의 개수
선형합동식 $ax\equiv b\;(\text{mod}\; n)$ 을 생각하자. $\gcd(a,n)=g\mid b$ 라면, 법 $n$ 에 대하여 정확히 $g$ 개의 합동이 아닌 해가 존재한다. 그리고 그 해(동치류)는 다음과 같이 표현된다.
$$x=x_0+\left( \displaystyle \frac{n}{g} \right)t\;\;\;\;\;(t=0,1,\cdots , g-1)$$ 즉, 해의 개수는 정수로서 무한히 많으나, 동치류 표현으로서 정확히 $g$ 개 존재한다는 뜻이다. 이를 반영하여, 앞으로 '해의 개수'라는 것은 동치류인 해의 개수임을 뜻하는 것으로 표현한다.

따름정리($N.T$) 3.12.1) 합동방정식이 유일한 해를 가질 조건
선형합동식 $ax\equiv b \;(\text{mod}\; n)$ 을 생각하자. $\gcd(a,n)=1$, 즉 $a$ 와 $n$ 이 서로소이면, 이 방정식은 유일한 해(동치류로서 1개)를 갖는다.

증명) $ax\equiv b \;(\text{mod}\; n)$ 이고 $g=\gcd (a,n)$ 이면서 $g\mid b$ 라고 하자. 그러면 $ax+(-k)n=b$ 의 형태가 된다. (이는 1차 선형 디오판토스 방정식과 형태가 비슷하고, $x, -k$ 가 미지수 역할, $a,n$ 이 상수 역할이다. 그러면 그 해는 $ x=x_0+\left( \displaystyle\frac{n}{g} \right) t\;\;(t\in\mathbb{Z})$ 가 된다. 그런데 여기서 $g=\gcd(a,n)$ 이므로 $n=gm\;\;(m\in\mathbb{Z})$ 와 같이 쓸 수가 있으며, 따라서 $x=x_0+mt\;\;(t\in\mathbb{Z})$ 가 되는 셈이다. 그러면 $x\equiv x_0 \;(\text{mod}\; m)$ 이다.

이것은 선형합동식 $ax\equiv b \;(\text{mod}\; n)$ 의 모든 해를 압축적으로 표현한 일반적인 식이다. 그런데 여기서 목표는 법 $n$ 에 대하여 정확히 $g$ 개의 합동이 아닌 해를 찾는 것이다. 그러니 여기서 특수해 $x_0$ 를 시작으로 그 다음 해를 나열해서 적어보면 

$$ x=x_0\;, \; x=x_0+\left( \displaystyle\frac{n}{g} \right) \;,\; x=x_0+2\left( \displaystyle\frac{n}{g} \right)
+ \cdots + x=x_0+(g-1)\left( \displaystyle\frac{n}{g} \right)$$
가 된다. 여기서 $t=g$ 를 대입하면 다시 $x=x_0+n$ 이 되어서 $x=x_0$ 와 겉형태는 달라도 $x\equiv x_0 \;(\text{mod}\; n) $ 에 포함되는 두 해이다. 따라서, 동치류 형태로 법 $n$ 에 대하여 정확히 합동이 아닌 해가 몇 가지인지는 $t=0,1,\cdots, g-1$ 을 대입했을 때 나타나는 정확히 $g$ 개의 해이다. $_\blacksquare$


따름정리의 증명) $g=1$ 이므로 동치류 해의 개수는 오직 한 개이다. $_\blacksquare$

 

 

---

2. 역원

 

이제 선형합동식을 만났을 때, 해가 존재하는지의 여부를 포함하여 그 해의 형태가 어떤 꼴을 가지고 있는지를 모두 설명했습니다. 

 

수학은 항상 일반적인 상황과 그 안에 포함된 특수적인 상황을 구분하는 일이 중요합니다. 그래서 선형합동식은 결국 해가 존재하는지의 여부를 따진 뒤 그 해가 유일하게 존재하는지를 찾아야 하는 경우가 흔합니다. 이러한 판단은 정수론에서 뿐만 아니라, 어차피 대수학에 갔을 때 이 개념을 주구장창 써재껴야 하기 때문에 중요하게 여겨집니다.

 

그런데 해가 유일하게 존재하는 상황은 역원의 존재성 여부에 크게 달려있습니다. 선형대수학에서도 $A\mathbf{x}=\mathbf{b}$ 와 같은 행렬방정식에 대해 $A$ 가 가역이라 $A^{-1}$ 가 존재할 때 유일한 해 $\mathbf{x}=A^{-1}\mathbf{b}$ 를 가졌었습니다. 따라서, 역원의 존재성은 곧 방정식의 해가 유일함을 보장한다는 사실과 필요충분조건임을 알 수 있습니다. 선형합동식에서도 이것은 그대로 적용됩니다. 사실 이들의 근원은 대수학에서 역원의 존재성에 그 바탕을 두고 있기 때문입니다.

 

그리고 이는 대수학에 가서 줄기차게 사용하는 $\mathbb{Z}_n^*$ 을 정의할 수 있게 됩니다.

 

 

정의($N.T$) 3-7)
법 $n\in\mathbb{N}$ 이 주어졌을 때, 다음의 집합을 '법 $n$ 에 대한 곱셈 정수 집합(Sets of multiplicative integers modulo $n$)' 이라고 정의한다. 이는 곧 $\mathbb{Z}_n$ 의 원소 중 곱셈 연산에 대해 역원을 가지는 원소들만을 추려 뽑아 만든 집합으로, $\overline{a}x\equiv 1 \;(\text{mod}\; n)$ 을 만족하는  동치류 $\overline{a}$ 들로 구성된 집합이다. 이를 조건제시법으로 나타내면 다음과 같다.
$$\mathbb{Z}_n^*:=\left\{  \overline{a}\in\mathbb{Z}_n\mid \gcd(a,n)=1
  \right\}\subseteq \mathbb{Z}_n$$

 

이제 역원에 대한 소개를 해봅시다.

 

 

정의($N.T$) 3-8) 합동에서 곱셈에 대한 역원
$ax\equiv 1\;(\text{mod}\; n)$ 에서, $\gcd(a,n)=1$ 이라 합동식이 유일한 (동치류) 해 $x$ 를 가질 때, 이 해를 '법 $n$ 에 대하여 $a$ 의 곱셈에 대한 역원(multiplicative inverse)' 라 하고 $a^{-1}\;(\text{mod}\; n)$ 로 나타낸다.

따름정리($N.T$) 3.12.2)
선형합동식 $ax\equiv b\;(\text{mod}\; n)$ 에 대하여 $a$ 의 역원 $a^{-1}\;(\text{mod}\; n)$ 가 존재할 필요충분조건은 $\gcd(a,n)=1$ 인 것이다.

증명) $\Longrightarrow$ : $a$ 의 역원이 존재하면 $a^{-1}a \equiv 1 \;(\text{mod}\; n)$ 이 성립한다. 그러면 어떤 $-k\in\mathbb{Z}$ 가 존재하여 $aa^{-1}+(-k)n=1$ 이 성립한다. 고로 베주항등식에 의해 $\gcd(a,n)=1$ 가 성립한다.

$\Longleftrightarrow$ : $\gcd(a,n)=1$ 이면 베주항등식에 의해 $ax+bn=1$ 이 성립하는 $x,b\in\mathbb{Z}$ 가 존재한다. 이는 곧 $ax=\equiv 1\;(\text{mod}\; n)$ 임이 성립하게 하는 $x\in\mathbb{Z}$ 가 존재한다는 것이며, 따름정리($N.T$) 3.12.1) 에 따라 그 값은 유일하다. 이 값이 역원의 정의에 해당하므로 $x=a^{-1}\;(\text{mod}\; n)$ 가 역원이다. $_\blacksquare$

 

 

 

 

 

[참고문헌]

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

 

 

 

 

 

 

1. 중학교때 배우는 그것 맞다. [본문으로]