곱셈 역원이란?
어떤 수의 곱셈 역원은 그 수에 곱했을 때 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\)입니다.
자주 묻는 질문
왜 0에는 역원이 없나요? 어떤 수에 0을 곱하더라도 결과는 항상 0이며, 절대 1이 될 수 없기 때문입니다.
모듈러 역원이 존재하지 않는 경우는 언제인가요? \(\gcd(a, m) \neq 1\)일 때입니다. 예를 들어 4는 공통 약수 4를 공유하므로 mod 8에서 역원이 없습니다.
모듈러 역원에 음수를 사용할 수 있나요? 네, 가능합니다. 음수는 먼저 0부터 \(m-1\) 사이의 범위로 변환된 뒤 역원이 계산됩니다.
