일차합동식 합동의 법(modular)

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

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

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

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

2. 성질[편집]

1. (반사성) $a\equiv a\left(\text{mod}\,m\right)$이다.
   

   증명

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

   증명

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

   증명

4. $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)$이다. (복부호동순)
   

   증명

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

   증명

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

   증명

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

   증명

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

   증명

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

   증명

3. 일차합동식[편집]

3.1. 일차합동식의 정의[편집]

일차합동식이란, 일차방정식과 비슷하게 미지수의 차수가 1인 합동식을 의미한다. 수식으로 간단하게 표현하면 $ax\equiv b\left(\text{mod}\,m\right)$인 형태인 모든 합동식이 일차합동식이다. 일차방정식에 해가 존재할 조건이 있듯이, 일차합동식에도 해가 존재할 조건이 있다. $d=\gcd\left(a,m\right)$[7]라 했을 때, $d\nmid b$이면[8] 합동식은 정수해를 갖지 않고, $d\mid b$[9]이면 법 $m$에 대해 정확히 $d$개의 서로 다른 해를 갖게된다. 해의 존재성에 대한 증명은 다음과 같다.
{{| 1. $d\nmid b$인데 해가 존재한다고 가정하자. 그럼 적당한 정수 $y$에 대하여 $ax+my=b$가 성립한다. 그런데 $d\mid ax+my=b$이므로 $d\mid b$이다. 이는 가정에 모순되므로 주어진 합동식의 해는 존재하지 않는다.

1. $ax+my=b$의 한 해를 $x_0,y_0$라 하면, 일반해는 $x_k=x_0+\frac{mk}{d},y_k=y_0-\frac{ak}{d}$의 꼴이다 (단 $k$는 임의의 정수).[10] 여기서 $x_k$가 합동식 $ax\equiv b\left(\text{mod}\,m\right)$을 만족시키는 모든 해이다. 나눗셈 정리에 의해 $k=qd+r,\,\left(0\leq r<d\right)$이고, 이를 $x_k$에 대입하면, $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)$이다. 이것은 곧 모든 $x_k$가 $x_0,x_1,\cdots,x_{d-1}$ 중 하나와 법 $m$에 대해 합동임을 의미한다. 이제 $x_i\equiv x_j\left(\text{mod}\,m\right)$, ($0\leq i,j\leq d-1$)라 가정하면, $\frac{im}{d}\equiv\frac{jm}{d}\left(\text{mod}\,m\right)$이다. 그런데 $\gcd\left(\frac{m}{d},m\right)=\frac{m}{d}$이므로 위 성질 7번에 의해 $i\equiv j\left(\text{mod}\,d\right)$이다. 이는 곧 $x_0,x_1,\cdots,x_{d-1}$가 법 $m$에 대해 서로 합동이 아님을 의미한다.|}}

3.2. 일차합동식의 해법[편집]

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

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

3.2.1. 디오판토스 방정식 이용[편집]

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

3.2.2. 유클리드 호제법 이용[편집]

$\gcd\left(3,4\right)=1$이므로, 적당한 정수 $a,b$에 대해 $3a+4b=1$이다.[11] 실제로, $\left(-1\right)\cdot3+1\cdot4=1$이다. 이 사실은 우리에게 $1\cdot x$를 얻기 위하여 $x$의 계수를 바꿀 수 있음을 암시한다. 즉, 아래와 같이 된다.
$4x\equiv0\left(\text{mod}\,4\right)\quad\cdots\left(1\right)$
$3x\equiv7\left(\text{mod}\,4\right)\quad\cdots\left(2\right)$

그리고, (1) 식에서 (2)식을 빼면, x ≡ -7 (mod 4) 가 된다. -7 + 2*4 = 1 이므로 -7 ≡ 1 (mod 4) 이기에, 위 식을 x ≡ 1 (mod 4) 로 써도 된다.

그래서 답은 $x\equiv1\left(\text{mod}\,4\right)$이다.

3.2.3. 잉여역수 이용[편집]

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

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

위 표에서 보듯이 $3\cdot3\equiv1\left(\text{mod}\,4\right)$이다. 

원래 식 $3x\equiv7\left(\text{mod}\,4\right)$ 의 양변에 3을 곱하면 $3 \cdot 3x\equiv 3 \cdot 7\left(\text{mod}\,4\right)$ 이 되는데, $3\cdot3\equiv1\left(\text{mod}\,4\right)$이고, $21\equiv1\left(\text{mod}\,4\right)$ 이므로 이를 정리하면

$x\equiv 1\left(\text{mod}\,4\right)$ 이 나온다.

namu.wiki