7. 방정식의 풀이 (종합편)

VII.방정식의 풀이

 정수론은 정수계수정수방정식(디오판토스방정식)의 해법을 탐구하는 분야이다. 

일차디오판토스 방정식은 최대공약수가 일차결합으로 표현된다는 사실을 통해 해를 구할 수 있었다.

그러나 모든 디오판토스 방정식의 해를 직접 구하기는 쉽지 않다. 그러므로 수학자들은 합동방정식이라는 방법을 생각해내었다.

그것은 바로 수의 범위를 유한개로 제한 하는 것이었고 수의 범위를 줄이는 방법으로 '~을 법으로 하는' 동치류들을 생각하는 방식을 생각해내었는데 이것을 통하여 Z에서의 연산을 Zp의 연산으로 끌어옴으로서 좀 더 쉽게(물론 상대적으로 쉽게) 해에 대한 접근을 할 수 있었다.

그런데 소수를 법으로 하는 다항합동방정식만 있는 것은 아니다. 그러므로 합성수를 법으로 하는 다항합동식은 먼저 합성수를 표준분해 한 후 표준분해한 각 소수에 대한 합동방정식을 풀어내어 연립하는 방법을 채택하게 된다. 이러한 풀이를 가능하게 해준 것은 바로 중국인의 나머지정리이다.

이제 남은 것은 소수를 법으로 한 복잡한 합동방정식을 간단하게 하는 문제이다. 단순히 차수가 큰 경우에는 주로 페르마의 소정리나 오일러정리를 통해 차수를 낮추거나 여의치 않은 경우에는 이산로그를 활용하기도 한다. 그러나 법으로 하는 소수자체가 큰 경우도 있다. 그러한 경우엔 일차합동방정식의 경우 유클리드 호제법을 통해 역원을 구해내는 방법이 주요하지만 2차에선 르장드르기호나 야코비기호의 이차상반법칙을 이용하여 간단히 만들어 해의 존재성을 예측해볼 수는 있다. 

1. 일차부정방정식(일차디오판토스방정식)

 $mZ+nZ=(m,n)Z$라는 것을 이용하여 일차부정방정식의 해를 구할 수 있다. 

$mx+ny=c$라는 방정식이 정수해를 갖는지 알아보려면 c가 (m,n)Z의 원소인지만 알면 충분하다. 만약 원소가 아니라면 이는 m,n의 일차결합으로 c를 만들어낼 수 없으므로 해가 없는 것이다. 이를 아는 방법은 간단하다 (m,n)|c 인지만 살펴보면 된다.

만약 해가 존재한다면 유클리드 호제법을 이용한 역순전개로 $mx+ny=(m,n)$을 만족하는 x,y를 찾을 수 있고 양변을 적절히 곱하면 $mx+ny=c$를 만족하는 x,y도 찾을 수 있다. 그렇다면 특수해는 구해진 것이다.

마지막으로 일반해를 구한다. 일반해를 구하는 공식은 $x=x_0+\frac{n}{d}k$, $y=y_0-\frac{m}{d}k$ 이다.

2. 일차합동방정식

$ax \equiv b$ (mod m) 형식의 일차합동방정식은 a의 역원이 있어서 계수a를 약분할 수 있다면 해를 구할 수 있고 해가 존재한다. 즉 a의 역원이 존재하고 역원이 존재하려면 (a, m)=1이어야 한다. a의 역원을 찾는 방법은 유클리드 호제법의 역순전개를 쓰는 방법이다. 만약 (a, m)=1이 아니라면 식을 적절히 약분 할 수 있으면 계수와 법이 서로소가 되도록 약분해주고 나중에 약분된 법을 다시 돌려놓으면 된다.(물론 돌려놓는 방법이 있다.) 만약 약분이 안된다면 해가 없다.

약분된 법을 다시 돌려놓는 방법은 $x \equiv c$ (mod m) $\Rightarrow$ $x \equiv c+tm$ (mod nm) (0<t<n) 공식을 활용하면 된다.  

3. 중국인의 나머지정리 

일차부정방정식의 해는 최대공약수의 성질로 구했지만 아직도 수 많은 형식의 방정식을 풀 수 없다. 이제 디오판토스 방정식을 합동방정식으로 변환하여 계산하는 것을 소개하고자 한다. 합동방정식으로 변환하여 계산하는 이점을 보기 위해서는 법을 소수로 바꿔주는 것이 좋다. 이 때 중국인의 나머지정리가 제 역할을 한다.

$m_{ 1 },\, \cdots ,\, m_{ n }$ : 쌍마다 서로소, $c_{ 1 },\, \cdots ,\, c_{ n } \in Z$ 일 때, 연립합동방정식 $\begin{cases} x\equiv c_{ 1 }\; (mod\; m_{ 1 }) \\ \vdots  \\ x\equiv c_{ n }\; (mod\; m_{ n }) \end{cases}$ 는 정수해를 갖고 mod $m_{ 1 } \cdots  m_{ n }$에 대하여 유일하다.

위 정리의 powerful함을 직접 예시를 하나 들어 살펴보자.

$\begin{cases} x\equiv c_{ 1 }\; (mod\; m_{ 1 }) \\ x\equiv c_{ 2 }\; (mod\; m_{ 2 }) \end{cases}$를 풀어보자. 우선 $x_1 \equiv c_{ 1 }\; (mod\; m_{ 1 })$을 만족하는 $x_1$과 $x_2 \equiv c_{ 2 }\; (mod\; m_{ 2 })$을 만족하는 $x_2$를 만들어보자. $x_{ 1 }=c_{ 1 }\cdot m_{ 2 }^{ * }\cdot m_{ 2 }\begin{cases} \equiv c_{ 1 }\; (mod\; m_{ 1 }) \\ \equiv 0\; (mod\; m_{ 2 }) \end{cases}$ $x_{ 2 }=c_{ 2 }\cdot m_{ 1 }^{ * }\cdot m_{ 1 }\begin{cases} \equiv 0\; (mod\; m_{ 1 }) \\ \equiv c_{ 2 }\; (mod\; m_{ 2 }) \end{cases}$ 위 $x_1,x_2$는 $x_{ 1 }\equiv c_{ 1 }\; (mod\; m_{ 1 })$과 $x_{ 2 }\equiv c_{ 2 }\; (mod\; m_{ 2 })$를 각각 만족하면서 다른 법에 대해서는 0이 되도록 세팅이 되었다. 이제 이 둘을 더하면 $x=x_{ 1 }+x_{ 2 }\begin{cases} \equiv c_{ 1 }+0\equiv c_{ 1 }\; (mod\; m_{ 1 }) \\ \equiv 0+c_{ 2 }\equiv c_{ 2 }\; (mod\; m_{ 2 }) \end{cases}$ 이제 만족하는 x를 제시하면 된다.  $x\equiv x_{ 1 }+x_{ 2 }\;(mod \;m_1m_2)$

이와 같이 중국인의 나머지정리를 통해 법을 쪼개서 계산이 가능하다. 이때 해의 개수는 매칭되는 모든 경우의 수가 된다. (이 말이 무엇인지는 몇문제 풀다보면 안다.)

4. 이항합동식

$ax^n \equiv b$ (mod m)의 형식의 2개의 항으로 이루어진 합동식을 이항합동식이라고 한다. 이를 도입하기 이전에 하나의 정리를 보고자 한다. 라그랑지가 정수론분야에 남긴 정리이다.

p : 소수일 때 $f(x)=a_{ n }x^{ n }+\cdots +a_{ 1 }x+a_{ 0 }\equiv 0 $ (mod p), $a_n \not\equiv 0$ (mod p)에 대하여  (1) $f(x)\equiv 0$ (mod p) : n개 이하의 정수해를 갖는다. (2) $f(x)\equiv 0$ (mod p)이 n개의 해 $c_{ 1 },\, \cdots ,\, c_{ n }$을 가지면 $f(x)\equiv a_{ n }(x-c_{ 1 })\, \cdots (x-c_{ n })$ (mod p)

그렇다면 우리가 페르마 소정리에서 익히 보던 식들을 다음과 같이 표현할 수도 있다.

$x^{ p }-x=x(x-1)\cdots (x-(p-1)) $ (mod p) $x^{ p-1 }-1=(x-1)\cdots (x-(p-1))$ (mod p)

두번째 식에서 x=0을 넣어 약간만 정리하면 윌슨의 정리를 얻을 수 있다.

n : 소수 ⇔ (n-1)!$\equiv$-1 (mod n)

$x^{ \frac { p-1 }{ 2 }  }\equiv 1$ (mod p)와 $x^{ \frac { p-1 }{ 2 }  }\equiv -1$ (mod p)이라는 합동식을 탐구해보자.

라그랑지 정리에 의해 두 방정식 모두  $\frac { p-1 }{ 2 } $ 가지의 해를 가지고 있어야 하며 첫번째 식의 해는 제곱수의 형식이다. 그러므로 $\pm$1부터 $\pm \frac { p-1 }{ 2 } $ 까지의 정수를 제곱한 제곱수인 이차잉여류가 첫번째 식의 해가 될 것이고 나머지는 두번째 식의 해가 될 것이다.

5. 이차합동식

이차합동식이 만약 $x^2 \equiv d$ 와 같은 간단한 형식이면 우리는 이차잉여인 것을 찾으면 된다. 그러나 일반 $ax^2+bx+c \equiv 0$과 같은 형식이면 어떻게 해의 존재성을 알 수 있을지 생각해보자. 

$ax^{ 2 }+bx+c\equiv 0 $ (mod p) $\Leftrightarrow x^{ 2 }+a^{ * }bx+a^{ * }c\equiv 0$ (mod p) $\Leftrightarrow x^{ 2 }+a^{ * }bx+(2^{ * }a^{ * }b)^{ 2 }\equiv (2^{ * }a^{ * }b)^{ 2 }-a^{ * }c$(modp) $\Leftrightarrow (x+2^{ * }a^{ * }b)^{ 2 }\equiv (2^{ * }a^{ * }b)^{ 2 }-a^{ * }c\equiv (2^{ * }a^{ * })^{ 2 }(b^{ 2 }-4ac)$(modp) 여기서 해가 존재하기 위해선 $b^{ 2 }-4ac$가 제곱수가 되어야 한다. $b^{ 2 }-4ac$ 를 $D$라고 하고 이를 판별식이라고 하자.

결국 이런 형식의 합동방정식이 정수해를 갖는다는 것은 판별식 $D$가 제곱수라는 것이고 이것은 $D$가 법p에 대한 이차잉여라는 것을 의미한다. 

결과로서 알아두면 좋은 것이 있어 소개한다.

소수 p가 $p \equiv 3$ (mod 4) , $a \equiv 0$ (mod p) 일 때 $\exists x \in Z \; s.t. \; x^2 \equiv a$ (mod p) $\Rightarrow$ $x^2 \equiv a$ (mod p)의 해 : $x \equiv \pm a^{\frac{p+1}{4}}$ (mod p)