개나 소나 이해하는 중국인의 나머지 정리 (2부)

1부 보러가기

3 으로 나누어 2가 남고,

5로 나누어 3이 남고,

7로 나누어 2가 남는 수는?

합동방정식

---

  지난 시간엔 사장의 고민과 5세기 중국인의 고민을 같이 살펴봤다. 보기엔 별것 아닌 듯 보여도 막상 풀려니 안 풀리는 문제였다. 이제 여러분은 ≡과 합동을 대강 알게 되었다. 그럼 문제로 들어가 볼까?

  사장은 조건에 맞는 수를 구하느라 진을 빼는 중이다. 알지 못하는 수를 우리는 미지수라고 부른다. 미지수가 들어간 식을 방정식이라고 한다. 우리가 자주 보는 방정식은 이렇게 생겼다.

$4x + 15 = 9$

$x^2 - 6x + 9 = 16$

(참고로 위 식 해는 $x=-4$, 아래는 $x=7, -1$이다.)

  이렇듯 =를 사이에 두고 모르는 숫자 x가 있어 그걸 풀 수 있다. 그럼 ≡가 있는 방정식은 없을까? 합동식인데 x가 있는 방정식이니, 이런 식을 합동방정식이라 부르자.

보통 1차합동방정식은 이렇게 생겼다.

$25x\equiv10 \pmod{15}$

  $25x$는 15로 나누어 10이 남는다는 말이다. 이 정도면 계산이 필요 없긴 하다. $x=1$ 이면 $25\equiv10 \pmod{15}$니까 맞다. $x=2$는 성립 안 하고, $x=3$이면 $75\equiv10 \pmod{15}$가 성립한다.

아마 답은 $x= 1, 3, 5\dotsc$인 모양이다. 이렇게 합동방정식의 해는 하나가 아니며 ≡를 넣어 표현할 수 있다. 위 같은 경우는 $x\equiv1 \pmod{2}$일 것이다.

일차합동식 일차합동식은 일차방정식의 합동식 Ver.이다. 일차합동식의 해는 x≡☆ (mod ◇) 형태다.

일차합동식 풀어보기

---

  그럼 $25 \equiv10 \pmod{15}$를 '수학적'으로 풀어보자. 사장이 원하는 답은 일차합동식과 큰 관련이 있다.

  우리가 알고 싶은 건 $ax \equiv b \pmod{m}$을 만족하는 x다. ≡가 있는 걸 보니 ax와 b는 m으로 나눈 나머지가 같다. 식으로 표현하면 이렇다.

ax = □m + ※

b  = △m + ※

(□, △, ※는 당연히 정수다)

※가 공통이니까 따로 정리할 수 있다. 따라서

※ = ax-□m = b-△m,

ax-b = (□-△)m = km

이다.

  a, b, m은 알고 x, k는 모른다. 그런데 k를 y로 바꾸면 x와 y가 있는, 그나마 보기에 평범한 식이다.

$ax - my = b$

  이런 방정식을 선형 디오판토스 방정식이라고 한다. 옛날 그리스 수학자 디오판토스가 열심히 연구해서 이런 이름이 붙었다. 여기서 디오판토스 방정식을 구구절절 설명할 생각은 없다. 하나 확실한 건, 선형 디오판토스 방정식에 해가 존재하려면 b가 (a, m)의 최대공약수에 나누어떨어져야 한다는 점이다.

수학자들이 내놓은 결론 선형 디오판토스 방정식에 정수해가 존재할 조건은 'b가 (a, m)의 최대공약수에 나누어떨어질 것'이다.

알아두면 좋은 점 1  물론 여기서는 디오판토스 방정식의 정수해만 이야기한다. 정수 이외 해를 허락하면 아무 x나 잡아도 그에 맞는 y가 있을 것이다.

알아두면 좋은 점 2  디오판토스 방정식의 유명한 예는 바로 페르마의 마지막 정리일 것이다. 심지어 페르마는 악명높은 ‘여백이 부족해 적지 못했다’라는 글귀를 디오판토스가 쓴 <산학> 귀퉁이에 적어놓았다. 읽다가 영감이 온 모양이지?

  a, m의 최대공약수를 d라고 부르자. 즉 b가 d에 나누어떨어져야만 위 일차합동식의 해가 존재한다.

  만약 저 조건이 맞아서 정수해가 존재한다고 하자. 그럼 그 해는 얼마일까? 다행히 수학자들이 다 구해 두었다.

디오판토스 방정식의 해  $ax + by = c$인 선형 디오판토스 방정식에서 해가 존재할 때 $(x, y)$가 해라면 $(x + kv, y – ku)$도 해다. (k는 정수, u와 v는 각각 a와 b를 $gcd(a, b)$로 나눈 것)

  헷갈리지 않게 원래 식으로 쓰자면 u와 v는 각각 a와 m을 $gcd(a, m)$으로 나눈 값이다.

  보다시피 선형 디오판토스 방정식의 x는 가짓수가 무한하다(존재한다면). 그러나 우리는 합동식을 푸니까 x는 0보다는 크고 b보다는 작아야 함을 잊지 말자.

  디오판토스 방정식에서 해를 $x_0$, $y_0$라고 하자. $x_{0}$는 수많은 해 중에 제일 작은 양수다. 선형 디오판토스 방정식의 해에 따라 정수해 쌍은 $(x,y)=(x_0+\frac{mk}{d}, y_0-\frac{ak}{d})$다. 이 쌍의 x들이 우리가 원하는 일차합동식의 해가 되어줄 것이다.

잠깐, $x=x_{0}+\frac{mk}{d}$라고?

그럼 x는 '$\frac{m}{d}$의 정수곱에 $x_{0}$를 더한 것'이라고 말해도 되겠네?

그럼 $x \equiv x_{0} \pmod{{m/d} }$라고 불러도 되지 않을까?

  바로 예시로 들어가 보자.

예시- $35x \equiv14 \pmod{21}$의 해는?

성질 7

“$ab \equiv{ac} \pmod{m}$ 이고  $d=gcd(a, m)$ 이면 $b \equiv c \pmod{m/d}$다.”

를 기억하는가?

이 공식을 알면 합동식 양변을 나누어 쉽게 문제를 풀 수 있다.

  위 식을 쪼개면 $7 \times 5x \equiv 7 \times 2 \pmod{21}$이 된다. 7과 21의 최대공약수는 7이니까 $5x \equiv 2 \pmod{21/7=3}$으로 바꾸어 쓸 수 있다. 디오판토스 식으로 쓰면 $5x-3y = 2$고 제일 단순한 해는 'x가 1, y가 1'이다.

  단순해진 합동식은 더는 나눌 수가 없으니 여기서 멈추자. 이 단순해진 디오판토스 방정식의 해는 $(1 + k \times 3/1 , 1 – k \times 5/1)=(1+3k, 1-5k)$다. 우리한테는 x만 필요하니 결국 해는 $x \equiv 1 \pmod{3}$이다.(다른 말로 하면 3으로 나누어 나머지가 1인 수, 그러니까 1, 4, 7, 10....인 것이다.)

  근데 이건 단순해진 디오판토스 식의 해일 뿐 우리가 원하는 디오판토스 식의 해가 아니다. 물론 1, 4, 7, 10… 도 답이지만 뭔가 부족하다.

$35x \equiv 14 \pmod{21}$역시 쉬운 해를 구해서 $mk/d$를 더하면 일반적인 해가 될 텐데….

아까 구한 1, 4, 7, 10... 이 쉬운 해 아닌가!

$x_{0}=1$이라면 $1+k21/7=1+3k  \to x \equiv1 \pmod{21}$

$x_{0}=4$라면 $4+k21/7=4+3k \to x \equiv4 \pmod{21} \dots$

  ($x \equiv 22 \pmod{21}$부터는 쓰지 말자. 21로 나누어 나머지가 어떻게 21이냐는 말이다.)

  이렇게 일차합동방정식의 해를 구해 보았다. 보다시피 해는 7가지가 나왔다. 물론 이보다 더 복잡한 일차합동식이 있으며, 지금 배운 방법으로 풀 수 없는 합동식도 있지만 우린 여기까지만 하자. 필요한 건 다 챙겼으니 말이다.

  다음 시간에...

3부 보러가기

아무튼 위 일차합동식의 정답은 $x \equiv 1, 4, 7, 10, 13, 16, 19 \pmod{21}$이다. ( x는 21로 나누어 나머지가 1, 4, 7, 10... 인 정수)