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

Python에서 x를 하나씩 넣어 보며 (a*x - b) % n == 0인 값을 찾는 문제를 생각해 봅시다. 수학 기호로 쓰면 바로 다음 형태입니다.

$$ax \equiv b \pmod n$$

예를 들어 3*x % 7 == 4를 만족하는 x는 어떻게 찾을까요? 지난 글에서 본 모듈러 역원이 이 문제를 빠르게 푸는 도구가 됩니다. 이 식을 선형 합동식이라고 합니다.

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차 디오판토스 방정식과 연결되어 있습니다.

실험: 손으로 계산하기

선형 합동식은 처음부터 공식으로 밀어붙이기보다, 작은 mod에서 $x=0,1,2,\dots,n-1$을 넣어 보면 해의 존재 조건이 눈에 보입니다.

실험 1. $3x\equiv 4\pmod 7$

$x$	$3x$	mod 7 나머지
0	0	0
1	3	3
2	6	6
3	9	2
4	12	5
5	15	1
6	18	4

나머지 4가 나오는 곳은 $x=6$입니다. 따라서 $x\equiv 6\pmod 7$입니다.

실험 2. $4x\equiv 2\pmod 6$

$x$	$4x$	mod 6 나머지
0	0	0
1	4	4
2	8	2
3	12	0
4	16	4
5	20	2

이번에는 해가 두 개 보입니다.

$$x\equiv 2,5\pmod 6$$

실험 3. $4x\equiv 3\pmod 6$

위 표에서 mod 6 나머지는 0, 4, 2만 반복됩니다. 3은 한 번도 나오지 않으므로 해가 없습니다.

패턴 발견

세 실험을 비교해 봅시다.

• $3x\equiv 4\pmod 7$에서는 $\gcd(3,7)=1$이고 해가 같은 나머지를 가진 수들의 한 묶음으로 나왔습니다.
• $4x\equiv 2\pmod 6$에서는 $\gcd(4,6)=2$이고, 2가 오른쪽 2를 나누므로 해가 있었습니다.
• $4x\equiv 3\pmod 6$에서는 같은 최대공약수 2가 오른쪽 3을 나누지 못하므로 해가 없었습니다.

핵심 패턴은 왼쪽 계수와 법의 최대공약수가 오른쪽 값을 나누는가입니다. 역원이 없는 경우에도 이 조건이 맞으면 해가 생길 수 있습니다.

이론 정리

선형 합동식의 해 존재 조건

$ax\equiv b\pmod n$에 대해 $d=\gcd(a,n)$라 하겠습니다.

• $d\nmid b$이면 해가 없습니다.
• $d\mid b$이면 해가 존재합니다.
• 특히 $d=1$이면 $a$의 역원을 이용해 해가 mod $n$에서 같은 나머지를 가진 수들의 한 묶음으로 정리됩니다.

합동식은

$$ax+ny=b$$

꼴의 1차 디오판토스 방정식과 연결됩니다.

Python으로 확인하기

작은 범위에서는 모든 나머지 대표값을 대입해 해를 찾을 수 있습니다.

from math import gcd


def solve_linear_congruence(a, b, n):
    return [x for x in range(n) if (a * x - b) % n == 0]

examples = [(3, 4, 7), (4, 2, 6), (4, 3, 6)]

for a, b, n in examples:
    d = gcd(a, n)
    solutions = solve_linear_congruence(a, b, n)
    print(f"{a}x ≡ {b} (mod {n})")
    print("gcd(a,n) =", d, "| solutions =", solutions)

손으로 만든 표의 해와 Python 결과가 같은지 비교해 보세요.

Common mistakes

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

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

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

합동식의 해는 보통 하나의 수가 아니라 하나 이상의 같은 나머지를 가진 수들입니다. 특히 $\gcd(a,n)>1$인 경우에는 여러 개의 나머지 묶음가 함께 나올 수 있습니다.

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

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

Silverman 교재 연결

이 글은 Silverman 《친절한 수론 길라잡이》(경문사)의 다음 내용과 연결됩니다.

• 8장: 합동 - 8장 후반부의 선형 합동식 $ax \equiv c \pmod m$ 풀이와 직접 연결됩니다.
• 관련 정리/예제: $g=\gcd(a,m)$라고 할 때 $ax \equiv c \pmod m$은 $g\mid c$일 때 그리고 그때에만 해를 가지며, 해가 존재하면 법 $m$에서 서로 합동이 아닌 해가 정확히 $g$개입니다.

연습 문제

아래 점검 퀴즈에서 학습한 내용을 확인해 보세요.

Wrap-up

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

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

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

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