[정수론 입문 시리즈 13편] 모듈러 역원은 언제 존재할까?

RSA 암호에서 공개키 $e$로 잠근 메시지를 풀려면, 비밀키 $d$가 필요합니다. 이 $d$의 정체는 사실 $e$의 모듈러 역원입니다. 즉, 어떤 수를 곱했을 때 나머지가 1이 되게 만드는 수입니다.

지난 글에서 모듈러 세계에서는 덧셈과 곱셈이 잘 작동한다는 점을 봤습니다. 하지만 나눗셈은 더 조심해야 합니다. 실수에서는 2로 나누는 것이 늘 가능하지만, mod 6의 세계에서는 그렇지 않을 수 있습니다. 이 문제를 푸는 핵심 개념이 모듈러 역원입니다.

What this post covers

• 모듈러 역원이 무엇인지 설명합니다.
• 왜 나눗셈 문제가 사실은 역원 문제인지 이해합니다.
• 역원이 존재하는 조건이 서로소와 연결된다는 점을 정리합니다.
• 다음 글의 선형 합동식 풀이로 이어집니다.

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

• 모듈러 역원 (Modular Inverse): 어떤 수와 곱했을 때 mod $n$에서 1이 되는 수입니다.
• 서로소 (Coprime): 최대공약수가 1인 두 수의 관계입니다.
• 합동 (Congruence): 같은 나머지를 가지는 관계입니다.
• 선형 합동식 (Linear Congruence): $ax \equiv b \pmod n$ 꼴의 합동식입니다.

먼저 실험해 보기: mod 7에서 나눗셈 흉내 내기

mod 7에서 “3으로 나눈다”는 말을 직접 쓰기는 어렵습니다. 대신 어떤 수를 곱했을 때 1이 되는지 찾아봅시다.

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

나머지 1이 나오는 곳은 $x=5$입니다. 그래서 mod 7에서는 3으로 나누는 일을 5를 곱하는 일로 바꿔 생각할 수 있습니다.

이제 용어를 붙여 봅시다. 정수 $a$에 대해, 어떤 정수 $x$가 있어서

$$ax \equiv 1 \pmod n$$

이 되면 $x$를 $a$의 mod $n$에서의 모듈러 역원이라고 합니다.

실수 세계에서 $a^{-1}$를 곱하면 나눗셈을 대신할 수 있듯이, 모듈러 세계에서도 역원이 있으면 나눗셈 비슷한 일을 할 수 있습니다.

또 한 번 역원을 찾으면 mod $n$에서는 같은 나머지를 가진 수들이 같은 역할을 합니다. 예를 들어 mod 7에서 5가 3의 역원이면, 12나 19처럼 5와 합동인 수들도 같은 역원 역할을 합니다.

예시 1. mod 7에서 3의 역원

다음 식을 만족하는 수를 찾습니다.

$$3x \equiv 1 \pmod 7$$

직접 넣어 보면

$$3 \times 5 = 15 \equiv 1 \pmod 7$$

이므로 5는 3의 mod 7에서의 역원입니다.

즉, mod 7에서는 “3으로 나눈다”는 말을 “5를 곱한다”로 바꾸어 이해할 수 있습니다.

언제 역원이 존재할까?

핵심 조건은 다음과 같습니다.

$a$가 mod $n$에서 역원을 가지는 것은 정확히 $\gcd(a,n)=1$일 때입니다.

즉, $a$와 $n$이 서로소여야 합니다.

왜 서로소 조건이 필요할까?

직관부터 보면, $a$와 $n$이 공약수 $d>1$를 가진다면 $ax$는 어떤 $x$에 대해서도 항상 $d$의 배수입니다. 그런데 $ax \equiv 1 \pmod n$이 성립하려면 결국 $ax-1$이 $n$의 배수, 따라서 $d$의 배수여야 합니다. 하지만 $ax$가 $d$의 배수이면 $ax-1$은 $d$의 배수가 될 수 없습니다. 그래서 공약수가 있으면 역원이 존재할 수 없습니다.

만약

$$ax \equiv 1 \pmod n$$

이라면,

$$ax - 1$$

은 $n$의 배수입니다. 즉,

$$ax + ny = 1$$

꼴로 쓸 수 있습니다. 그런데 이런 식이 가능하려면 베주 항등식에 의해 $\gcd(a,n)=1$이어야 합니다.

반대로 $\gcd(a,n)=1$이면 베주 항등식으로

$$ax + ny = 1$$

인 정수해가 존재하므로, mod $n$에서

$$ax \equiv 1 \pmod n$$

가 되어 역원이 존재합니다.

예시 2. 왜 mod 6에서 2는 역원이 없을까?

2와 6의 최대공약수는 2입니다.

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

따라서 서로소가 아닙니다. 실제로 2에 0,1,2,3,4,5를 곱해 보면 나머지는 0,2,4만 반복되고 1은 나오지 않습니다. 그래서 2는 mod 6에서 역원이 없습니다.

역원이 있으면 무엇이 좋아질까?

예를 들어 mod 7에서

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

을 풀고 싶다면, 3의 역원 5를 양변에 곱해서

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

처럼 정리할 수 있습니다.

즉, 역원은 선형 합동식을 푸는 핵심 도구입니다.

실험: 손으로 계산하기

이번에는 “어떤 수를 곱해서 1이 되는가?”를 직접 찾아봅시다. 역원은 처음부터 공식으로 찾기보다 작은 mod에서 곱셈표를 만들어 보면 감각이 빨리 잡힙니다.

실험 1. mod 7에서 3의 역원 찾기

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

나머지 1이 처음 나오는 곳은 $x=5$입니다. 따라서 3의 mod 7 역원은 5입니다.

실험 2. mod 6에서 2의 역원 찾기

$x$	$2x$	mod 6 나머지
0	0	0
1	2	2
2	4	4
3	6	0
4	8	2
5	10	4

나머지가 0, 2, 4만 반복되고 1은 나오지 않습니다. 그래서 2는 mod 6에서 역원이 없습니다.

실험 3. mod 10에서 역원이 있는 수와 없는 수

수 $a$	$\gcd(a,10)$	역원 존재?	이유
3	1	예	$3\times 7=21\equiv 1$
4	2	아니오	곱해도 짝수 나머지만 나옴
7	1	예	$7\times 3=21\equiv 1$
5	5	아니오	곱하면 0 또는 5만 반복

패턴 발견

표를 보면 역원이 있는 수들은 공통적으로 mod와 서로소입니다. 반대로 공약수가 2나 5처럼 남아 있으면, 아무리 곱해도 나머지 1에 도달하지 못합니다.

따라서 발견해야 할 핵심 패턴은 이것입니다. 모듈러 세계에서 나눗셈이 가능하려면, 나누는 수가 법과 서로소여야 합니다. 역원은 단순한 계산 요령이 아니라 “곱셈으로 나눗셈을 대신할 수 있는가?”를 판정하는 도구입니다.

이론 정리

모듈러 역원의 존재 조건

정수 $a$가 mod $n$에서 역원을 가진다는 것은 어떤 정수 $x$에 대해

$$ax\equiv 1\pmod n$$

이 성립한다는 뜻입니다.

이 역원이 존재할 정확히 이럴 때만은

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

입니다.

Python으로 확인하기

아래 코드는 작은 범위에서 직접 곱해 보며 역원을 찾습니다.

from math import gcd


def inverse_by_search(a, n):
    for x in range(n):
        if (a * x) % n == 1:
            return x
    return None

for a, n in [(3, 7), (2, 6), (3, 10), (4, 10), (7, 10), (5, 10)]:
    inv = inverse_by_search(a, n)
    print(f"a={a}, n={n}, gcd={gcd(a, n)}, inverse={inv}")

출력에서 $\gcd(a,n)=1$인 경우에만 역원이 발견되는지 확인해 보세요.

Common mistakes

1. 모든 수가 역원을 가진다고 생각하는 실수

실수와 달리 모듈러 세계에서는 역원이 없는 수가 많습니다.

2. 서로소 조건을 확인하지 않는 실수

먼저 $\gcd(a,n)=1$인지 봐야 합니다. 이 조건이 핵심입니다.

3. 역원을 찾았는데 대표값을 하나만 정답으로 생각하는 실수

mod $n$에서는 같은 나머지를 가진 수들은 모두 같은 역할을 합니다. 예를 들어 mod 7에서 5와 12는 같은 역원 표현입니다.

Silverman 교재 연결

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

• 6장: 베주 항등식 - $\gcd(a,m)=1$일 때 $ax+my=1$ 꼴로 1을 만들 수 있다는 사실이 역원 계산의 바탕이 됩니다.
• 8장: 합동 - 선형 합동식 $ax \equiv c \pmod m$의 특수한 경우로 $ax \equiv 1 \pmod m$을 보면, 모듈러 역원의 존재 조건을 이해할 수 있습니다.
• 관련 정리/예제: $ax \equiv 1 \pmod m$의 해, 즉 $a$의 법 $m$에 대한 역원은 정확히 $\gcd(a,m)=1$일 때 존재합니다.

연습 문제

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

Wrap-up

이번 글에서는 모듈러 역원이 모듈러 세계의 나눗셈을 가능하게 하는 개념이며, 그 존재 조건이 $\gcd(a,n)=1$, 즉 서로소라는 점을 정리했습니다.

다음 글에서는 이 도구를 사용해 $ax \equiv b \pmod n$ 꼴의 선형 합동식을 실제로 푸는 방법을 보겠습니다.