선형 합동방정식

선형 합동방정식은 다음과 같은 형태의 방정식이다.

이때, $a, b, n$은 주어진 상수이고 $x$는 미지수이다.

구간 $[0, n - 1]$에서 $x$값을 구해야 한다 (당연히, 수직선에서 $n \cdot k$만큼 차이나는 무수히 많은 해가 존재한다). 해가 유일하지 않다면, 모든 해를 구하는 방법을 고려할 것이다.

역원을 통해 구한 해

$a$와 $n$이 서로소인 ($\gcd(a, n) = 1$)인 간단한 경우를 먼저 생각하자. 이때 $a$의 [역원]](./module-inverse.html)을 찾을 수 있고, 이를 양변에 곱함으로써 유일한 해를 얻는다.

$a$와 $n$이 서로소가 아닌 ($\gcd(a, n) \ne 1$) 경우를 생각하자. 이때 해는 존재하지 않을 수도 있다 (예를 들어 $2 \cdot x = 1 \pmod 4$는 해를 갖지 않는다). $g = \gcd(a, n)$을 $a$와 $n$의최대공약수라고 하자.

$b$가 $g$로 나누어 떨어지지 않으면 해는 존재하지 않는다. 어떠한 $x$에 대해서도 좌변 $a \cdot x \pmod n$은 $g$로 나누어 떨어지지만 우변은 그렇지 않기 때문이다.

$g$가 $b$를 나누면, 방정식의 양변을 $g$로 나누어 새로운 방정식을 얻는다:

이때 $a^\prime$과 $n^\prime$은 서로소이고, 이 방정식에서 해를 구하는 방법은 이미 논하였다. $x$에 대한 해 $x^\prime$를 얻었다고 하자.

$x^\prime$이 원래 방정식의 해가 된다는 것은 분명하지만, 이것은 유일한 해가 아니다. 원래 방정식이 해를 정확히 $g$개 가짐을 보일 수 있고, 이들은 다음과 같은 꼴이다:

정리하면, 선형 합동방정식의 해의 개수는 $g = \gcd(a, n)$이거나 0이다.

확장 유클리드 호제법을 통한 해

원래 선형 합동식을 다음 디오판토스 방정식으로 다시 쓸 수 있다:

이때 $x$와 $k$는 미지수이다.

이러한 방정식을 푸는 것은 선형 디오판토스 방정식 문서에서 다루었고, 이는 확장 유클리드 호제법을 적용하는 것이다.

이 방법은 찾아낸 하나의 해로부터 모든 해를 구하는 방법 또한 묘사하는데, 잘 생각해보면 이전 절에서 묘사한 방법과 동등하다.