[정수론] 합동식2. 선형 합동식

디오판토스 방정식

디오판토스 방정식은, 정수만을 해로 가질 수 있는 다항 부정방정식이다.

대표적으로 $x^2 + y^2 = z^2$과 같은 방정식이 있으며, 이는 당연히 $x=3,y=4,z=5$와 같은 해를 갖는다.

 

그 중에서 $ax+by=c$와 같은 형태의 디오판토스 방정식은 해의 존재성과 관련하여 한가지 정리가 있다.

 

 

 

Theorem. 선형 디오판토스 방정식 $ax+by=c$는 $d=\mathrm{gcd}(a,b)$에 대해 $d \vert c$일 때만 해를 갖는다. 

 

Proof. 필요충분조건이므로, 두 경우에 대해 모두 증명해보겠다.

 

$d=\mathrm{gcd}(a,b)$라면, 어떤 정수 $r, s$에 대해 $a=dr, b=ds$로 나타낼 수 있다. 

이때, $ax+by=c$의 해가 존재한다면, 어떤 정수 $x_0, y_0$에 대해 $ax_0 + by_0 =c$가 성립한다.

 

이 식을 $d$를 이용해 다시 쓰면, $drx_0 + dsy_0 = d(rx_0 + sy_0) = c$가 된다.

따라서 $d \cdot k = c$를 만족하는 정수 $k$가 존재하므로, $d \vert c$임을 알 수 있다.

 

 

반대로, $d \vert c$인 경우를 생각해보자. 

$d=\mathrm{gcd}(a,b)$라면, $d=ax_0+by_0$인 정수 $x_0, y_0$이 존재한다.

위의 내용은 Well Ordering Principle을 이용해서 증명할 수 있다. 참고 : WOP

그런데 합동식을 다루는 글에서 엄밀하기 증명하기에는 사실 좀 관련 없는 내용인것 같아서 pass...

 

어쨋든, 그렇다고 받아들이면.. $d \vert c$라면 $c=td$인 정수 $t$가 존재한다는 것이다.

따라서 $c=td=t(ax_0+by_0)$ 이므로, 방정식 $ax+by=c$의 해로 $tx_0, ty_0$가 존재하게 된다. $\blacksquare$

 

 

---

 

 

선형 디오판토스와 관련한 정리를 하나만 더 살펴보자.

 

 

Theorem. 두 정수 $x_0, y_0$가 선형 디오판토스 방정식 $ax+by=c$의 해라면, 이 방정식의 일반해는 다음과 같다.

$$x=x_0 + \left(\frac{b}{d}\right)t, \,y=y_0 - \left(\frac{a}{d}\right)t$$

 

Proof. $x', y'$이 방정식 $ax+by=c$의 또 다른 정수해라고 하자. 그럼 다음이 성립한다.

$$ax_0+by_0 = ax'+by' = c$$

양변을 이항하면 $a(x'-x_0) = b(y_0-y') \cdots (1)$이 성립한다.

 

이때, 이 선형 디오판토스 방정식의 해가 존재하므로, $d=\mathrm{gcd}(a,b)$라고 하면, $d\vert c$이다.

따라서 $a=dr, b=ds$인 정수 $r, s$가 존재한다.

이를 이용해서 위의 식$(1)$을 다시 써보면 아래와 같다.

$$dr(x'-x_0) = ds(y_0-y')$$

이 식의 양변을 $d$로 나누면, $r(x'-x_0)=s(y_0 - y') \cdots (2)$가 성립한다.

 

즉, $r \cdot k = s(y_0-y')$인 정수 $k$가 존재한다는 의미이다.

따라서 $r \vert s(y_0 -y')$인데, 정수 $r$과 $s$는 서로소이므로 $r \vert (y_0-y')$이다.

결국 어떤 정수 $t$에 대해 $rt = y_0-y'$이 성립한다. 

이를 식 $(2)$에 대입하면 $x'-x_0 = st$임을 알 수 있다.

결과적으로 아래와 같은 결과를 얻을 수 있다. 

$$x' = x_0 + st = x_0 + \left(\frac{b}{d}\right)t, \,y' = y_0 - rt = y_0 - \left(\frac{a}{d}\right)t \,\blacksquare$$ 

 

 

 

---

 

 

 

선형 합동식

 

 

선형 합동식이란, $ax \equiv b \bmod n$과 같은 형태의 방정식을 말한다. 

 

$ax \equiv b \bmod n$이라면, 정의에 의해 $n \vert ax-b$이다.

따라서 $nk = ax -b$를 만족시키는 정수 $k$가 존재한다는 것이다.

이때, 이항하면 $ax-nk=b$ 이므로, 선형 합동식은 선형 디오판토스 방정식과 동치임을 알 수 있다.

 

 

 

Theorem. 선형 합동식 $ax \equiv b \bmod n$은 $d= \mathrm{gcd}(a,n)$에 대해 $d \vert b$일 때 해가 존재한다. 

 

Proof. $ax \equiv b \bmod n$의 해는 선형 디오판토스 방정식 $ax -nk =b$와 동일함을 확인하였다. 

따라서 $ax \equiv b \bmod n$의 해의 존재 여부는 $ax -nk =b$의 해의 존재 여부를 확인하면 된다.

 

선형 디오판토스 방정식 $ax -nk =b$는 $d = \mathrm{gcd}(a, -n) = \mathrm{gcd}(a, n)$에 대해 $d \vert b$일 때 해가 존재한다.

따라서 $d \vert b$라면, $ax \equiv b \bmod n$의 해가 존재한다는 것을 확인할 수 있다. $\blacksquare$

 

 

 

선형 합동식을 푸는 것과 선형 디오판토스 방정식을 푸는 것이 동일하다는 것을 확인하였다.

따라서, 합동식 $ax \equiv b \bmod n$의 해가 $x_0, y_0$이라면, 일반해가 다음과 같다는 것도 알 수 있다.

$$x=x_0 + \left(\frac{n}{d}\right)t, y=y_0 + \left(\frac{a}{d}\right)t$$

물론, 우리는 $x$만 궁금한 것이기 때문에 $y$의 해의 형태는 크게 신경쓰지 않아도 된다.

 

 

그런데, 이때는 디오판토스 방정식과는 달리 $($법 $n$에 대해 합동이 아닌$)$ 무한개의 해를 갖지 않는다.

더 정확히 표현하면, 방정식 $ax \equiv b \bmod n$은 법 $n$에 대해 $d = \mathrm{gcd}(a, n)$개의 합동이 아닌 해를 갖는다.

이때, 서로 합동이 아닌 $d$개의 해는 다음과 같다.

$$x_0, x_0 + \left(\frac{n}{d}\right), x_0 + \left(\frac{2n}{d}\right), \cdots , x_0 + \left(\frac{(d-1)n}{d}\right)$$

 

이를 증명하기 위해서는 두 가지의 증명이 필요하다.

$(1)$ $d$개의 해가 법 $n$에 대해 합동이 아님을 보여야 한다.

$(2)$ $d$개의 해 이외에는 존재하지 않음을 보여야 한다.

 

하나씩 증명해보자...

 

 

---

 

$(1)$ $x = x_0 + \left(\frac{nt}{d}\right), (0 \leq t \leq d-1)$는 법 $n$에 대해 합동이 아니다.

 

Proof. 귀류법을 이용해서 증명할 수 있다.

서로 다른 두 정수 $0 \leq t_1, t_2 \leq d-1$에 대해, $x_0 + \left(\frac{nt_1}{d}\right), x_0 + \left(\frac{nt_2}{d}\right)$가 합동이라고 가정하자. 

 

즉, $x_0 + (nt_{1}/d) \equiv x_0 + (nt_{2}/d) \bmod n$이다.

양변에 $x_0$를 빼면, $nt_{1}/d \equiv nt_{2}/d \bmod n$이다.

 

이때, $\mathrm{gcd}(n/d, n) = n/d$이므로, $t_1 \equiv t_2 \bmod d$임을 알 수 있다.

즉, $d \vert (t_1 - t_2)$라는 것인데, $0 < t_1 - t_2 < d$ 이므로 모순이다.

 

따라서 우리는 가정이 틀렸음을 알 수 있다. $\blacksquare$

 

 

$(2)$ 방정식 $ax \equiv b \bmod n$은 주어진 $d$개의 해 이외에는 법 $n$에 대해 합동이 아닌 해가 존재하지 않는다.

 

Proof. 어떤 $d$ 이상인 정수 $t'$를 선형 합동식의 일반해의 꼴에 대입해보면 아래와 같다.

$$x = x_0 + \left( \frac{n}{d} \right)t' \cdots (a)$$

 

이때, $t'$를 $d$로 나누었을 때의 몫을 $q$, 나머지를 $r$이라고 하면, $t'$은 다음과 같이 나타낼 수 있다.

$$t' = qd + r, (0 \leq r < d)$$

이를 식 $(a)$에 대입하면 아래와 같다.

$x = x_0 + (n/d)t' = x_0 + (n/d)(qd + r) = x_0 + nq + (n/d)r$

$\equiv x_0 + (n/d)r \bmod n$

 

따라서 $d$ 이상인 정수 $t'$에 대한 해 $x$는 $d$개의 해 중 하나와 합동임을 알 수 있다.

특히, $t'$을 $d$로 나누었을 때의 나머지 $r$에 대해 $x_0 + (n/d)r$과 합동이다. $\blacksquare$

 

 

 

결과적으로, $(1), (2)$에 의해서 $ax \equiv b \bmod n$은 법 $n$에 대해 $d$개의 합동이 아닌 해를 갖으며 이는 다음과 같다. $($단, $x_0$는 $ax \equiv b \bmod n$의 한 해이다.$)$

$$x_0, x_0 + (n/d), x_0 + (2n/d), \cdots , x_0 + ((d-1)n/d)$$