#모듈러 연산

정수론을 다룰 때 우리는 나머지를 가지고 작업하게 됩니다.

식 $a \equiv b \pmod m$은 $a$를 $m$으로 나눈 나머지와 $b$를 $m$으로 나눈 나머지가 같다는 것을 의미합니다. 이 식은 “$a$는 $m$을 법으로 하여 $b$와 합동이다"라고 읽습니다.

다음과 같이 정의할 수도 있습니다. $(a - b)$가 $m$으로 나누어떨어지면 $a$는 $m$을 법으로 $b$와 합동입니다.

모든 정수는 동치류로 나눌 수 있습니다. 두 수가 $m$을 법으로 합동이면 같은 동치류에 속합니다. 이를 두고 우리가 「$m$을 법으로 하는 나머지 환」에서 작업한다고 말하며, 이 환에는 정확히 $m$개의 원소 $0, 1, 2, \cdots, m-1$이 있습니다.

모듈러 덧셈, 뺄셈, 곱셈은 꽤 직관적으로 정의됩니다. 해당 연산을 수행한 뒤 나눗셈의 나머지를 취하면 됩니다.

몇 가지 성질:

1. $a \equiv b$, $c \equiv d \Rightarrow a \pm c \equiv b \pm d \mod m$
2. $a \equiv b$, $c \equiv d \Rightarrow ac \equiv bd \mod m$
3. $a\equiv b \mod m \Rightarrow a^n \equiv b^n \mod m$

모듈러 나눗셈

모듈로 $m$에 대한 잉여류 환에서 한 수 $a$를 다른 수 $b$로 나눈다는 것은 $cb \equiv a \mod m$을 만족하는 수 $c$를 찾는다는 뜻입니다. 이 문제는 모듈로 덧셈이나 곱셈보다 더 어렵습니다. 이 문제는 수 $b$에 대한 이른바 모듈로 역원을 찾는 문제로 귀결됩니다.

법 $m$에 대한 수 $a$의 역원이란 $a\cdot a^{-1} \equiv 1 \mod m$을 만족하는 수 $a^{-1}$를 말합니다.

모듈러가 소수인 경우, 원래 수가 모듈러 $m$으로 나누어떨어지지 않기만 하면 모듈러 역원을 항상 찾을 수 있습니다. 반면 모듈러가 합성수라면, $a$의 모듈러 역원은 $(a, m) = 1$일 때만, 즉 $a$와 $m$이 서로소일 때만 존재합니다.

{{ Утверждение |Название=모듈러 역원의 존재 |Показать название=0 |Утверждение=모듈러 역원은 모듈러와 서로소인 수에 대해서만 존재합니다 |Доказательство= 먼저 $m$과 서로소인 수에 대해서는 모듈러 역원이 항상 존재함을 보이겠습니다. 우리는 $m$을 법으로 하는 나머지만 다루므로, 수와 그 나머지를 같은 대상으로 간주하겠습니다.

수 $0\cdot a, 1\cdot a, … , (m-1)\cdot a$를 살펴봅시다. 이들이 $m$을 법으로 하는 서로 다른 나머지임을 보이겠습니다. 같은 것이 두 개 있고, 그것이 $xa$와 $ya$라고 가정합시다. 그러면 $a(x - y) \equiv 0 \mod m$입니다. 그런데 $(a, m) = 1$이므로 $x - y \equiv 0 \mod m$입니다. 그런데 두 수 $x, y$는 모두 구간 $[0, m-1]$에 속합니다. 두 수의 차가 0과 합동이므로 두 수는 같은 수일 수밖에 없습니다. 그렇지 않으면 그 차는 구간 $[1, m-1]$에 속하게 됩니다. 따라서 모든 나머지는 서로 다릅니다. 나머지가 $m-1$개이므로 반드시 나머지 $1$이 나타납니다. 즉, $ka \equiv 1 \mod m$을 만족하는 수가 존재하며, 이것이 $m$을 법으로 하는 수 $a$의 역원입니다.

이제 $m$과 서로소가 아닌 수에 대해서는 역원이 존재하지 않음을 보이겠습니다. $(a, m) = b > 1$이라고 합시다. 그러면 역원이 존재한다면 $aa^{-1} \equiv 1 \mod m$입니다.

$a = bt, \ m = bp$

$bta^{-1}-1=bp \Rightarrow b\left(ta^{-1} - p\right) = 1 \Rightarrow b \mid 1$이므로 모순입니다.

따라서 모듈러 역원은 모듈러 $m$과 서로소인 원소에 대해서만, 그리고 그러한 원소에 대해서는 반드시 존재합니다. }}

$b$의 역원을 찾았다면, $ab^{-1} \equiv bcb^{-1} \equiv c \mod m$입니다. 즉, $a$에 $b$의 역원을 곱함으로써 나눗셈을 수행하여 구하려던 $c$를 찾은 것입니다.

모듈러 역원을 구하는 방법은 별도의 글을 참고하십시오. Категория:Конспект Категория:Конспект