지난 글에서 모듈러 세계에서는 덧셈과 곱셈이 잘 작동한다는 점을 봤습니다. 하지만 나눗셈은 더 조심해야 합니다. 예를 들어 실수 세계에서는 2로 나누는 것이 늘 가능하지만, mod 6의 세계에서는 그렇지 않을 수 있습니다. 이 문제를 푸는 핵심 개념이 모듈러 역원입니다.
What this post covers
- 모듈러 역원이 무엇인지 설명합니다.
- 왜 나눗셈 문제가 사실은 역원 문제인지 이해합니다.
- 역원이 존재하는 조건이 서로소와 연결된다는 점을 정리합니다.
- 다음 글의 선형 합동식 풀이로 이어집니다.
이번 글에서 새로 나오는 용어
- 모듈러 역원 (Modular Inverse): 어떤 수와 곱했을 때 mod 에서 1이 되는 수입니다.
- 서로소 (Coprime): 최대공약수가 1인 두 수의 관계입니다.
- 합동 (Congruence): 같은 나머지를 가지는 관계입니다.
- 선형 합동식 (Linear Congruence): 꼴의 합동식입니다.
모듈러 역원이란 무엇인가?
정수 에 대해, 어떤 정수 가 있어서
이 되면 를 의 mod 에서의 모듈러 역원이라고 합니다.
실수 세계에서 를 곱하면 나눗셈을 대신할 수 있듯이, 모듈러 세계에서도 역원이 있으면 나눗셈 비슷한 일을 할 수 있습니다.
또 한 번 역원을 찾으면 그것은 mod 에서 하나의 합동류로 정해집니다. 예를 들어 mod 7에서 5가 3의 역원이면, 12나 19처럼 5와 합동인 수들도 같은 역원 역할을 합니다.
예시 1. mod 7에서 3의 역원
다음 식을 만족하는 수를 찾습니다.
직접 넣어 보면
이므로 5는 3의 mod 7에서의 역원입니다.
즉, mod 7에서는 “3으로 나눈다”는 말을 “5를 곱한다”로 바꾸어 이해할 수 있습니다.
언제 역원이 존재할까?
핵심 조건은 다음과 같습니다.
가 mod 에서 역원을 가질 필요충분조건은 이다.
즉, 와 이 서로소여야 합니다.
왜 서로소 조건이 필요할까?
직관부터 보면, 와 이 공약수 를 가진다면 는 어떤 에 대해서도 항상 의 배수입니다. 그런데 이 성립하려면 결국 이 의 배수, 따라서 의 배수여야 합니다. 하지만 가 의 배수이면 은 의 배수가 될 수 없습니다. 그래서 공약수가 있으면 역원이 존재할 수 없습니다.
만약
이라면,
은 의 배수입니다. 즉,
꼴로 쓸 수 있습니다. 그런데 이런 식이 가능하려면 베주 항등식에 의해 이어야 합니다.
반대로 이면 베주 항등식으로
인 정수해가 존재하므로, mod 에서
가 되어 역원이 존재합니다.
예시 2. 왜 mod 6에서 2는 역원이 없을까?
2와 6의 최대공약수는 2입니다.
따라서 서로소가 아닙니다. 실제로 2에 0,1,2,3,4,5를 곱해 보면 나머지는 0,2,4만 반복되고 1은 나오지 않습니다. 그래서 2는 mod 6에서 역원이 없습니다.
역원이 있으면 무엇이 좋아질까?
예를 들어 mod 7에서
을 풀고 싶다면, 3의 역원 5를 양변에 곱해서
처럼 정리할 수 있습니다.
즉, 역원은 선형 합동식을 푸는 핵심 도구입니다.
Common mistakes
1. 모든 수가 역원을 가진다고 생각하는 실수
실수와 달리 모듈러 세계에서는 역원이 없는 수가 많습니다.
2. 서로소 조건을 확인하지 않는 실수
먼저 인지 봐야 합니다. 이 조건이 핵심입니다.
3. 역원을 찾았는데 대표값을 하나만 정답으로 생각하는 실수
mod 에서는 같은 합동류의 수들은 모두 같은 역할을 합니다. 예를 들어 mod 7에서 5와 12는 같은 역원 표현입니다.
Wrap-up
이번 글에서는 모듈러 역원이 모듈러 세계의 나눗셈을 가능하게 하는 개념이며, 그 존재 조건이 , 즉 서로소라는 점을 정리했습니다.
다음 글에서는 이 도구를 사용해 꼴의 선형 합동식을 실제로 푸는 방법을 보겠습니다.
💬 댓글
이 글에 대한 의견을 남겨주세요