합동의 연산성질(Operations on congruence in the Number Theory)

합동의 대한 기초 개념을 학습하고 나서는 합동 관계에서 덧셈, 뺄셈, 곱셈, 나눗셈을 하는 방법을 익혀야 합니다. 이 개념은 정수론뿐만 아니라 대수학의 군론을 시작할 때 반드시 필요하므로 이번 글의 중요성을 또 한번 강조해도 지나치지 않습니다.

 

---

1. 합동의 기본 연산

 

1) 덧셈과 곱셈의 기본 연산

 

정리($N.T$) 3.6) 두 합동식은 연결해서 양변 각각 덧셈과 곱셈이 가능
$a\equiv b\;(\text{mod}\; n)$ 이고 $c\equiv d\;(\text{mod}\; n)$ 이라고 하자. 그러면 다음이 성립한다.
① $a+c=b+d\;(\text{mod}\; n)$
② $ac=bd\;(\text{mod}\; n)$

따름정리($N.T$) 3.6.1)
$a\equiv b\;(\text{mod}\; n)$ 이면 임의의 $c\in\mathbb{Z}$ 에 대하여 다음이 성립한다. 역은 항상 성립하지 않는다.
① $a+c=b+c\;(\text{mod}\; n)$
② $ac=bc\;(\text{mod}\; n)$

증명) ① 가정에 의하여 $a-b=kn$ 이고 $c-d=mn$ 을 만족하는 $k,m\in\mathbb{Z}$ 가 존재한다. 양변끼리 더하면 $(a-b)+(c-d)=(a+c)-(b+d)=(k+m)n$ 이 성립하고, 따라서 합동의 정의에 의하여 $a+c\equiv b+d \;(\text{mod}\; n)$ 이 성립한다.

② $a-b=kn$ 의 양변에 $c$ 를 곱하고, $c-d=mn$ 의 양변에는 $b$ 를 곱한 뒤 변변끼리 더한다. 그러면 $ac-bc=bc-bd=knc+bmn$ 이 성립한다. 그러므로 $ac-bd=(kc+bm)n$ 이고, 합동의 정의에 의하여 $ac=bd\;(\text{mod}\; n)$ 를 얻는다. $_\blacksquare$


따름정리의 증명) 합동은 동치관계이므로 $c\equiv c\;(\text{mod}\; n)$ 가 성립한다. 위 정리에 $d$ 대신 $c$ 를 대입하면 주어진 결과를 얻는다. $_\blacksquare$

 

 

이 정리의 결과는 매우 중요합니다. 합동방정식을 풀 때 애용될 것입니다. 일단 ①과 같은 경우를 생각하면, $a,b,c$ 는 애초에 정수이기 때문에 결국 $a\equiv b\;(\text{mod}\; n)$ 의 양변에 어떤 정수를 더하거나 빼도 된다는 것을 뜻합니다.

---

예제 1) 벽시계를 보니 현재 시간이 오전 5시이다. 100시간 뒤는 몇 시인가? 모듈로 공식을 사용해서 생각해보라.

 

 

Sol) 나눗셈의 원리와 24시간제만 알아도 쉽게 풀 수 있기는 하다. $100$ 을 $24$ 로 나눈 나머지는 $4$ 이기 때문에 정답은 오전 9시에 해당한다. 그러나 위의 정리를 사용해서 생각해보자. $100=24\cdot + 4$  에서 $100\equiv 4 \;(\text{mod}\; 4 )$ 이다. 오전 5시에서 시작하니 $5\equiv 5 \;(\text{mod}\; 4)$ 라고 식을 세운다. 변변끼리 더하면

 

$$5+100\equiv 4+5 \equiv 9 (\;(\text{mod}\; 4)$$

 

따라서 100시간 뒤는 오전 9시이다. $_\blacksquare$

 

 

정리($N.T$) 3.7) 합동식은 지수 성질을 보존
$a\equiv b\;(\text{mod}\; n)$ 이라고 하자. 그러면 $k\in \mathbb{N}$ 에 대해 $a^k\equiv b^k\;(\text{mod}\; n)$ 가 성립한다.

증명) 수학적 귀납법을 사용한다. $n$ 이라는 문자가 합동의 법(modulo)으로 사용되고 있으니 $m$ 으로 생각한다.
i) (Base step) $m=1$ : 가정에 의해 $a\equiv b \;(\text{mod}\; n)$ 에서 성립한다.
ii) (Induction hypothesis) $m$ 일 때 $a^m\equiv b^m\;(\text{mod}\; n)$ 이 참이라고 하자.
iii) (Inductive step) $m+1$ 일 때 생각하면,
$$a^{m+1}\equiv a\cdot a^m \equiv b\cdot b^m\equiv b^{m+1}\;(\text{mod}\; n)$$ 가 된다. 따라서 수학적 귀납법에 의해 증명이 끝난다. $_\blacksquare$

 

 

 

2) 합동에서 곱 소거

 

여기서 정리($N.T$) 2.6)-② 를 봅시다. 우리는 역이 성립하는 것에 관심이 있습니다. $2\times 6\equiv 2\times 11 \;(\text{mod}\; 5)$ 와 같은 경우 $6\equiv 11\;(\text{mod}\; 5)$ 와 같이 소거가 가능한 경우가 있습니다. 그런데 $2\times 3\equiv 5\times 3\;(\text{mod}\; 9)$ 에서 $3$ 을 소거하면 $2\not\equiv  5\;(\text{mod}\; 9)$ 에 해당합니다.

 

결론부터 미리 스포를 하자면 모듈로 곱 연산에서 '모듈로 값 $n$ 을 유지한 채' 한 수를 소거하는 것은 그 수가 모듈로 $n$ 에 대해 역원을 가질 때만 가능합니다. 이것은 우리가 결국에 합동방정식을 풀어내기 위해 반드시 필요한 개념입니다. 따라서 언제 역원을 갖는지에 대해 탐구가 필요합니다.

 

 

정리($N.T$) 3.8) 합동식의 곱 소거
$ac\equiv bc\;(\text{mod}\; n)$ 이고 $g=\gcd (c,n)$ 이라 하자. 그러면 다음이 성립한다.
$$a\equiv b \;\left( \text{mod}\; \displaystyle\frac{n}{g} \right)$$ 단, 여기서 $\displaystyle \frac{n}{g}\in\mathbb{N}$ 이 되어야만 한다.

따름정리($N.T$) 3.8.1)
$ac\equiv bc \;(\text{mod}\; n)$ 이고 $\gcd (c,n)=1$ 이면, $a\equiv b \;(\text{mod}\; n)$ 이다.

따름정리($N.T$) 3.8.2)
$p$ 가 소수일 때 $ac\equiv bc \;(\text{mod}\; p)$ 이고 $p\not\mid c$ 라 하자. 그러면
$$a\equiv b \;(\text{mod}\; p)$$

증명) $g=\gcd (c,n)$ 이라고 하자. 그러면 $x,y\in\mathbb{Z}$ 가 존재하여 $c=gx, n=gy$ 가 성립한다. 보이고 싶은 것은 $\displaystyle\frac{n}{g}\mid (a-b)$ 에 해당하는데, $y=\displaystyle\frac{n}{g}$ 가 성립하므로 $y\mid (a-b)$ 를 증명하면 된다. 가정에 의하여

$$\begin{align*} ac-bc=kn\;\;&\Longrightarrow \;\;(a-b)c=kn \\\\&\Longrightarrow (a-b)gx=kgy \\\\&\Longrightarrow (a-b)x=ky \\\\&\Longrightarrow y\mid (a-b)x \end{align*}$$
이 성립한다. 남은 것은 $x$ 를 없애는 작업이다. 정리($N.T$) 1.3) 에 의하여 $\gcd (x,y)=\gcd \left( \displaystyle\frac{c}{g} , \displaystyle\frac{n}{g} \right)=1$ 이 성립하고, 유클리드 보조정리에 의하여 $\gcd(x,y)=1$ 이고 $y=(a-b)x$ 가 성립하므로 $y\mid (a-b)$ 이다. 첫번째 따름정리의 증명은 그냥 $g=1$ 일 때에 해당할 뿐이며, 두번째 따름정리는 소수 $p$ 가 $c$ 를 나누지 못한다는 것이 $\gcd(c,p)=1$ 이라는 사실로부터 따라 나온다. $_\blacksquare$

 

---

예제 2) 선형합동식 $3x\equiv 6 \;(\text{mod}\; 12)$ 의 양변을 $3$ 으로 나누는 것은 가능한가?

 

Sol) 선형합동식이 무엇인지는 지금 당장 중요하지 않으며, 답을 찾는 것에 일단 주목해보자. 정리($N.T$) 3.8) 을 사용해주면, 해당 정리에서 $c=3$ 이고 $a=x, b=2$ 인 상황이다. 그러면 $g:=\gcd(3, 12) = 3$ 이므로, $3x$ 와 $6$, 그리고 모듈러 $12$ 를 동시에 $3$ 으로 나누어

 

$$x\equiv 2 \;(\text{mod}\; 4)$$

 

와 같이 만들 수 있다. 따라서 양변을 $3$ 으로 나누는 것은 가능하다. $_\blacksquare$

---

 

정리($N.T$) 3.9) 합동식에서 $0$ 의 소거
$ab\equiv 0 \;(\text{mod}\; n)$ 이고 $\gcd(a,n)=1$ 이라 하자. 그러면 $b\equiv 0 \;(\text{mod}\; n)$ 이 성립한다.

증명) $ab\equiv 0\equiv  a\times 0 \;(\text{mod}\; n)$ 이라고 생각하자. 공통인수 $a$ 와 모듈로 $n$ 의 최대공약수가 $1$ 이므로, 따름정리($N.T$) 3.8.1) 에 의하여 $b\equiv 0 \;(\text{mod}\; n)$ 이 성립한다. $_\blacksquare$

 

 

정리($N.T$) 3.10)
소수 $p$ 에 대해 다음이 성립한다.
① $ab\equiv 0 \;(\text{mod}\; p)\; \Longrightarrow \;a\equiv 0\;(\text{mod}\; p)$ 또는 $b\equiv 0 \;(\text{mod}\; p)$ 이다.
② $x^2\equiv 0 \;(\text{mod}\; p)$ 이면 $p\mid x$ 이다.
③ $a^2\equiv b^2 \;(\text{mod}\; p) \; \Longleftrightarrow \; a\equiv \pm b\;(\text{mod}\; p)$

증명) ① $ab\equiv 0 \;(\text{mod}\; p)$ 에서 $p\mid (ab)$ 이다. 이때 정리($N.T$) 1.8)(= 소수의 기본 정리)을 적용해보면 $p\mid a$ 또는 $p\mid b$ 이기 때문에 $a\equiv 0 \;(\text{mod}\; p)$ 이거나 $b\equiv 0 \;(\text{mod}\; p)$ 가 성립해야 한다.

② $x^2=pk$ 인 $k\in\mathbb{Z}$ 가 존재한다. 그러면 $p\mid x^2=x\cdot x$ 라는 뜻이고, 소수의 기본 성질에 의하여 $p\mid x$ 가 성립한다.

③ 가정에 의하여 $a^2-b^2=mp=(a-b)(a+b)$ 가 되게 하는 $m\in\mathbb{Z}$ 가 존재한다. 이때 유클리드 보조정리에 의하여 $p\mid (a-b)(a+b)$ 이면 $p\mid (a-b)$ 이거나 $p\mid (a+b)$ 가 성립한다. 앞의 경우이면 $a\equiv b \;(\text{mod}\; p)$ 인 것이고, 뒤의 경우이면 $a\equiv -b \;(\text{mod}\; p)$ 인 것이다. $_\blacksquare$

 

 

 

 

 

 

[참고문헌]

Introduction to Number Theory - William W. Adams, Larry Joel Goldstein