곱셈 역원이란?
어떤 수의 곱셈 역원은 그 수에 곱했을 때 1이 되는 값을 말합니다. 일반적인 실수 a의 경우 역원은 단순히 역수 \(1/a\)입니다. 예를 들어 4의 역원은 0.25인데, \(4 \times 0.25 = 1\)이기 때문이죠. 단, 0에는 역원이 없습니다. 어떤 수에 0을 곱해도 1이 될 수 없기 때문입니다.
$$a^{-1} = \frac{1}{\text{Number (a)}}$$
모듈러 역원
모듈러 연산에서 a의 (mod m) 곱셈 역원은 \(a \cdot x \equiv 1 \pmod{m}\)을 만족하는 0부터 \(m-1\) 사이의 정수 x를 의미합니다. 이 개념은 정수론과 암호학(RSA, 해싱, 오류 정정 부호 등)에서 끊임없이 등장합니다. 모듈러 역원은 a와 m이 서로소일 때, 즉 \(\gcd(a, m) = 1\)일 때만 존재합니다. 이 계산기는 확장 유클리드 알고리즘을 사용해 역원을 찾아냅니다.
$$\text{Number (a)} \cdot a^{-1} \equiv 1 \pmod{\text{Modulus (m)}}$$
계산기 사용법
먼저 수 a를 입력하세요. 모듈러스를 0으로 두거나 비워 두면 일반 역수 \(1/a\)가 계산됩니다. 모듈러 역원을 구하려면 1보다 큰 모듈러스 m을 입력하세요. 계산기는 a를 m으로 나눈 나머지로 줄인 뒤 역원을 반환하며, a와 m이 공통 약수를 가지면 역원이 존재하지 않는다고 알려줍니다.
풀이 예제
11을 법으로 하는 3의 역원을 구해 봅시다. \(3x \equiv 1 \pmod{11}\)을 만족하는 x가 필요합니다. \(x = 4\)를 넣어 보면 $$3 \times 4 = 12 = 11 + 1 \equiv 1 \pmod{11}$$이 됩니다. 따라서 모듈러 역원은 4입니다. 한편 역수로 보면 3의 역원은 \(1/3 \approx 0.333333\)입니다.
확장 유클리드 호제법으로 손으로 모듈러 역원 구하기
\(a\)의 법 \(m\)에 대한 모듈러 역원은 \(a \cdot x \equiv 1 \pmod{m}\)을 만족하는 수 \(x\)이다. 이는 \(\gcd(a, m) = 1\)일 때에만 존재한다. 확장 유클리드 호제법으로 이를 구할 수 있다.
- 유클리드 호제법을 실행한다. \((m, a)\)에 대해 나눗셈을 반복하며, 나머지를 \(r\)이라 할 때 쌍 \((m, a)\)를 \((a, r)\)로 바꾸고, 나머지가 0이 될 때까지 계속한다.
- 최대공약수를 확인한다. 0이 아닌 마지막 나머지가 \(\gcd(a, m)\)이다. 이것이 1이 아니면 역원이 존재하지 않으므로 여기서 중단한다.
- 나눗셈 행을 거슬러 대입하여 \(1 = a \cdot x + m \cdot y\) 형태로 쓴다.
- \(x\)를 법 \(m\)에 대해 0부터 \(m-1\) 범위로 줄인다. \(x\)가 음수이면 \(m\)을 더한다.
- 검증한다: \(a \cdot x \bmod m = 1\)인지 확인한다.
예시: 26을 법으로 한 7의 역원.
| 행 | 나눗셈 | 몫 | 나머지 |
|---|---|---|---|
| 1 | 26 = 3·7 + 5 | 3 | 5 |
| 2 | 7 = 1·5 + 2 | 1 | 2 |
| 3 | 5 = 2·2 + 1 | 2 | 1 |
| 4 | 2 = 2·1 + 0 | 2 | 0 |
0이 아닌 마지막 나머지는 1이므로 \(\gcd(7, 26) = 1\)이며 역원이 존재한다.
3행부터 거슬러 대입한다:
$$1 = 5 - 2\cdot 2$$
2행에서 \(2 = 7 - 1\cdot 5\)를 대입한다:
$$1 = 5 - 2(7 - 5) = 3\cdot 5 - 2\cdot 7$$
1행에서 \(5 = 26 - 3\cdot 7\)을 대입한다:
$$1 = 3(26 - 3\cdot 7) - 2\cdot 7 = 3\cdot 26 - 11\cdot 7$$
따라서 \(x = -11\)이다. 줄이면 \(-11 + 26 = \)15이다.
검증: \(7 \cdot 15 = 105 = 4\cdot 26 + 1\)이므로 \(105 \bmod 26 = 1\)이다. ✓
역수와 모듈러 역원 비교: 예시 입력
역수 \(1/a\)는 0이 아닌 모든 실수에 대해 존재한다. 모듈러 역원은 \(a\)와 \(m\)이 서로소일 때에만 존재한다. 두 값은 서로 다른 양이다.
| a | 법 m | 역수 1/a | 모듈러 역원 | 비고 |
|---|---|---|---|---|
| 3 | 11 | 0.3333 | 4 | 3·4 = 12 ≡ 1 (mod 11) |
| 4 | 8 | 0.25 | 없음 | gcd(4, 8) = 4, 1이 아님 |
| 7 | 26 | 0.142857 | 15 | 7·15 = 105 ≡ 1 (mod 26) |
| −3 | 11 | −0.3333 | 7 | −3을 11로 나눈 나머지는 8이고, 8·7 = 56 ≡ 1 (mod 11) |
| 0 | 1보다 큰 임의의 m | 정의되지 않음 | 없음 | 0·x는 항상 0이며 1이 되지 않음 |
역수는 법을 고려하지 않는다. 모듈러 역원은 0부터 \(m-1\) 사이의 정수이며, \(\gcd(a, m) = 1\)일 때에만 존재한다.
자주 묻는 질문
왜 0에는 역원이 없나요? 어떤 수에 0을 곱하더라도 결과는 항상 0이며, 절대 1이 될 수 없기 때문입니다.
모듈러 역원이 존재하지 않는 경우는 언제인가요? \(\gcd(a, m) \neq 1\)일 때입니다. 예를 들어 4는 공통 약수 4를 공유하므로 mod 8에서 역원이 없습니다.
모듈러 역원에 음수를 사용할 수 있나요? 네, 가능합니다. 음수는 먼저 0부터 \(m-1\) 사이의 범위로 변환된 뒤 역원이 계산됩니다.