정수론의 합동에서 동치류들의 연산

여태까지 합동에 관한 뼈대가 되는 개념들을 모두 다루었습니다. 이번 글부터는 본격적으로 대수학을 하기 위해 $\mathbb{Z}_n$ 과 $\mathbb{Z}_n^*$ 을 다루는 과정에서 필요한 동치류들의 연산에 대해 정리할 것입니다. 이미 배웠던 내용, 특히 합동의 연산 성질을 바탕으로 약간만 확장하는 것이기 때문에 그리 어렵지 않을 것입니다.

 

 

그러나 결론적으로 보면, 합동식 $ax\equiv b \;(\text{mod}\; n)$ 와 같은 식에서 사실 해는 무수히 많아 동치류들로 적는다는 점을 고려할 때, $\mathbb{Z}$ 를 $\mathbb{Z}_n$ 으로 줄여서 생각하더라도 그러한 합동의 개념 본질이 달라지는 것은 아니기 때문에 사실 합동의 연산 관계들은 자연스럽게 동치류에서도 성립할 것임을 알 수 있습니다. 그리하여 사실 이번 글에서 적는 내용들은 이미 우리가 다 배웠던 합동식에서의 연산, 합동방정식의 해를 다루는 법에 포함된 내용인 셈입니다.

---

1. 합동에서 동치류들의 연산

 

서론에서 언급한 것과 같이, 오늘 다루는 내용은 거의 동어반복에 가까우며 확장성을 의미하는 것임을 매순간 기억하고 읽어야 합니다.

 

1) 기본 덧셈과 곱셈 : 바 연결하기

 

정리($N.T$) 3.13)
법 $n\in\mathbb{N}$ 에 대한 정수집합의 두 원소 $\overline{a},\overline{b}\in\mathbb{Z}_n$ 을 생각하자. 그러면 다음이 성립한다.
① $\overline{a}+\overline{b}=\overline{a+b}$
② $\overline{a}\overline{b}=\overline{ab}$

증명) ① $\overline{a}:=\{ x\in\mathbb{Z}\mid x\equiv a \;(\text{mod}\; n) \}$ 이고 $\overline{b}:=\{ y\in\mathbb{Z}\mid y\equiv b \;(\text{mod}\; n) \}$ 로 정의된다. 그러면 $p,q\in\mathbb{Z}$ 에 대하여 $x=pn+ a$ 이고 $y=pn+b$ 가 된다. 변변끼리 더하게 되면

$$\overline{a}+\overline{b}=\{ x+y\in\mathbb{Z}\mid x\in\overline{a}\;,\;y\in\overline{b} \}\;\;\;\;\;\cdots \;\;\;(1)$$
이라고 볼 수 있다. 그런데 분석해보면 $x+y=(a+b)+(p+q)n$ 의 꼴이기 때문에 이는 결국 $(x+y)\equiv (a+b) \;(\text{mod}\; n)$ 가 되며, 따라서 

$$\overline{a+b}=\left\{ z\in\mathbb{Z}\mid z\equiv (a+b)\;(\text{mod}\; n) \right\}$$
가 된다, 그러면 $(1)$ 에서 $x+y=z$ 이므로 증명이 끝난다.

② 정의에 의하여 $\overline{a}\overline{b}=\left\{  xy\in\mathbb{Z}\mid x\in\overline{a}\;,\;y\in\overline{b}\right\}$ 이다. $xy=(a+pn)(b+qn)=ab+(aq+pb+pqn)n$ 이므로 $xy\equiv ab \;(\text{mod}\; n)$ 이 성립한다. 그러면

$$\overline{ab}=\{ z\in\mathbb{Z} \mid z\equiv ab \;(\text{mod}\; n)\}$$
이므로 $z=xy$ 에서 증명이 끝난다. $_\blacksquare$

 

 

 

2) 동치류에 대해 성립하는 법칙들

 

아래 정리의 증명은 방법을 써두었지만 난이도는 매우 쉬운데 노가다의 느낌이 있습니다. 그래서 전부 다 자세히 증명하진 않았지만 방법을 잘 적어두었으니 참고하시기 바랍니다.

 

 

정의($N.T$) 3-9) 음의 동치류
$\overline{a}$ 가 주어졌다고 하자. 이때 음의 동치류는 $\overline{-a}:=-\overline{a}$ 로 정의한다.

정리($N.T$) 3.14)
법 $n\in\mathbb{N}$ 이 $n\geq 2$ 로 주어지고, 임의의 $a,b,c\in\mathbb{Z}$ 가 주어졌다고 하자. 그러면 $\mathbb{Z}_n$ 의 원소들 동치류 사이에서 다음이 성립한다.
① 덧셈과 곱셈의 교환법칙 : $\overline{a}+\overline{b}=\overline{b}+\overline{a}$ 이고, $\overline{a}\overline{b}=\overline{b}\overline{a}$
② 덧셈과 곱셈의 결합법칙 : $\overline{a}+(\overline{b}+\overline{c})=(\overline{a}+\overline{b})+\overline{c}$ 이고, $\overline{a}(\overline{b}\overline{c})=(\overline{a}\overline{b})\overline{c}$
③ 덧셈과 곱셈에 대한 항등원 : $\overline{a}+\overline{0}=\overline{a}$ 와 $\overline{a}\overline{1}=\overline{a}$
④ 역원 : $\overline{a}+\overline{-a}=\overline{0}$
⑤ 분배법칙 : $\overline{a}(\overline{b}+\overline{c})=\overline{a}\overline{b}+\overline{a}\overline{c}$

증명) 합동의 연산성질과 정수의 성질, 그리고 동치류의 정의를 그대로 사용하면 된다. 첫 두개만 자세히 증명해 보겠다.

① $\overline{a+b}=\left\{ z\in\mathbb{Z}\mid z\equiv (a+b)\;(\text{mod}\; n) \right\}$ 이다. 그런데 정수는 교환법칙이 성립하므로 $z\equiv (a+b) \;(\text{mod}\; n)$ 는 $z\equiv (b+a) \;(\text{mod}\; n)$ 인 것과 필요충분조건이다. 따라서 $\overline{a+b}=\overline{b+a}$ 이다. 비슷하게 $\overline{a}\overline{b}=\left\{  xy\in\mathbb{Z}\mid x\in\overline{a}\;,\;y\in\overline{b}\right\}$ 인데 $xy=yx$ 이므로 $\overline{a}\overline{b}=\overline{b}\overline{a}$ 가 성립한다.

② $\overline{a}+(\overline{b}+\overline{c})=\overline{a}+(\overline{b+c})=\overline{a+(b+c)}$ 이고, 
$(\overline{a}+\overline{b})+\overline{c}=\overline{a+b}+\overline{c}=\overline{(a+b)+c}$ 이다. 그런데 동치류의 정의 부분을 볼 때 정수는 덧셈에 대한 결합법칙이 성립하므로 이 둘은 같다. 정수의 곱셈도 결합법칙이 성립하므로 비슷하게 증명하면 된다.

③ 동치류의 정의와 합동의 연산성질을 사용한다.
④ 동치류의 정의, 합동의 연산성질, 음의 동치류 정의를 사용한다.
⑤ 정리($N.T$) 3.13) 의 두 조건을 모두 사용하고, 정수의 분배법칙을 사용한 다음, 다시 정리($N.T$) 3.13) 의 두 조건을 순서대로 쓴다. $_\blacksquare$

 

 

---

예제 1) $\mathbb{Z}_{35}$ 에서 $\overline{16}x=\overline{9}$ 의 해를 찾을 수 있는가? 즉 $\overline{16}$ 의 역원이 존재하는지 검토하여라.

 

 

Sol) 합동방정식의 해가 존재할 조건은 여기서 $\gcd(16,35)=1$ 임을 확인하는 것이다. 두 수의 최대공약수가 1이므로 이 합동방정식은 유일한 해를 가지며 $\overline{16}^{-1}$ 또한 존재한다. 이를 찾기 위해 유클리드 호제법을 사용해보자.

 

$$35=16\cdot 2+3$$

$$16=3\cdot 5+1$$

$$3=1\cdot 3+0$$

 

따라서 $\gcd(35,16)=\gcd(16,5)=1$ 이며, 역원을 찾기 위해서는 $\overline{16}y\equiv 1 \;(\text{mod}\; 35)$ 를 만족하는 $y$ 를 찾는 것이 관건이다. 따라서 어떤 $m\in\mathbb{Z}$ 에 대하여 $16=35m+1$ 꼴의 식을 만들어야 하므로, 유클리드 호제법의 결과로부터 $1=16-3\cdot 5$ 이고 $3=35-16\cdot 2$ 이므로

 

$$1=16-3\cdot 5 = 16-(35-16\cdot 2)\cdot 5=16\cdot 11-35\cdot 5$$

를 얻고, 정리하면 $16\cdot 11=(35\cdot 5)+1$ 이다. 따라서 $\overline{16}\cdot\overline{11}\equiv \overline{1} \;(\text{mod}\; 35)$ 이므로 $\overline{16}^{-1}=\overline{11}$ 이다.

 

이제 주어진 합동방정식의 해를 찾아보자. 양변에 $\overline{11}$ 을 곱해주면

 

$$x=\overline{11}\cdot \overline{9}=\overline{99}$$

를 얻는다. 따라서 해는 $\overline{99}$ 이지만 이것을 $\mathbb{Z}_{35}$ 의 원소로 생각해야 하기 때문에 숫자의 크기를 $35$ 미만으로 줄여아 한다. 그러면 $99\equiv 29 \;(\text{mod}\; 35)$ 이므로 정확한 답은 $x=\overline{29}\in\mathbb{Z}_{35}$ 라 말할 수 있다. 결론적으로 볼 때, 동치류의 표현을 위해 숫자 위해 바(bar)를 사용했으나 일반 선형합동식에서 해를 찾았던 방법처럼 굳이 바를 사용하지 않는 형태의 식으로 작성해도 문제가 전혀 없다. 왜냐하면 애초에 선형합동식의 해 자체가 동치류 꼴이기 때문이다. 단, 이 문제에서와 같이 만일 $\mathbb{Z}_n$ 에서의 계산이라고 하면 답을 낼 때 해를 $0\leq x < 35$ 가 되도록 숫자를 조정해야한다는 차이는 존재한다. $_\blacksquare$

---

 

여기까지 학습을 완료하면 이미 이해되어야 하는 점이긴 하지만 마지막으로 서술을 해봅시다. $\mathbb{Z}$ 와 $\mathbb{Z}_n$ 의 차이는 무엇인가요?

 

1) $\mathbb{Z}$ 는 정수집합입니다. 이는 무한집합이고, 이것의 원소들은 단순히 정수 즉 숫자입니다.

 

2) $\mathbb{Z}_n$ 은 $n-1$ 개의 동치류로 이루어진 집합입니다. 따라서 유한집합입니다. 이것들의 원소는 동치류이니 결국 집합입니다. 그러면 정수와의 관계는? 바로 임의의 $z\in\mathbb{Z}$ 는, 반드시 어떤 $\overline{a}\in\mathbb{Z}_n$ 에 포함되어 있다는 점입니다.

 

이 둘의 관계는 몫군을 다루게 되면서 조금 더 선명해지게 됩니다. 이제 대수학의 시간으로 다시 돌아가 봅시다.

 

 

 

 

[참고문헌]

Introduction to Abstract Algebra, 4e, W.Keith Nicholson