[정수론 입문 시리즈 12편] 모듈러 연산에서는 왜 큰 수를 작게 바꿔도 될까?

Python에서 왜 다음 코드가 항상 같은 결과를 낼까요?

(a * b) % n == ((a % n) * (b % n)) % n

지난 글에서 합동은 같은 나머지를 가진다는 관계라는 점을 봤습니다. 이제 그 관계가 덧셈과 곱셈에서도 안전하게 유지되는지 확인해 보겠습니다.

What this post covers

• 모듈러 연산의 기본 생각을 설명합니다.
• 합동에서 덧셈, 뺄셈, 곱셈이 왜 보존되는지 이해합니다.
• 거듭제곱 계산을 나머지로 줄이는 감각을 익힙니다.
• 다음 글의 모듈러 역원으로 이어집니다.

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

• 모듈러 연산 (Modular Arithmetic): 나머지를 기준으로 계산하는 방식입니다.
• 합동 (Congruence): 같은 나머지를 가지는 정수들의 관계입니다.
• 모듈러 역원 (Modular Inverse): 모듈러 세계에서 곱해서 1이 되는 수입니다.
• 나머지 (Remainder): 나눗셈에서 남는 부분입니다.

실험: 손으로 계산하기

먼저 이론을 더 외우기 전에 작은 계산을 직접 해 봅시다. 핵심은 “큰 수를 먼저 작게 줄여도 같은 나머지가 나오는가?”입니다.

실험 1. mod 7에서 덧셈 줄이기

계산	먼저 나머지로 줄이기	결과
$29+15$	$1+1$	$2 \pmod 7$
$34+26$	$6+5=11$	$4 \pmod 7$
$50-18$	$1-4=-3$	$4 \pmod 7$

직접 원래 계산을 해도 $44,60,32$의 mod 7 나머지는 각각 $2,4,4$입니다.

실험 2. mod 6에서 곱셈 줄이기

$$14\times 11 \equiv 2\times 5 = 10 \equiv 4 \pmod 6$$

이번에는 하나 더 해 봅시다.

$$25\times 19 \equiv 1\times 1 \equiv 1 \pmod 6$$

실제로 $25\times 19=475$이고, 475를 6으로 나누면 나머지는 1입니다.

실험 3. mod 5에서 거듭제곱 줄이기

거듭제곱	나머지
$3^1$	3
$3^2=9$	4
$3^3\equiv 4\times 3=12$	2
$3^4\equiv 2\times 3=6$	1

큰 수를 한 번에 계산하지 않고, 매 단계에서 나머지로 줄이면 손으로도 충분히 따라갈 수 있습니다.

패턴 발견

위 실험에서 어떤 공통점이 보이나요?

• 덧셈에서는 각 항을 먼저 나머지로 바꿔도 최종 나머지가 같습니다.
• 곱셈에서도 각 항을 먼저 나머지로 바꿔도 최종 나머지가 같습니다.
• 거듭제곱은 “곱셈을 반복하는 것”이므로, 매번 작게 줄이면 큰 지수도 다룰 수 있습니다.

즉, 모듈러 연산의 핵심 패턴은 다음입니다. 계산하기 전에 줄여도 되고, 계산한 뒤에 줄여도 같은 나머지에 도착합니다. 이 감각이 이후 역원, 선형 합동식, 페르마 소정리의 계산을 모두 떠받칩니다.

모듈러 연산의 기본 생각

예를 들어 mod 5의 세계에서는

$$12 \equiv 2 \pmod 5$$

이고

$$17 \equiv 2 \pmod 5$$

입니다. 즉, 12나 17 같은 큰 수를 2라는 더 작은 대표값으로 바꾸어 생각할 수 있습니다.

이렇게 바꿔도 계산 결과의 나머지는 유지됩니다.

덧셈과 곱셈은 왜 안전할까?

만약

$$a \equiv b \pmod n, \qquad c \equiv d \pmod n$$

라면 다음이 성립합니다.

$$a+c \equiv b+d \pmod n$$ $$ac \equiv bd \pmod n$$

즉, 같은 나머지를 가지는 수끼리 바꾸어도 덧셈과 곱셈의 결과는 mod $n$에서 그대로 유지됩니다.

이유는 $a-b$와 $c-d$가 모두 $n$의 배수이면, 합의 차 $(a+c)-(b+d)$도 $n$의 배수이고, 곱의 차 $ac-bd$도 정리하면 결국 $n$의 배수로 쓸 수 있기 때문입니다.

뺄셈도 같은 방식으로 다룰 수 있습니다. 즉,

$$a-c \equiv b-d \pmod n$$

도 성립합니다.

예시 1. 덧셈

다음 값을 mod 7에서 계산해 봅시다.

$$29 + 15$$

먼저 줄이면

$$29 \equiv 1 \pmod 7, \qquad 15 \equiv 1 \pmod 7$$

이므로

$$29 + 15 \equiv 1 + 1 \equiv 2 \pmod 7$$

입니다.

실제로 44를 7로 나누면 나머지는 2입니다.

같은 생각으로

$$29 - 15 \equiv 1 - 1 \equiv 0 \pmod 7$$

처럼 뺄셈도 줄여서 계산할 수 있습니다.

예시 2. 곱셈

다음 값을 mod 6에서 계산해 봅시다.

$$14 \times 11$$

먼저

$$14 \equiv 2 \pmod 6, \qquad 11 \equiv 5 \pmod 6$$

이므로

$$14 \times 11 \equiv 2 \times 5 = 10 \equiv 4 \pmod 6$$

입니다.

거듭제곱은 왜 특히 중요할까?

모듈러 연산이 강력한 이유는 큰 거듭제곱도 계속 줄여 가며 계산할 수 있기 때문입니다.

예를 들어 mod 5에서

$$3^4 = 81$$

를 직접 계산해도 되지만,

$$3^2 = 9 \equiv 4 \pmod 5$$

이므로

$$3^4 = (3^2)^2 \equiv 4^2 = 16 \equiv 1 \pmod 5$$

처럼 줄여서 생각할 수 있습니다.

이런 계산은 이후 페르마 소정리와 암호학에서 매우 중요합니다.

모듈러 세계에서 “나눗셈”은 왜 조심해야 할까?

덧셈과 곱셈은 비교적 안전하게 다룰 수 있지만, 나눗셈은 그렇지 않습니다. 어떤 수는 모듈러 세계에서 나눌 수 있고, 어떤 수는 나눌 수 없습니다. 그 차이를 이해하려면 모듈러 역원이 필요합니다.

그래서 다음 글에서는 “mod에서 언제 나눌 수 있는가?”를 다룹니다.

이론 정리

모듈러 연산의 보존 법칙

$a\equiv b \pmod n$, $c\equiv d \pmod n$이면

$$a+c\equiv b+d\pmod n$$ $$a-c\equiv b-d\pmod n$$ $$ac\equiv bd\pmod n$$

따라서 거듭제곱도 각 단계에서 나머지로 줄이며 계산할 수 있습니다.

Python으로 확인하기

손계산한 내용을 Python으로 확인해 봅시다. 핵심은 % 연산자가 나머지를 계산한다는 점입니다.

examples = [
    (29 + 15, 7),
    (34 + 26, 7),
    (50 - 18, 7),
    (14 * 11, 6),
    (25 * 19, 6),
]

for value, mod in examples:
    print(value, "mod", mod, "=", value % mod)

# 3의 거듭제곱을 mod 5에서 단계별로 확인하기
x = 1
for k in range(1, 5):
    x = (x * 3) % 5
    print(f"3^{k} mod 5 = {x}")

출력값이 손으로 만든 표와 일치하는지 확인해 보세요.

Common mistakes

1. 큰 수를 줄인 뒤 mod를 잊어버리는 실수

중간 계산에서 나머지로 줄여도 최종 결론은 항상 mod $n$ 기준으로 읽어야 합니다.

2. 덧셈과 곱셈이 되니까 나눗셈도 항상 된다고 생각하는 실수

모듈러에서 나눗셈은 별도의 조건이 필요합니다. 다음 글의 핵심이 바로 그 부분입니다.

3. 대표값이 하나뿐이라고 생각하는 실수

mod 5에서 2와 7과 12는 모두 같은 부류입니다. 대표값은 편의를 위한 선택일 뿐입니다.

Silverman 교재 연결

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

• 8장: 합동 - $a \equiv b \pmod m$라는 합동 표기와 법 $m$에 대한 나머지 계산의 기본 성질을 다룹니다.
• 관련 정리/예제: 같은 나머지를 가진 수의 대표값을 바꾸어도 덧셈, 뺄셈, 곱셈, 거듭제곱 계산이 같은 나머지로 이어진다는 사실을 손계산으로 확인하는 부분과 연결됩니다.

연습 문제

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

Wrap-up

이번 글에서는 모듈러 연산에서 큰 수를 작은 나머지로 바꾸어도 덧셈, 곱셈, 거듭제곱 계산을 안전하게 이어 갈 수 있다는 점을 정리했습니다.

다음 글에서는 이 흐름을 바탕으로, 모듈러 세계에서 언제 “나눗셈”이 가능한지 모듈러 역원으로 이어가겠습니다.