모듈러 역원 계산기

모듈러 역원 계산기

성장 중 AI Skill PRO

계산 입력

결과

모듈러 역원
4
(a·x) mod m = 1을 만족하는 x
역원 존재 여부 예
gcd(a, m) 1

공식

a·x≡1(modm)⟹x=a−1modm\text{a} \cdot x \equiv 1 \pmod{\text{m}} \quad\Longrightarrow\quad x = \text{a}^{-1} \bmod \text{m}
사용 통계

광고

이 페이지의 오류 신고

모듈러 역원이란?

정수 a의 법 m에 대한 모듈러 곱셈 역원은 \((a \cdot x) \bmod m = 1\)을 만족하는 정수 x를 말합니다. 모듈러 산술에서 '나눗셈'에 해당하는 연산으로, 정수론은 물론 RSA 암호 시스템과 부호 이론의 여러 알고리즘에서 핵심적인 역할을 합니다. 이 계산기는 확장 유클리드 알고리즘을 사용해 x를 구합니다.

$$\text{a} \cdot x \equiv 1 \pmod{\text{m}} \quad\Longrightarrow\quad x = \text{a}^{-1} \bmod \text{m}$$

시계 같은 원형 모듈러스 링을 감싸는 수직선에서 a 곱하기 x가 1에 도달하는 모습
모듈러 역원 x는 곱하면 a를 다시 1로 되돌리며, 모듈러스 m을 한 바퀴 돕니다.

계산기 사용법

숫자 a와 법 m(단, \(m \geq 2\))을 입력하세요. 이 도구는 \(0 \leq x < m\) 범위에서 가장 작은 음이 아닌 역원 x를 알려 주고, 역원이 존재하는지 확인해 주며 \(\gcd(a, m)\) 값도 함께 표시합니다. 만약 \(\gcd(a, m) \neq 1\)이면 역원이 존재하지 않으며, 결과는 "없음"으로 표시됩니다.

공식 풀이

역원은 \(\gcd(a, m) = 1\)일 때, 즉 a와 m이 서로소일 때만 존재합니다. 확장 유클리드 알고리즘은 \(a \cdot x + m \cdot y = \gcd(a, m)\)을 만족하는 정수 x, y를 찾아 줍니다. gcd가 1이면 x를 법 m으로 나눈 나머지가 곧 역원이 됩니다. 이때 결과가 음수이면 m을 더해 양수 값으로 정규화합니다.

광고
gcd와 계수를 생성하는 확장 유클리드 알고리즘 단계의 평면 순서도
확장 유클리드 알고리즘은 gcd(a, m) = 1일 때 역원을 주는 계수를 산출합니다.

예제로 살펴보기

법 11에 대한 3의 역원을 구해 봅시다. \(3x \equiv 1 \pmod{11}\)을 만족하는 x가 필요합니다. 직접 대입해 보면 $$3 \times 4 = 12 = 11 + 1$$이므로 \(12 \bmod 11 = 1\)이 됩니다. 따라서 \(x = 4\)입니다. 확장 유클리드 알고리즘도 동일한 값을 반환하며, \(\gcd(3, 11) = 1\)이므로 역원이 존재함을 확인할 수 있습니다.

단계별 설명: 손으로 푸는 확장 유클리드 알고리즘

법 m에 대한 a의 모듈러 역원은 \(a \cdot x \equiv 1 \pmod{m}\)을 만족하는 수 x입니다. 이는 \(\gcd(a, m) = 1\)일 때만 존재합니다. 확장 유클리드 알고리즘은 세 단계로 이를 구합니다.

  1. 반복 나눗셈. m을 a로 나누고, 이전 제수를 나머지로 나누는 과정을 나머지가 0이 될 때까지 반복합니다. 마지막으로 0이 아닌 나머지가 최대공약수입니다. 이 값이 1이 아니면 역원은 존재하지 않습니다.
  2. 1을 조합으로 표현. 역방향 대입(back-substitution)을 하거나, 과정 중에 계수를 추적하여 \(1 = a \cdot x + m \cdot y\)를 작성합니다. 이것이 베주 항등식입니다.
  3. x 줄이기. \(x \bmod m\)을 구합니다. x가 음수이면 0에서 m − 1 범위에 들어올 때까지 m을 더합니다(필요하면 반복).

풀이 예: a = 7, m = 40.

단계 나눗셈 몫 q 나머지
1 40 = 5·7 + 5 5 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, 40) = 1\)이며 역원이 존재합니다.

역방향 대입:

$$1 = 5 - 2\cdot 2 = 5 - 2(7 - 5) = 3\cdot 5 - 2\cdot 7 = 3(40 - 5\cdot 7) - 2\cdot 7 = 3\cdot 40 - 17\cdot 7$$

따라서 \(7 \cdot (-17) + 40 \cdot 3 = 1\)이며, 이로부터 \(x = -17\)을 얻습니다.

반복 검산 (a의 계수 t): \(t_0 = 0\)(m = 40인 경우)과 \(t_1 = 1\)(a = 7인 경우)에서 시작하여 \(t_{k+1} = t_{k-1} - q_k \, t_k\)를 사용합니다.

나머지 사용한 q t
40 – 0
7 – 1
5 5 0 − 5·1 = −5
2 1 1 − 1·(−5) = 6
1 2 −5 − 2·6 = −17

나머지가 1이 되는 행에서 \(t = -17\)을 얻습니다. 이를 줄이면 \(-17 + 40 = \)23입니다.

검증: \(7 \cdot 23 = 161 = 4 \cdot 40 + 1\)이므로 \(161 \bmod 40 = 1\). ✓

같은 방법은 더 큰 수에도 적용됩니다. a = 17, m = 3120의 경우 x = 2753이 되는데, 이는 \(17 \cdot 2753 = 46801 = 15 \cdot 3120 + 1\)이기 때문입니다. 이 쌍은 RSA의 고전적인 교과서 예제입니다.

입력 예시와 그 역원

아래의 각 역원은 \((a \cdot x) \bmod m = 1\)을 만족합니다. \(\gcd(a, m) > 1\)이면 역원은 존재하지 않습니다.

a m gcd(a, m) 역원 x 검산
3 11 1 4 3·4 = 12 = 1·11 + 1
7 26 1 15 7·15 = 105 = 4·26 + 1
5 12 1 5 5·5 = 25 = 2·12 + 1
10 17 1 12 10·12 = 120 = 7·17 + 1
17 3120 1 2753 17·2753 = 46801 = 15·3120 + 1
4 6 2 없음 4x mod 6은 항상 짝수이므로 1이 될 수 없음
6 9 3 없음 6x mod 9는 항상 3의 배수이므로 1이 될 수 없음

5는 12를 법으로 할 때 자기 자신의 역원이라는 점에 주목하세요. 일반적으로 \(x^2 \equiv 1 \pmod{m}\)은 1 이외의 해를 가질 수 있으므로, 어떤 수들은 자기 역원입니다.

광고

핵심 용어: 서로소, 최대공약수, 합동, 잉여류

  • 법 (m): 시계 눈금처럼 값이 한 바퀴 돌아 감기는 기준이 되는 양의 정수입니다.
  • 합동 (≡): \(a \equiv b \pmod{m}\)은 m이 \(a - b\)를 나눈다는 뜻이며, 따라서 a와 b는 m으로 나눌 때 같은 나머지를 가집니다.
  • GCD (최대공약수): 두 수를 모두 나누는 가장 큰 정수입니다.
  • 서로소 (coprime, relatively prime): 최대공약수가 1인 두 정수입니다. 이것이 모듈러 역원이 존재하기 위한 바로 그 조건입니다.
  • 베주 항등식: 정수 a와 m에 대해 \(a \cdot x + m \cdot y = \gcd(a, m)\)을 만족하는 정수 x와 y가 존재합니다. 최대공약수가 1이면 이 식을 m으로 나눈 나머지로 환원하여 \(a \cdot x \equiv 1\)을 얻으며, 따라서 x가 역원입니다.
  • 잉여류: m으로 나눈 나머지가 같은 모든 정수의 집합입니다. 역원은 잉여류로서 유일하며, 계산기는 0에서 m − 1 사이의 대표값을 보고합니다.
  • 모듈러 곱셈 역원: \(a \cdot x \equiv 1 \pmod{m}\)을 만족하는 잉여 \(x = a^{-1} \bmod m\)입니다.

오일러 정리: \(\gcd(a, m) = 1\)이면 \(a^{\varphi(m)} \equiv 1 \pmod{m}\)이며, 여기서 \(\varphi\)는 오일러 파이 함수입니다. 따라서 역원은 \(a^{\varphi(m)-1} \bmod m\)으로도 계산할 수 있습니다.

페르마의 소정리: m = p가 소수이면 \(\varphi(p) = p - 1\)이므로, p로 나누어떨어지지 않는 모든 a에 대해 \(a^{-1} \equiv a^{p-2} \pmod{p}\)입니다. 예: \(3^{9} = 19683 = 1789 \cdot 11 + 4\)이므로 \(3^{-1} \equiv 4 \pmod{11}\)이며, 위 표와 일치합니다. 거듭제곱 공식은 (\(\varphi\)를 구하기 위해) m의 인수분해가 필요한 반면, 확장 유클리드 알고리즘은 그렇지 않으므로 일반적인 법에 대해서는 보통 더 빠른 방법입니다.

자주 묻는 질문

역원이 존재하지 않는 경우는 언제인가요? a와 m이 1보다 큰 공약수를 가질 때입니다. 예를 들어 법 6에 대한 4(\(\gcd = 2\))는 역원이 없습니다.

m이 반드시 소수여야 하나요? 아닙니다. m은 2 이상의 어떤 정수든 될 수 있으며, 중요한 것은 a와 m이 서로소인지 여부뿐입니다.

답은 어떤 범위로 나오나요? 역원은 0부터 \(m - 1\) 사이의 가장 작은 음이 아닌 나머지로 표시됩니다.

최종 업데이트:

수학 및 통계 인기 계산기

수학 및 통계 계산기 전체 보기