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

지난 글에서 합동은 같은 나머지를 가진다는 관계라는 점을 봤습니다. 이제 중요한 질문은 이것입니다. 합동 관계를 알고 있을 때, 덧셈과 곱셈도 마음 놓고 해도 될까요? 정답은 그렇다는 것입니다. 그리고 그 덕분에 큰 수 계산이 훨씬 쉬워집니다.

What this post covers

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

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

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

모듈러 연산의 기본 생각

예를 들어 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에서 언제 나눌 수 있는가?”를 다룹니다.

Common mistakes

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

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

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

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

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

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

Wrap-up

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

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