합동식

• 상위 항목: 수학 관련 정보, 정수론

1 개요

정수 [math] a,b,m[/math]에 대하여, [math]m\mid\left(a-b\right)[/math]일 때, [math]a[/math]는 법 [math]m[/math]에 대하여 b와 합동이다([math]a[/math] is congruent to [math]b[/math] modulo [math]m[/math])라고 한다. 이 때, 기호로는 [math]a\equiv b\left(\text{mod}\,m\right)[/math]라고 쓴다. [math]m[/math]를 합동의 법(modular)이라고 한다. 간단히 말해서, [math]a[/math]를 [math]m[/math]으로 나눈 나머지는 [math]b[/math]를 수식으로 표현한 것.

일반적으로 나머지는 나누는 수보다 작지만, 합동식에서는 [math]b[/math]값에 제한이 없다는 차이점은 존재한다. 다시말해 [math]a\equiv b\left(\text{mod}\,m\right)[/math]에서 b에 들어갈 수 있는 수 자체는 많이 있고, 그 중에 가장 작은 수가 초등학교 때 배운 '나머지'이다.

나머지라는 개념 자체가 초등학교 시절 분수 배우기 전에 배우던 것이여서 보통 마치 가르치기 어려운 개념을 회피하기 위해 만들어진 것 같아 보인다. 그러나 천만의 말씀. 나머지는 수학에서 가장 신비로운 개념 중 하나로, 덧셈이나 곱셈에만 적용되는 줄 알았던 연산개념이 신기하게도 나머지에서 완전 같은 방법으로 적용된다는 점을 깨닫게 되면 정수론에 대한 관심이 꽃피게 되는 일이 많다.

대학교의 정수론 수업을 듣지 않는한 배울 일이 없지만, KMO를 비롯한 수학 경시대회를 준비한다면 반드시 알아놔야 할 것 중 하나. 이차 잉여까지는 알 필요 없지만 아래 기본적인 성질은 모두 숙지하는 것이 좋다. 사실 경시대회 준비가 아니더라도 고등학교 때 이항정리 문제 중 합동식을 쓰면 편한 문제가 나오므로 알아놔서 절대 나쁠 건 없다.

2 성질

1. (반사율) [math]a\equiv a\left(\text{mod}\,m\right)[/math]이다.
2. (대칭률) [math]a\equiv b\left(\text{mod}\,m\right)[/math]이면 [math]b\equiv a\left(\text{mod}\,m\right)[/math]이다.
3. (추이율) [math]a\equiv b\left(\text{mod}\,m\right), b\equiv c\left(\text{mod}\,m\right)[/math]이면 [math]a\equiv c\left(\text{mod}\,m\right)[/math]이다.
4. [math]a\equiv b\left(\text{mod}\,m\right), c\equiv d\left(\text{mod}\,m\right)[/math]이면, [math]a\pm c\equiv b\pm d\left(\text{mod}\,m\right)[/math]이다. (복부호동순)
5. [math]a\equiv b\left(\text{mod}\,m\right), c\equiv d\left(\text{mod}\,m\right)[/math]이면, [math]ac\equiv bd\left(\text{mod}\,m\right)[/math]이다.
6. [math]a\equiv b\left(\text{mod}\,m\right)[/math]이면, [math]a^k\equiv b^k\left(\text{mod}\,m\right)[/math]이다.
7. [math]ab\equiv ac\left(\text{mod}\,m\right)[/math]이고, [math]d=\gcd\left(a,m\right)[/math]이면, [math]b\equiv c\left(\text{mod}\,\frac{m}{d}\right)[/math]이다.
8. [math]a\equiv b\left(\text{mod}\,m\right)[/math]이고, [math]n[/math]이 [math]m[/math]의 약수이면, [math]a\equiv b\left(\text{mod}\,n\right)[/math]이다.
9. [math]a\equiv b\left(\text{mod}\,m\right)[/math]이고, [math]d\gt0[/math]이 [math]a,b,m[/math]의 공약수이면, [math]\frac{a}{d}\equiv\frac{b}{d}\left(\text{mod}\,\frac{m}{d}\right)[/math]이다.

3 증명

1. [math]a-a=0[/math]이고, [math]m\cdot0=0[/math]이므로 [math]m\mid0[/math]이다. 따라서, [math]a\equiv a\left(\text{mod}\,m\right)[/math]이다.

2. [math]a\equiv b\left(\text{mod}\,m\right)[/math]이면 [math]m\mid\left(a-b\right)[/math]이다. 또, [math]m\mid\left(a-b\right)[/math]이므로 [math]m\mid\left(b-a\right)[/math]이다. 따라서, [math]b\equiv a\left(\text{mod}\,m\right)[/math]이다.

3. [math]a\equiv b\left(\text{mod}\,m\right)[/math]이면 [math]m\mid\left(a-b\right)[/math]이고, [math]b\equiv c\left(\text{mod}\,m\right)[/math]이면 [math]m\mid\left(b-c\right)[/math]이다. 그러므로 [math]m\mid{\left(a-b\right)+\left(b-c\right)}[/math]이다. 즉, [math]m\mid\left(a-c\right)[/math]이다. 따라서, [math]a\equiv c\left(\text{mod}\,m\right)[/math]이다.

4. [math]a\equiv b\left(\text{mod}\,m\right)[/math]이면 [math]m\mid\left(a-b\right)[/math]이고, [math]c\equiv d\left(\text{mod}\,m\right)[/math]이면 [math]m\mid\left(c-d\right)[/math]이다. 그러므로 [math]m\mid{\left(a-b\right)\pm\left(c-d\right)}[/math]이다. 즉, [math]m\mid{\left(a\pm c\right)-\left(b\pm d\right)}[/math]이다. 따라서, [math]a\pm c\equiv b\pm d\left(\text{mod}\,m\right)[/math]이다.

5. [math]a\equiv b\left(\text{mod}\,m\right)[/math]이면 [math]m\mid\left(a-b\right)[/math]이고, [math]c\equiv d\left(\text{mod}\,m\right)[/math]이면 [math]m\mid\left(c-d\right)[/math]이다. 그러므로 [math]m\mid{\left(a-b\right)c+\left(c-d\right)b}[/math]이다. 즉, [math]m\mid\left(ac-bd\right)[/math]이다. 따라서, [math]ac\equiv bd\left(\text{mod}\,m\right)[/math]이다.

6. [math]a\equiv b\left(\text{mod}\,m\right)[/math]이면 [math]m\mid\left(a-b\right)[/math]이다. 또, [math]k\geq2[/math]일 때, [math]a^k-b^k =\left(a-b\right)\left(a^{k-1} + a^{k-2}b+\cdots +ab^{k-2}+b^{k-1}\right)[/math]
이므로, [math]m\mid\left(a^k-b^k\right)[/math]이다. 따라서, [math]a^k\equiv b^k\left(\text{mod}\,m\right)[/math]이다.

7. [math]ab\equiv ac\left(\text{mod}\,m\right)[/math]이면, [math]m\mid a\left(b-c\right)[/math]이다. [math]d=\gcd\left(a,m\right)[/math]이므로, [math]a=dx_1,m=dx_2[/math]를 만족하는 정수 [math]x_1,x_2[/math]가 존재한다. 또한, [math]dx_2\mid dx_1\left(b-c\right)[/math]이다. 또, [math]x_1[/math]과 [math]x_2[/math]가 서로소이므로 [math]x_2\mid\left(b-c\right)[/math]이다. 그런데, [math]x_2=\frac{m}{d}[/math]이므로, [math]\frac{m}{d}\mid\left(b-c\right)[/math]이다. 따라서, [math]b\equiv c\left(\text{mod}\,\frac{m}{d}\right)[/math]이다.

8. [math]a\equiv b\left(\text{mod}\,m\right)[/math]이면 [math]m\mid\left(a-b\right)[/math]이다. 또 [math]n\mid m[/math]이면, [math]n\mid\left(a-b\right)[/math]이다. 따라서, [math]a\equiv b\left(\text{mod}\,n\right)[/math]이다.

9. [math]a\equiv b\left(\text{mod}\,m\right)[/math]이면 [math]m\mid\left(a-b\right)[/math]이다. 또, [math]d[/math]가 [math]a,b,m[/math]의 공약수이므로 [math]a=dx_1,b=dx_2,m=dx_3[/math]를 만족하는 정수 [math]x_1,x_2,x_3[/math]가 존재한다. 또한, [math]dx_3\mid d\left(x_1-x_2\right)[/math]이다. 그러므로, [math]x_3\mid\left(x_1-x_2\right)[/math]이다. 그런데, [math]x_1=\frac{a}{d},x_2=\frac{b}{d},x_3=\frac{m}{d}[/math]이므로, [math]\frac{m}{d}\mid\left(\frac{a}{d}-\frac{b}{d}\right)[/math]이다. 따라서, [math]\frac{a}{d}\equiv\frac{b}{d}\left(\text{mod}\,\frac{m}{d}\right)[/math]이다.

4 일차합동식

4.1 일차합동식의 정의

일차합동식이란, 일차방정식과 비슷하게 미지수의 차수가 1인 합동식을 의미한다. 수식으로 간단하게 표현하면 [math]ax\equiv b\left(\text{mod}\,m\right)[/math]인 형태인 모든 합동식이 일차합동식이다. 일차방정식에 해가 존재할 조건이 있듯이, 일차합동식에도 해가 존재할 조건이 있다. [math]d=\gcd\left(a,m\right)[/math]라 했을 때, [math]d\nmid b[/math]이면 합동식은 정수해를 갖지 않고, [math]d\mid b[/math]이면 법 [math]m[/math]에 대해 정확히 [math]d[/math]개의 서로 다른 해를 갖게된다. 해의 존재성에대한 증명은 다음과 같다.

 1. [math]d\nmid b[/math]인데 해가 존재한다고 가정하자. 그럼 적당한 정수 [math]y[/math]에 대하여 [math]ax+my=b[/math]가 성립한다. 그런데 [math]d\mid ax+my=d[/math]이므로 [math]d\mid b[/math]이다. 이는 가정에 모순되므로 주어진 합동식의 해는 존재하지 않는다.
 1.[math]ax+my=b[/math]의 한 해를 [math]x_0,y_0[/math]라 하면, 일반해는 [math]x_k=x_0+\frac{mk}{d},y_k=y_0-\frac{ak}{d}[/math]의 꼴이다 (단 [math]k[/math]는 임의의 정수). 여기서 [math]x_k[/math]가 합동식 [math]ax\equiv b\left(\text{mod}\,m\right)[/math]을 만족시키는 모든 해이다. 나눗셈 정리에 의해 [math]k=qd+r,\,\left(0\leq r\ltd\right)[/math]이고, 이를 [math]x_k[/math]에 대입하면, [math]x_k\equiv x_0+\frac{m\left(qd+r\right)}{d}\equiv x_0+\frac{mr}{d}\equiv x_r\left(\text{mod}\,m\right)[/math]이다. 이것은 곧 모든 [math]x_k[/math]가 [math]x_0,x_1,\cdots,x_{d-1}[/math]중 하나와 법 [math]m[/math]에 대해 합동임을 의미한다. 이제 [math]x_i\equiv x_j\left(\text{mod}\,m\right)[/math], ([math]0\leq i,j\leq d-1[/math])라 가정하면, [math]\frac{im}{d}\equiv\frac{jm}{d}\left(\text{mod}\,m\right)[/math]이다. 그런데 [math]\gcd\left(\frac{m}{d},m\right)=\frac{m}{d}[/math]이므로 위 성질 7번에 의해 [math]i\equiv j\left(\text{mod}\,d\right)[/math]이다. 이는 곧 [math]x_0,x_1,\cdots,x_{d-1}[/math]가 법 [math]m[/math]에 대해 서로 합동이 아님을 의미한다.

4.2 일차합동식의 해법

크게 디오판토스 방정식, 유클리드 호제법, 잉여역수를 이용하는 방법으로 나눌 수 있다. 여기서는 다음 예제의 해법을 소개한다.

일차합동식 [math]3x\equiv7\left(\text{mod}\,4\right)[/math]를 풀어라.

4.2.1 디오판토스 방정식 이용

적당한 정수 [math]y[/math]에 대하여 [math]3x+4y=7[/math]이다. 여기서 [math]x_0=1,y_0=1[/math]은 한 해(특이해)임을 쉽게 알 수 있다. [math]\gcd\left(3,4\right)=1[/math]이므로 일반해는 [math]x=1+4t,\quad y=1-3t[/math]이다. 우리가 구하는 것은 [math]x[/math]와 관련된 것이므로 [math]x\equiv1\left(\text{mod}\,4\right)[/math]가 해이다.

4.2.2 유클리드 호제법 이용

[math]\gcd\left(3,4\right)=1[/math]이므로, 적당한 정수 [math]a,b[/math]에 대해 [math]3a+4b=1[/math]이다. 실제로, [math]\left(-1\right)\cdot3+1\cdot4=1[/math]이다. 이 사실은 우리에게 [math]1\cdot x[/math]를 얻기 위하여 [math]x[/math]의 계수를 바꿀 수 있음을 암시한다. 즉,
[math]4x\equiv0\left(\text{mod}\,4\right)\quad\cdots\left(1\right)[/math]
[math]3x\equiv7\left(\text{mod}\,4\right)\quad\cdots\left(2\right)[/math]
에서 (1)-(2)하면 [math]x\equiv1\left(\text{mod}\,4\right)[/math]이다.
여기서 x=-7mod(4) 인데 -7 + 2*4 = 1 이므로 위 식처럼 나타낸다.

4.2.3 잉여역수 이용

법 4에 대한 곱셈표는 아래와 같다.

×	0	1	2	3
0	0	0	0	0
1	0	1	2	3
2	0	2	0	2
3	0	3	2	1

위 표에서 보듯이 [math]3\cdot3\equiv1\left(\text{mod}\,4\right)[/math]이다. 따라서, 3을 주어진 합동식에 곱하면 [math]3x\equiv7\left(\text{mod}\,4\right),\quad x\equiv21\equiv1\left(\text{mod}\,4\right)[/math]이다.

5 관련 항목

• 중국인의 나머지 정리
• 윌슨의 정리
• 페르마의 소정리
• 오일러의 정리
• 이차 잉여
• 이산 로그