정수론 (4) - 합동식에서의 나눗셈

저번에 우리는 합동식의 나눗셈에 대해 살펴보던 중

어떨 때는 합동식의 양변을 나누는 것이 안되고 어떨 때는 된다는 것을 관찰했습니다.

 

아래의 합동식은 안되는 예시이며,

$$
\begin{align}
15 \equiv 27 &\mod 12 \\
5 \equiv 9 &\mod 12
\end{align}
$$
아래는 되는 예시입니다.

$$
\begin{align}
24 &\equiv 66 \mod 7 \\
12 &\equiv 33 \mod 7 \\
8 &\equiv 22 \mod 7 \\
4 &\equiv 11 \mod 7
\end{align}
$$
이제부터 언제 합동식의 양변을 나눌 수 있는지 알아보고자 합니다.

 

항등원과 역원

얘기를 시작하기 전에 두 가지 용어를 알아야 합니다.

먼저 항등원이란, 임의의 원소 $a$ 와 연산 $*$ 에 대해서 $a*e=e*a=a$ 를 만족하는 원소 $e$ 입니다.

말이 어렵게 느껴지지만 실제로는 쉽습니다.

예를 들어 연산 $+$에 대해서 항등원은 $0$ 이고, 연산 $\times$에 대해서 항등원은 $1$입니다.

 

한편 원소 $a$ 의 연산 $*$ 에 대한 역원이란 $a * a^{-1} = a^{-1} * a = e$ 를 만족하는 $a^{-1}$ 을 말합니다.

예를 들어 $4$ 의 $+$ 에 대한 역원은 $-4$ 이며, ($4 + (-4) = 0$ 이므로)

$\times$ 에 대한 역원은 $\frac{1}{4}$ 입니다. ($4 \times \frac{1}{4} = 1$ 이므로)

 

즉, 어떤 수를 $a$ 로 나눈다는 표현은, 어떤 수를 $a$ 의 곱셈에 대한 역원과 곱한다는 표현과 동일합니다.

그런데 만약 $a$ 의 곱셈에 대한 역원이 존재하지 않는다면 어떻게 될까요?

그럼 그 상황에서 나눗셈은 정의할 수 없게 되는 것입니다.

 

예를 들어 $a=0$일 때 $a$의 곱셈에 대한 역원이 존재하지 않으며,

때문에 $0$으로 나누기를 정의하지 않습니다.

합동식에서는 이런 상황이 훨씬 자주 발생합니다.

 

합동식에서 곱셈의 역원

먼저 합동식에서 역원이 존재하는 예시를 보겠습니다.

법 9에 대해서, 5의 역원을 생각해 보겠습니다.

합동식에서도 마찬가지로 곱셈에 대한 항등원은 1입니다.

즉, 5의 곱셈에 대한 역원 $x$는 다음을 만족시켜야 합니다.

$$
5 \times x \equiv 1 \mod 9
$$
$x = 0, 1, 2, 3, \cdots, 8$ 을 일일이 대입해보면 5의 역원을 찾을 수 있습니다.

(법 9에서 9 이상의 수는 0~8의 수 중 하나와 합동이므로 8까지만 고려하면 됩니다.)

대입해보면 $x=2$ 일 때 식이 성립합니다.

안타깝게도 일일이 대입해보는 것 외에 합동식에서 역원을 찾는 쉬운 방법은 없습니다.

(참고로 여기서 증명하지는 않겠지만 역원의 유일성은 항상 보장되어 있습니다.

때문에 $x=2$ 이후로는 굳이 확인할 필요가 없습니다.)

 

위에서 보았듯 5의 역원은 2입니다. 하지만 6의 역원은 존재하지 않습니다.

$$
6 \times x \equiv 1 \mod 9
$$
이 때는 $x = 0, 1, 2, 3, \cdots, 8$ 일일이 대입해보면 어떤 수도 위 식을 만족하지 않습니다.

따라서 6의 역원은 존재하지 않습니다.

 

즉, 법 9에서 5의 역원은 존재하고 6의 역원은 존재하지 않으므로,

양변을 5로 나누는 것(또는 양변에 2를 곱하는 것)은 가능하지만,

양변을 6으로 나누는 것은 불가능합니다.

 

구체적인 예시로 60과 90의 경우,

$$
\begin{align}
30 &\equiv 120 &\mod 9 \quad\\
6 &\equiv 24 &\mod 9 \quad &\text{(O)}\\
5 &\equiv 20 &\mod 9 \quad &\text{(X)}
\end{align}
$$

 

합동식에서 곱셈의 역원이 존재할 조건

그렇다면 어느 경우에 역원이 존재할까요?

법 $m$ 에 대하여 정수 $a$ 의 역원이 존재한다는 것은, 다음 식을 만족시키는 $a^{-1}$ 이 있다는 것입니다.

$$
a \times a^{-1} \equiv 1 \mod m
$$
혹시 정수론 (2)에서 했던 별 그리기 문제를 기억하시나요?

보시면 위 수식은 별 그리기 문제와 동일합니다!

원 위에 $m$ 개의 점이 찍혀 있을 때, $a$ 칸씩 건너뛰면서 별을 그릴 경우 도달할 수 있는 최소위치는 $\text{gcd}(a, m)$ 이었습니다.

즉, 다음 식이 성립한다는 것이죠.

(합동식에서 부등식의 사용은 권장하지 않습니다만 이해의 편의를 위해 이렇게 쓰겠습니다)

$$
a \times b \geq \text{gcd}(a, m) \mod m
$$
그렇다면 $a$ 가 역원을 가지기 위해서는, $\text{gcd}(a, m) = 1$ 이어야 합니다.

즉, $a$와 $m$이 서로소 는 $a$ 의 법 $m$ 에 대한 역원이 존재할 필요충분조건입니다!

 

결론

이로부터 다음 중요한 정리를 알게 되었습니다.

 

$a$ 와 $m$ 이 서로소인 경우, 법 $m$ 에 대해 $a$ 의 역원이 존재한다.

 

이는 다음 정리와 동치입니다.

 

$a$ 와 $m$ 이 서로소인 경우, 법 $m$ 의 합동식에서 양변을 $a$ 로 나눌 수 있다.

 

이의 따름정리는 아래와 같습니다.

 

$p$ 가 소수일 떄, 법 $p$ 의 합동식에서는 양변을 $p$의 배수가 아닌 임의의 수로 나눌 수 있다.

 

이제 여러분은 나눗셈을 포함한 등식의 성질을 합동식에 적용할 수 있습니다!

다음 글에서는 합동식을 이용하여 본격적으로 정수론의 중요한 정리인 페르마 소정리에 대해서 알아보겠습니다.