[정수론] 5. 고차 합동 방정식

inverse modulo

$ax \equiv 1 \mod p$일 때 $x$를 inverse modulo(모듈러 역원)라고 한다.

 

하지만 언제나 존재하는 것은 아니다.

예를들어 $2x \equiv 1 \mod 4$일 때는 존재하지 않는다.

$ax - py = 1$로 나타낼 수 있으니 $\gcd(a,p) = 1$인 경우에만 inverse modulo가 존재한다.

$p$가 소수라면 $0 < a < p$에서 $\gcd(a,p) = 1$이니 언제나 존재할 것이다.

 

고차 합동 방정식

$x^2+1 \equiv 0 \mod m$을 보자.

$m = 5$일 때 $x = 2, 3$인 해를 가진다.

그런데 $m = 3$일 때는 해를 가지지 않는다.

이처럼 고차 합동방정식은 $m$이 소수이더라도 해가 존재하지 않을 수 있다.

 

그런데 $x^2+x \equiv 0 \mod 6$을 보면 $x = 0,2,3,5$로 4개의 해를 가진다.

2차 방정식에서 4개의 해를 가진다는 사실은 흥미롭다.

 

>> Theorem)

$f(x) = a_0x^d + a_1x^{d-1} + \cdots \ a_d$ $(d \ge 1)$ 이고 소수 $p \nmid a_0$일 때 $f(x) \equiv 0 \mod p$는 최대 $d$개의 해를 가진다.

 

proof

다항식은 나머지를 사용해서 $f(x) \equiv q(x)g(x) + r(x) \mod p$로 나타낼 수 있고 $deg r(x) < deg q(x)$일 것이다.

Corollary)

정수계수를 가지는 다항식 $f(a) \equiv 0 \mod p$라면 $f(x) \equiv (x-a)g(x) \mod p$이다.

인수분해가 가능하다는 따름정리이다.

 

$f(x) \equiv 0 \mod p$가 $a_1$을 해로 가진다고 하면 Corollary에 의해 $f(x) \equiv (x-a_1)g_1(x) \mod p$로 나타낼 수 있다.

마찬가지로 $a_2$도 해로 가진다면 $f(x) \equiv (x-a_1)(x-a_2)g_2(x) \mod p$이다.

이를 $d$번 반복하면 $f(x) \equiv (x-a_1)(x-a_2)\dots(x-a_d) \mod p$가 될 것이다.

여기에서 추가적인 해 $a_0$이 존재한다고 하면 $f(a_0) \equiv 0 \mod p$가 성립할 것이다.

$f(a_0) \equiv (a_0-a_1)(a_0-a_2)\dots(a_0-a_d) \equiv 0 \mod p$가 성립하려면 $a_0 \neq a_i$이므로 각 요소들 중 적어도 하나는 $p$를 나누어야 한다. (즉 $a_0-a_i | p$)

$0 \le a_i < p$이므로 $a_0-a_i$는 $p$의 배수가 될 수 없기 때문에 추가적인 해 $a_0$은 존재할 수 없다. $\Box$

 

$p$가 소수가 아니라면 서로 다른 요소들의 곱으로 $p$의 배수를 만들 수 있기 때문에 추가적인 해가 존재할 수 있다.

위 방정식 $x^2+x \equiv 0 \mod 6$을 예로 들자.

$x = 0, -1(5)$가 성립하므로 $x(x+1) \equiv 0 \mod 6$으로 인수분해할 수 있다.

이 인수분해된 식에 $x=2$를 대입한다면 $2 \times 3 = 6 \equiv 0 \mod 6$이므로 추가적인 해를 찾을 수 있다.