모듈러 역원 구하기
모듈러 역원은 특정 법에서 곱셈을 되돌립니다. 곱셈 역원만 다루며 RSA 키 생성·소인수분해는 하지 않습니다.
사용 방법
- 음수를 포함한 정수 a를 입력하세요.
- 1보다 큰 양의 법 m을 입력하세요.
- 계산하면 존재하는 경우 0~m−1의 유일한 대표값 x를 구합니다.
- 베주 식과 실제 곱의 나머지로 답을 독립적으로 확인하세요.
조건과 공식
gcd(a, m) = 1일 때만 역원이 있습니다. 확장 유클리드 알고리즘은 a·u + m·v = 1의 u·v를 찾고 u mod m이 역원이 됩니다.
음수 a는 ((a mod m) + m) mod m으로 정규화합니다. 답은 항상 최소 비음수 대표값입니다.
풀이 예시
법 11에서 3
gcd(3, 11) = 1, 3 × 4 = 12이며 12 mod 11 = 1이므로 역원은 4입니다.
법 11에서 −3
−3은 8로 정규화합니다. 8 × 7 = 56, 56 mod 11 = 1이므로 역원은 7입니다.
법 9에서 6
gcd(6, 9) = 3이므로 6에 어떤 정수를 곱해도 법 9에서 나머지 1을 만들 수 없습니다.
입력 제한과 범위
- 브라우저 응답성을 위해 각 입력은 10진 200자리까지입니다. 앞자리 0도 입력 길이에 포함합니다.
- 10진 정수만 허용합니다. 소수, 과학적 표기, 내부 공백, 단위, Infinity는 거부합니다.
- 법 0·1·음수는 유효하지 않습니다. a = 0은 허용하지만 m > 1에서 역원이 없습니다.
- 결과는 소수 근사가 아닌 정확한 정수입니다. 산술 보조 도구이며 암호 키 생성기·보안 서비스는 아닙니다.
자주 묻는 질문
최대공약수가 왜 1이어야 하나요?
a·m에 1보다 큰 공약수가 있으면 모든 a×x에도 그 인수가 있어 법 m에서 1과 합동일 수 없습니다.
음수도 역원이 있나요?
네. 최소 비음수 나머지로 줄인 뒤 같은 서로소 검사를 합니다.
답을 하나만 표시하는 이유는 무엇인가요?
모든 역원의 차이는 m의 배수입니다. 0~m−1 범위의 유일한 값을 표시합니다.
1/a와 같은가요?
아니요. 모듈러 역원은 선택한 법에서 곱의 나머지가 1이 되는 정수입니다.