모듈러 연산 계산기란?
모듈러 연산은 흔히 '시계 산술'이라고 불립니다. 숫자가 정해진 법(法) n에 도달하면 다시 처음으로 돌아가며 순환하기 때문입니다. 이 계산기는 \((a\ op\ b)\bmod n\) 형태의 식을 계산하며, 연산은 덧셈, 뺄셈, 곱셈은 물론 하나의 값 a를 단순히 n으로 나눈 나머지를 구하는 것까지 지원합니다. 결과는 항상 0부터 \(n - 1\) 사이의 최소 음이 아닌 잉여(least non-negative residue)로 반환됩니다.
사용 방법
a 값을 입력하고 연산을 선택한 뒤 b 값을 넣고('나머지만' 선택 시 b는 무시됩니다) 법 n을 지정하세요. 계산기는 먼저 원래 식의 값을 구한 다음, 그 결과를 n으로 나눈 나머지로 변환합니다. 음수 결과는 0…n−1 범위로 자동 변환되므로, −1 mod 12는 −1이 아니라 11을 반환합니다.
공식 풀이
핵심 관계식은 \(r = (a\ op\ b)\bmod n\)입니다. 프로그래밍에서 쓰는 나머지 연산은 음수가 나올 수 있기 때문에, 이 계산기는 유클리드 방식인 다음 식을 사용해 항상 음이 아닌 결과를 보장합니다.
$$r = ((x \bmod n) + n) \bmod n$$
이는 정수론, 암호학, 해싱 분야에서 표준으로 쓰는 수학적 관례와 일치합니다.
예제로 살펴보기
a = 17, 연산은 덧셈, b = 25, n = 12라고 가정해 봅시다. 먼저 \(17 + 25 = 42\)를 계산합니다. 그다음 \(42 \bmod 12\)를 구하면, \(42 = 3 \times 12 + 6\)이므로 나머지는 6입니다. 12시간제 시계에서 17 + 25 '시간'은 결국 6의 위치에 도달합니다.
음수와 곱셈을 포함한 추가 예제
모든 경우에 계산기는 최소 비음수 나머지 \(r\)을 반환합니다. 이는 \(0 \le r < n\)을 만족하고 \(\text{raw} = n\cdot q + r\)을 만족하는 정수 \(q\)가 존재하는 유일한 값입니다. 모듈러스 \(n\)은 양의 정수여야 합니다.
예제 1: 음수 원시 결과가 나오는 뺄셈
\((5 - 23) \bmod 7\)을 계산합니다.
- 원시 결과: \(5 - 23 = -18\).
- 나눗셈: \(-18 = 7 \cdot (-3) + 3\)이므로 몫은 \(-3\), 나머지는 \(3\)입니다. 확인: \(-18 + 21 = 3\).
- 최종 나머지: 3.
예제 2: 곱셈
\((47 \times 19) \bmod 10\)을 계산합니다.
- 원시 결과: \(47 \times 19 = 893\).
- 나눗셈: \(893 = 10 \cdot 89 + 3\)이므로 몫은 \(89\), 나머지는 \(3\)입니다.
- 최종 나머지: 3. (간단한 방법: mod 10에서는 마지막 자리만 중요하며, \(7 \times 9 = 63\)은 3으로 끝납니다.)
예제 3: 음수에 대한 단순 나머지 연산
\(-29 \bmod 6\)을 계산합니다.
- 원시 값: \(-29\) (단순 나머지 연산에는 두 번째 피연산자가 필요하지 않습니다).
- 나눗셈: \(-29 = 6 \cdot (-5) + 1\)이므로 몫은 \(-5\), 나머지는 \(1\)입니다. 확인: \(-29 + 30 = 1\).
- 최종 나머지: \(1\).
몫은 0을 향해 반올림되는 것이 아니라 내림(음의 무한대 방향)됩니다. 이것이 나머지를 0과 \(n-1\) 사이에 유지하는 방법입니다.
시나리오 비교: 같은 입력, 다른 연산
| a | b | n | 연산 | 원시 결과 | 최종 나머지 |
|---|---|---|---|---|---|
| 17 | 25 | 12 | 덧셈 | 42 = 12·3 + 6 | 6 |
| 17 | 25 | 12 | 뺄셈 | −8 = 12·(−1) + 4 | 4 |
| 17 | 25 | 12 | 곱셈 | 425 = 12·35 + 5 | 5 |
| −7 | 사용 안 함 | 5 | 단순 나머지 연산 | −7 = 5·(−2) + 3 | 3 |
| 17 | 25 | 1 | 곱셈 | 425 = 1·425 + 0 | 0 |
\(n = 1\)이면 모든 정수는 0과 합동이므로 결과는 항상 0입니다.
참고: 유클리드(최소 비음수) 나머지는 일부 프로그래밍 언어가 반환하는 부호 있는 나머지와 다를 수 있습니다. C, C++, Java, JavaScript에서 % 연산자는 0을 향해 절사하므로 -7 % 5는 \(-2\)를 반환하지만, 이 계산기는 \(3\)을 반환합니다. 양의 모듈러스를 사용하는 Python의 %는 유클리드 결과와 일치하는 \(3\)을 반환합니다. 부호 있는 나머지가 음수일 때 두 값은 정확히 \(n\)만큼 차이가 납니다.
자주 묻는 질문
'mod'는 무슨 뜻인가요? 나눗셈을 한 뒤의 나머지를 의미합니다. \(13 = 2 \times 5 + 3\)이므로 \(13 \bmod 5 = 3\)입니다.
음수가 왜 양수로 바뀌나요? 이 계산기는 최소 음이 아닌 잉여를 반환하기 때문입니다. 예를 들어 \(-7 \bmod 5 = 3\)인데, 5를 두 번 더하면(\(-7 + 10 = 3\)) 0…4 범위 안으로 들어오기 때문입니다.
n = 1이면 어떻게 되나요? 모든 정수는 1을 법으로 할 때 0과 합동이므로, 결과는 언제나 0입니다.