[정수론 입문 시리즈 14편] 선형 합동식은 어떻게 풀까?

지난 글에서는 모듈러 역원이 모듈러 세계의 나눗셈 역할을 한다는 점을 봤습니다. 이제 그 도구를 실제 문제에 적용해 보겠습니다. 정수론에서 자주 만나는 기본 문제는 다음과 같습니다.

$$ax \equiv b \pmod n$$

이 식을 선형 합동식이라고 합니다.

What this post covers

• 선형 합동식의 의미를 설명합니다.
• 역원이 있는 경우 해를 빠르게 구하는 방법을 봅니다.
• 역원이 없는 경우에도 해가 존재할 수 있는지 설명합니다.
• 다음 글의 중국인의 나머지 정리로 이어집니다.

이번 글에서 새로 나오는 용어

• 선형 합동식 (Linear Congruence): $ax \equiv b \pmod n$ 꼴의 합동식입니다.
• 모듈러 역원 (Modular Inverse): 곱해서 1이 되는 모듈러 세계의 역수 역할입니다.
• 합동 (Congruence): 같은 나머지를 가지는 관계입니다.
• 중국인의 나머지 정리 (Chinese Remainder Theorem): 여러 합동식을 동시에 푸는 정리입니다.

가장 쉬운 경우: 역원이 있을 때

만약 $\gcd(a,n)=1$이면 $a$는 mod $n$에서 역원을 가집니다. 그러면 양변에 그 역원을 곱해 바로 풀 수 있습니다.

예를 들어

$$3x \equiv 4 \pmod 7$$

에서 3의 mod 7 역원은 5입니다. 따라서

$$x \equiv 5 \times 4 = 20 \equiv 6 \pmod 7$$

입니다.

역원이 없으면 항상 해가 없을까?

그렇지는 않습니다. 핵심은

$$d = \gcd(a,n)$$

가 $b$를 나누는지 보는 것입니다.

$ax \equiv b \pmod n$이 해를 가질 필요충분조건은 $\gcd(a,n) \mid b$이다.

이 조건은 1차 디오판토스 방정식의 존재 조건과 매우 닮아 있습니다.

여기서 한 걸음 더 나가면 해의 모양도 갈립니다.

• $\gcd(a,n)=1$이면 해는 mod $n$에서 하나의 합동류로 정리되고
• $d=\gcd(a,n)>1$인데 $d \mid b$이면 보통 mod $n$에서 서로 다른 해가 여러 개 생깁니다.

그래서 선형 합동식에서는 먼저 "해가 있는가?"를 보고, 그다음에 "해가 몇 개의 합동류로 나타나는가?"를 보는 흐름이 중요합니다.

예시 1. 해가 하나의 합동류로 정리되는 경우

다시

$$3x \equiv 4 \pmod 7$$

을 보면 $\gcd(3,7)=1$이므로 해는 하나의 합동류로 정리됩니다.

$$x \equiv 6 \pmod 7$$

즉, 6, 13, 20, 27, ...이 모두 해입니다. 이 경우에는 mod 7에서 해가 하나의 합동류로 깔끔하게 정리됩니다.

예시 2. 해가 존재하지만 역원이 없는 경우

다음 식을 봅시다.

$$4x \equiv 2 \pmod 6$$

여기서

$$\gcd(4,6)=2$$

이고, 2는 오른쪽의 2를 나눕니다. 따라서 해가 존재합니다.

직접 대입해 보면

$$4 \times 2 = 8 \equiv 2 \pmod 6$$

이므로 $x \equiv 2 \pmod 6$는 해입니다. 또 $x \equiv 5 \pmod 6$도 해가 됩니다.

즉, 역원이 없다고 해서 무조건 해가 없는 것은 아닙니다. 이 예시에서는 mod 6에서 해가 두 개의 합동류 $x \equiv 2,5 \pmod 6$로 나타납니다.

예시 3. 해가 없는 경우

이번에는

$$4x \equiv 3 \pmod 6$$

을 봅시다. 여전히 $\gcd(4,6)=2$이지만, 2는 3을 나누지 못합니다. 따라서 해가 없습니다.

왜 디오판토스 방정식과 닮아 있을까?

합동식

$$ax \equiv b \pmod n$$

은

$$ax - b = ny$$

로 바꿀 수 있고, 다시 정리하면

$$ax + ny = b$$

가 됩니다. 즉, 선형 합동식은 사실상 1차 디오판토스 방정식과 연결되어 있습니다.

Common mistakes

1. 역원이 없으면 무조건 해가 없다고 생각하는 실수

해의 존재 조건은 $\gcd(a,n) \mid b$입니다. 역원의 존재 여부와 완전히 같지는 않습니다.

2. 한 해만 찾고 끝내는 실수

합동식의 해는 보통 하나의 수가 아니라 하나 이상의 합동류입니다. 특히 $\gcd(a,n)>1$인 경우에는 여러 합동류가 함께 나올 수 있습니다.

3. mod를 유지하지 않고 일반 방정식처럼 다루는 실수

합동식은 항상 mod $n$의 기준을 놓치지 않아야 합니다.

Wrap-up

이번 글에서는 선형 합동식 $ax \equiv b \pmod n$을 역원과 최대공약수 관점에서 해석하는 방법을 정리했습니다. 특히

$$\gcd(a,n) \mid b$$

가 해의 존재 조건이라는 점이 핵심입니다.

다음 글에서는 여러 합동식을 동시에 푸는 강력한 도구인 중국인의 나머지 정리로 넘어가겠습니다.