선형 합동 방정식¶
이 방정식은 다음과 같은 꼴입니다.
여기서 $a$, $b$, $n$은 주어진 정수이고 $x$는 미지의 정수입니다.
구간 $[0, n-1]$에서 $x$의 값을 구해야 합니다(수직선 전체에서는 해가 무한히 많을 수 있으며, 이 해들이 서로 $n \cdot k$만큼 차이가 난다는 것은 자명합니다. 여기서 $k$는 임의의 정수입니다). 해가 유일하지 않은 경우에는 모든 해를 구하는 방법을 살펴보겠습니다.
역원소를 구하는 풀이¶
먼저 $a$와 $n$이 서로소($\gcd(a, n) = 1$)인 더 간단한 경우를 살펴봅시다. 이 경우 $a$의 역원을 구할 수 있고, 방정식의 양변에 이 역원을 곱하면 유일한 해를 얻을 수 있습니다.
이제 $a$와 $n$이 서로소가 아닌($\gcd(a, n) \ne 1$) 경우를 살펴봅시다. 이 경우 해가 항상 존재하지는 않습니다(예를 들어 $2 \cdot x \equiv 1 \pmod 4$는 해가 없습니다).
$g = \gcd(a, n)$라고 합시다. 즉, $g$는 $a$와 $n$의 최대공약수이며, 이 경우에는 1보다 큽니다.
그러면 $b$가 $g$로 나누어떨어지지 않을 때에는 해가 존재하지 않습니다. 실제로 임의의 $x$에 대해 방정식의 좌변 $a \cdot x \pmod n$은 항상 $g$로 나누어떨어지지만 우변은 $g$로 나누어떨어지지 않으므로, 해가 존재하지 않는다는 결론이 나옵니다.
$g$가 $b$를 나누면, 방정식의 양변을 $g$로 나누어(즉 $a$, $b$, $n$을 $g$로 나누어) 다음과 같은 새로운 방정식을 얻습니다.
이 방정식에서 $a^\prime$과 $n^\prime$은 이미 서로소이며, 이러한 방정식을 다루는 방법은 앞에서 이미 살펴보았습니다. 이렇게 하여 $x$에 대한 해로 $x^\prime$을 얻습니다.
이 $x^\prime$이 원래 방정식의 해이기도 하다는 것은 자명합니다. 그러나 이것이 유일한 해는 아닙니다. 원래 방정식은 정확히 $g$개의 해를 가지며, 그 해들이 다음과 같은 꼴임을 보일 수 있습니다.
정리하면, 선형 합동 방정식의 해의 개수는 $g = \gcd(a, n)$이거나 0이라고 말할 수 있습니다.
확장 유클리드 알고리즘을 이용한 풀이¶
선형 합동식은 다음과 같은 디오판토스 방정식으로 다시 쓸 수 있습니다.
여기서 $x$와 $k$는 미지의 정수입니다.
이 방정식을 푸는 방법은 해당 문서인 선형 디오판토스 방정식에 설명되어 있으며, 그 방법은 확장 유클리드 알고리즘을 적용하는 것입니다.
그 문서에서는 구한 해 하나로부터 이 방정식의 모든 해를 구하는 방법도 설명하는데, 덧붙이자면 이 방법을 자세히 살펴보면 앞 절에서 설명한 방법과 완전히 동일합니다.