위키득계정 ↗
과학

모듈러 역원

모듈러 역원과학
영문명
Modular multiplicative inverse
정의 식
ax≡1 (mod m)
존재 조건
gcd(a,m)=1
유일성
법 m에서 같은 나머지로 유일
법 m에서 정수 a의 모듈러 역원은 ax≡1 (mod m)을 만족하는 정수 x다. m>1일 때 역원이 존재하는 필요충분조건은 a와 m이 서로소인 것이다.

곱해서 나머지 1 만들기

법 7에서 3에 5를 곱하면 15이고 나머지는 1이다. 따라서 5는 3의 모듈러 역원이다. 이는 실수에서의 역수 1/3을 그대로 나머지로 바꾼다는 뜻이 아니라 정수의 곱에 관한 합동 관계다.

존재하지 않는 경우

법 9에서 3의 역원은 없다. 3에 어떤 정수를 곱해도 3의 배수이므로 9로 나눈 나머지가 1일 수 없기 때문이다. 법과 공약수가 있다는 점이 역원의 존재를 막는다.

대표값의 선택

법 7에서 5와 12는 같은 나머지를 가지며 둘 다 3과 곱하면 1에 합동이다. 역원이 유일하다는 말은 정수값이 하나뿐이라는 뜻이 아니라 합동류가 하나라는 뜻이다. 보통 0 이상 7 미만의 대표값 5를 택한다.

일차 합동식에 사용

3x≡4 (mod 7)의 양쪽에 3의 역원 5를 곱하면 x≡20≡6 (mod 7)을 얻는다. 법과 서로소인 계수에서는 이렇게 역원으로 소거할 수 있다. 역원이 없는 계수를 같은 방식으로 나눌 수는 없다.

관련 문서

합동식 / 정수 / 나머지 / 서로소 / 최대공약수 / 필요충분조건 / 역수 / 동치류 / 유클리드 호제법