합동식 (모듈러 연산)에 대한 이해와 고찰 (정의, 기본성질)

1. Introduction

여러분은 합동식 (Congruence)에 대해 알고 있는가? 아마 이과라도 정규 교육과정만 배웠다면 합동식에 대해 들어본 적 없을 수 있다. 컴공정도는 되어야 익숙하게 설명할 수 있을 듯한 이 합동식은 사실 정수론의 핵심적인 이론이다.

합동식의 정의는 다음과 같다.

"정수 $a,b,m$에 대하여, $m∣(a−b)$일 때, $a$는 법 $m$에 대하여 $b$와 합동이다."

이때, 기호로는 $$a\equiv b\left(\text{mod}\,m\right)$$라고 쓴다. $m$를 합동의 법(modular)이라고 한다.

이해하기 어려운가? 간단하게 말해서,

"$a$를 $m$으로 나눈 나머지와 $b$를 $m$으로 나눈 나머지는 같다."

라는 것과 같은 말이다. 컴공에서는 합동식이 결국 나머지를 요하는 식이다 보니 합동식이라고 부르기보다는 합동의 법이랑 같이 깡그리 모듈러 연산이라고 부른다. 이후로는 편의상 "모듈러"라고 부르도록 하겠다.

---

2. Properties

모듈러는 다음과 같은 성질을 가지고 있다.

2.1 반사성 (Reflexivity)

$a\equiv a\left(\text{mod}\,m\right)$

직관적으로 당연히, $a$를 나눈 나머지와 $a$를 나눈 나머지는 같겠지만 굳이 증명하자면,

$a-a=0$고, $m⋅0=0$이므로 $m∣0$이다. 따라서, $a\equiv a\left(\text{mod}\,m\right)$이다. 

---

2.2 대칭성 (Symmetry)

$a\equiv b\left(\text{mod}\,m\right)$이면, $b\equiv a\left(\text{mod}\,m\right)$. 즉 교환법칙이다.

이 부분도, 직관적으로 느껴지겠지만 굳이 증명하면,

$a\equiv b\left(\text{mod}\,m\right)$ 이므로, $m\mid\left(a-b\right)$이고, $m | n$이면, $m\mid\left(-n\right)$ 역시 성립하기 때문에 $m\mid\left(b-a\right)$이고, $b\equiv a\left(\text{mod}\,m\right)$

---

2.3 추이성 (Transtivity) 

$a\equiv b\left(\text{mod}\,m\right), b\equiv c\left(\text{mod}\,m\right)$이면, $a\equiv c\left(\text{mod}\,m\right)$이다.

역시 직관적으로 이해되는 부분.

$a\equiv b\left(\text{mod}\,m\right)$에서, $m\mid\left(a-b\right)$.

$b\equiv c\left(\text{mod}\,m\right)$에서, $m\mid\left(b-c\right)$.

$m\mid{\left(a-b\right)+\left(b-c\right)}$ 이므로, $m\mid\left(a-c\right)$ 이고 $a\equiv c\left(\text{mod}\,m\right)$.

---

2.4 정수합 (Compatibility with translation)

$a\equiv b\left(\text{mod}\,m\right)$이면, $a+k\equiv b+k\left(\text{mod}\,m\right)$이다.

역시 직관적.

$a\equiv b\left(\text{mod}\,m\right)$에서, $m\mid\left(a-b\right)$.

$m\mid\left((a+k)-(b+k)\right)$이므로, $a+k\equiv b+k\left(\text{mod}\,m\right)$

---

2.4.1 합동식의 합차 (Compatibility with addition and subtraction)

$a\equiv b\left(\text{mod}\,m\right), c\equiv d\left(\text{mod}\,m\right)$이면, $a\pm c\equiv b\pm d\left(\text{mod}\,m\right)$이다.

$a\equiv b\left(\text{mod}\,m\right)$에서, $m\mid\left(a-b\right)$.

$c\equiv d\left(\text{mod}\,m\right)$에서, $m\mid\left(c-d\right)$.

$m\mid{\left(a-b\right)\pm\left(c-d\right)}$이므로, $m\mid{\left(a\pm c\right)-\left(b\pm d\right)}$이고,

$a\pm c\equiv b\pm d\left(\text{mod}\,m\right)$

---

2.5 정수배 (Compatibility with scaling)

$a\equiv b\left(\text{mod}\,m\right)$이면, $ka\equiv kb\left(\text{mod}\,m\right)$이다.

여기까지 보면 알겠지만 사실상 모듈러 연산 성질로 될만한 것들은 다 합동식에서도 다 통한다.

$a\equiv b\left(\text{mod}\,m\right)$에서, $m\mid\left(a-b\right)$.

$m\mid\left(k(a-b)\right)$이므로, $ka\equiv kb\left(\text{mod}\,m\right)$

---

2.5.1 합동식의 곱 (Compatibility with multiplication)

$a\equiv b\left(\text{mod}\,m\right), c\equiv d\left(\text{mod}\,m\right)$이면, $ac\equiv bd\left(\text{mod}\,m\right)$이다.

$a\equiv b\left(\text{mod}\,m\right)$에서, $m\mid\left(a-b\right)$.

$c\equiv d\left(\text{mod}\,m\right)$에서, $m\mid\left(c-d\right)$.

$m\mid{\left(a-b\right)c+\left(c-d\right)b}$ 이므로 $m\mid\left(ac-bd\right)$ 이고, $ac\equiv bd\left(\text{mod}\,m\right)$.

---

2.6 지수배(compatibility with exponentiation)

음수가 아닌 정수 $k$에 대해, $a\equiv b\left(\text{mod}\,m\right)$이면, $a^k\equiv b^k\left(\text{mod}\,m\right)$이다.

$a\equiv b\left(\text{mod}\,m\right)$에서 $m\mid\left(a-b\right)$.

$k\geq2a^k-b^k =\left(a-b\right)\left(a^{k-1} + a^{k-2}b+\cdots +ab^{k-2}+b^{k-1}\right)$

$m\mid\left(a^k-b^k\right)$에서 $a^k\equiv b^k\left(\text{mod}\,m\right)$.

---

2.7 모듈러 축소

$ab\equiv ac\left(\text{mod}\,m\right)$이고, $d=\gcd\left(a,m\right)$이면, $b\equiv c\left(\text{mod}\,\cfrac{m}{d}\right)$이다.

여기서부터 직관적으로 바로 이해되지 않을 수 있다. 실용적으로 보자면, m이 커서 좋을 일은 없을 테니 m의 크기를 줄이는데 쓰인다, 합동식의 피연산자의 gcd를 찾아내서 그 gcd와 m을 다시 gcd한 값만큼 m을 줄일 수 있다는 것.

$ab\equiv ac\left(\text{mod}\,m\right)$이면, $m\mid a\left(b-c\right)$이다.

$d=\gcd\left(a,m\right)$이므로, $a=dx_1,m=dx_2$를 만족하는 정수$x_1,x_2$가 존재한다.

$dx_2\mid dx_1\left(b-c\right)$이다. $x_1, x_2$가 서로소이므로 $x_2\mid\left(b-c\right)$이다.

그런데, $x_2=\cfrac{m}{d}$이므로, $\cfrac{m}{d}\mid\left(b-c\right)$이다.

따라서, $b\equiv c\left(\text{mod}\,\cfrac{m}{d}\right)$이다.

---

2.8 모듈러 약수

$a\equiv b\left(\text{mod}\,m\right)$이고, $n$이 $m$의 약수이면, $a\equiv b\left(\text{mod}\,n\right)이다.$

이해하기 쉬운 편.

$a\equiv b\left(\text{mod}\,m\right)$이면, $m\mid\left(a-b\right)$.

$n\mid mn∣m$이면, $n\mid\left(a-b\right)n∣(a−b)$.

따라서, $a\equiv b\left(\text{mod}\,n\right)$이다.

---

2.9 합동식의 나눗셈 (Compatibility with division)

$a\equiv b\left(\text{mod}\,m\right)$이고, $d>0$인 $d$가 $a,b,m$의 공약수이면, $\cfrac{a}{d}\equiv\cfrac{b}{d}\left(\text{mod}\,\cfrac{m}{d}\right)$이다.

나눗셈은 합, 차, 곱과 달리 조건이 필요하다.

$a\equiv b\left(\text{mod}\,m\right)$이면 $m\mid\left(a-b\right)$.

$d$가 $a,b,m$의 공약수이므로 $a=x_1d,\; b=x_2d,\; m=x_3d$를 만족하는 정수 $x_1,x_2,x_3$가 존재한다.

$dx_3\mid d\left(x_1-x_2\right)$이므로, $x_3\mid\left(x_1-x_2\right)$이다.

$x_1=\cfrac{a}{d},x_2=\cfrac{b}{d},x_3=\cfrac{m}{d}$이므로, $\frac{m}{d}\mid\left(\frac{a}{d}-\frac{b}{d}\right)$이다.

따라서, $\cfrac{a}{d}\equiv\cfrac{b}{d}\left(\text{mod}\,\cfrac{m}{d}\right)$.