1. 개요
漢: 合同式 / En: Congruence
정수 [math(a,b,m)]에 대하여, [math(mmidleft(a-bright))]일 때[1]가 [math(m)]으로 나누어 떨어질 때([math(m)] divides [math(a-b)]). 즉, 적당한 정수 [math(k)]에 대하여 [math(a-b=km)]], [math(a)]는 법 [math(m)]에 대하여 [math(b)]와 합동이다[2]([math(a)] is congruent to [math(b)] modulo [math(m)])라고 한다. 이때, 기호로는 [math(aequiv bleft(text{mod},mright))]라고 쓴다. [math(m)]를 합동의 법(modular)이라고 한다. 간단히 말해서, "[math(a)]를 [math(m)]으로 나눈 나머지는 [math(b)]"라는 문장을 수식으로 표현한 것. [3]일 때에][4], [math(n)]은 자연수.]
일반적으로 나머지는 나누는 수보다 작지만, 합동식에서는 [math(b)]값에 제한이 없다는 차이점은 존재한다. 다시 말해 [math(aequiv bleft(text{mod},mright))]에서 b에 들어갈 수 있는 수 자체는 많이 있고, 그중에 가장 작은 양의 정수가 초등학교 때 배운 '나머지'이다.
나머지라는 개념 자체가 초등학교 시절 분수 전에 배우던 것이어서 보통 마치 가르치기 어려운 개념을 회피하기 위해 만들어진 것 같아 보인다. 그러나 천만의 말씀. 나머지는 수학에서 가장 신비로운 개념 중 하나로, 덧셈이나 곱셈에만 적용되는 줄 알았던 연산개념이 신기하게도 나머지에서 완전 같은 방법으로 적용된다는 점을 깨닫게 되면 정수론에 대한 관심이 꽃피게 되는 일이 많다.
대학교의 정수론 수업이나 특정 수학 과목의 정수론 파트를 듣지 않는 한 배울 일이 없지만, KMO를 비롯한 수학 경시대회를 준비한다면 반드시 알아놔야 할 것 중 하나. 2차 잉여까지는 알 필요 없지만 아래 기본적인 성질은 모두 숙지하는 것이 좋다. 사실 경시대회 준비가 아니더라도 고등학교 때 이항정리 문제 중 합동식을 쓰면 편한 문제가 나오므로 알아놔서 절대 나쁠 건 없다.
정수 [math(a,b,m)]에 대하여, [math(mmidleft(a-bright))]일 때[1]가 [math(m)]으로 나누어 떨어질 때([math(m)] divides [math(a-b)]). 즉, 적당한 정수 [math(k)]에 대하여 [math(a-b=km)]], [math(a)]는 법 [math(m)]에 대하여 [math(b)]와 합동이다[2]([math(a)] is congruent to [math(b)] modulo [math(m)])라고 한다. 이때, 기호로는 [math(aequiv bleft(text{mod},mright))]라고 쓴다. [math(m)]를 합동의 법(modular)이라고 한다. 간단히 말해서, "[math(a)]를 [math(m)]으로 나눈 나머지는 [math(b)]"라는 문장을 수식으로 표현한 것. [3]일 때에][4], [math(n)]은 자연수.]
일반적으로 나머지는 나누는 수보다 작지만, 합동식에서는 [math(b)]값에 제한이 없다는 차이점은 존재한다. 다시 말해 [math(aequiv bleft(text{mod},mright))]에서 b에 들어갈 수 있는 수 자체는 많이 있고, 그중에 가장 작은 양의 정수가 초등학교 때 배운 '나머지'이다.
나머지라는 개념 자체가 초등학교 시절 분수 전에 배우던 것이어서 보통 마치 가르치기 어려운 개념을 회피하기 위해 만들어진 것 같아 보인다. 그러나 천만의 말씀. 나머지는 수학에서 가장 신비로운 개념 중 하나로, 덧셈이나 곱셈에만 적용되는 줄 알았던 연산개념이 신기하게도 나머지에서 완전 같은 방법으로 적용된다는 점을 깨닫게 되면 정수론에 대한 관심이 꽃피게 되는 일이 많다.
대학교의 정수론 수업이나 특정 수학 과목의 정수론 파트를 듣지 않는 한 배울 일이 없지만, KMO를 비롯한 수학 경시대회를 준비한다면 반드시 알아놔야 할 것 중 하나. 2차 잉여까지는 알 필요 없지만 아래 기본적인 성질은 모두 숙지하는 것이 좋다. 사실 경시대회 준비가 아니더라도 고등학교 때 이항정리 문제 중 합동식을 쓰면 편한 문제가 나오므로 알아놔서 절대 나쁠 건 없다.
2. 성질
- (반사성) [math(aequiv aleft(text{mod},mright))]이다.
증명
[math(a-a=0)]이고, [math(mcdot0=0)]이므로 [math(mmid0)]이다. 따라서, [math(aequiv aleft(text{mod},mright))]이다.
2. (대칭성) [math(aequiv bleft(text{mod},mright))]이면 [math(bequiv aleft(text{mod},mright))]이다. (교환법칙)
증명
[math(aequiv bleft(text{mod},mright))]이면 [math(mmidleft(a-bright))]이다. 또, [math(mmidleft(a-bright))]이므로 [math(mmidleft(b-aright))]이다. 따라서, [math(bequiv aleft(text{mod},mright))]이다.
3. (추이성) [math(aequiv bleft(text{mod},mright), bequiv cleft(text{mod},mright))]이면 [math(aequiv cleft(text{mod},mright))]이다.
증명
[math(aequiv bleft(text{mod},mright))]이면 [math(mmidleft(a-bright))]이고, [math(bequiv cleft(text{mod},mright))]이면 [math(mmidleft(b-cright))]이다. 그러므로 [math(mmid{left(a-bright)+left(b-cright)})]이다. 즉, [math(mmidleft(a-cright))]이다. 따라서, [math(aequiv cleft(text{mod},mright))]이다.
4. [math(aequiv bleft(text{mod},mright), cequiv dleft(text{mod},mright))]이면, [math(apm cequiv bpm dleft(text{mod},mright))]이다. (복부호동순)
증명
[math(aequiv bleft(text{mod},mright))]이면 [math(mmidleft(a-bright))]이고, [math(cequiv dleft(text{mod},mright))]이면 [math(mmidleft(c-dright))]이다. 그러므로 [math(mmid{left(a-bright)pmleft(c-dright)})]이다. 즉, [math(mmid{left(apm cright)-left(bpm dright)})]이다. 따라서, [math(apm cequiv bpm dleft(text{mod},mright))]이다.
5. [math(aequiv bleft(text{mod},mright), cequiv dleft(text{mod},mright))]이면, [math(acequiv bdleft(text{mod},mright))]이다.
증명
[math(aequiv bleft(text{mod},mright))]이면 [math(mmidleft(a-bright))]이고, [math(cequiv dleft(text{mod},mright))]이면 [math(mmidleft(c-dright))]이다. 그러므로 [math(mmid{left(a-bright)c+left(c-dright)b})]이다. 즉, [math(mmidleft(ac-bdright))]이다. 따라서, [math(acequiv bdleft(text{mod},mright))]이다.
6. [math(aequiv bleft(text{mod},mright))]이면, [math(a^kequiv b^kleft(text{mod},mright))]이다.
증명
7. [math(abequiv acleft(text{mod},mright))]이고, [math(d=gcdleft(a,mright))]이면, [math(bequiv cleft(text{mod},frac{m}{d}right))]이다.
증명
[math(abequiv acleft(text{mod},mright))]이면, [math(mmid aleft(b-cright))]이다. [math(d=gcdleft(a,mright))]이므로, [math(a=dx_1,m=dx_2)]를 만족하는 정수 [math(x_1,x_2)]가 존재한다. 또한, [math(dx_2mid dx_1left(b-cright))]이다. 또, [math(x_1)]과 [math(x_2)]가 서로소이므로 [math(x_2midleft(b-cright))]이다. 그런데, [math(x_2=frac{m}{d})]이므로, [math(frac{m}{d}midleft(b-cright))]이다. 따라서, [math(bequiv cleft(text{mod},frac{m}{d}right))]이다.
8. [math(aequiv bleft(text{mod},mright))]이고, [math(n)]이 [math(m)]의 약수이면, [math(aequiv bleft(text{mod},nright))]이다.
증명
[math(aequiv bleft(text{mod},mright))]이면 [math(mmidleft(a-bright))]이다. 또 [math(nmid m)]이면, [math(nmidleft(a-bright))]이다. 따라서, [math(aequiv bleft(text{mod},nright))]이다.
9. [math(aequiv bleft(text{mod},mright))]이고, [math(d>0)]이 [math(a,b,m)]의 공약수이면, [math(frac{a}{d}equivfrac{b}{d}left(text{mod},frac{m}{d}right))]이다.
증명
[math(aequiv bleft(text{mod},mright))]이면 [math(mmidleft(a-bright))]이다. 또, [math(d)]가 [math(a,b,m)]의 공약수이므로 [math(a=dx_1,b=dx_2,m=dx_3)]를 만족하는 정수 [math(x_1,x_2,x_3)]가 존재한다. 또한, [math(dx_3mid dleft(x_1-x_2right))]이다. 그러므로, [math(x_3midleft(x_1-x_2right))]이다. 그런데, [math(x_1=frac{a}{d},x_2=frac{b}{d},x_3=frac{m}{d})]이므로, [math(frac{m}{d}midleft(frac{a}{d}-frac{b}{d}right))]이다. 따라서, [math(frac{a}{d}equivfrac{b}{d}left(text{mod},frac{m}{d}right))]이다.
3. 일차합동식
3.1. 일차합동식의 정의
일차합동식이란, 일차방정식과 비슷하게 미지수의 차수가 1인 합동식을 의미한다. 수식으로 간단하게 표현하면 [math(axequiv bleft(text{mod},mright))]인 형태인 모든 합동식이 일차합동식이다. 일차방정식에 해가 존재할 조건이 있듯이, 일차합동식에도 해가 존재할 조건이 있다. [math(d=gcdleft(a,mright))][9]라 했을 때, [math(dnmid b)]이면[10] 합동식은 정수해를 갖지 않고, [math(dmid b)][11]이면 법 [math(m)]에 대해 정확히 [math(d)]개의 서로 다른 해를 갖게된다. 해의 존재성에 대한 증명은 다음과 같다.
1. [math(dnmid b)]인데 해가 존재한다고 가정하자. 그럼 적당한 정수 [math(y)]에 대하여 [math(ax+my=b)]가 성립한다. 그런데 [math(dmid ax+my=b)]이므로 [math(dmid b)]이다. 이는 가정에 모순되므로 주어진 합동식의 해는 존재하지 않는다.
|
3.2. 일차합동식의 해법
일차합동식 [math(3xequiv7left(text{mod},4right))]의 해를 구하시오.
|
3.2.1. 디오판토스 방정식 이용
적당한 정수 [math(y)]에 대하여 [math(3x+4y=7)]이다. 여기서 [math(x_0=1,y_0=1)]은 한 해(특이해)임을 쉽게 알 수 있다. [math(gcdleft(3,4right)=1)]이므로 일반해는 [math(x=1+4t,quad y=1-3t)]이다. 우리가 구하는 것은 [math(x)]와 관련된 것이므로 [math(xequiv1left(text{mod},4right))]가 해이다.
3.2.2. 유클리드 호제법 이용
[math(gcdleft(3,4right)=1)]이므로, 적당한 정수 [math(a,b)]에 대해 [math(3a+4b=1)]이다.[15] 실제로, [math(left(-1right)cdot3+1cdot4=1)]이다. 이 사실은 우리에게 [math(1cdot x)]를 얻기 위하여 [math(x)]의 계수를 바꿀 수 있음을 암시한다. 즉, 아래와 같이 된다.
[math(4xequiv0left(text{mod},4right)quadcdotsleft(1right))]
[math(3xequiv7left(text{mod},4right)quadcdotsleft(2right))]
그리고, (1) 식에서 (2)식을 빼면, x ≡ -7 (mod 4) 가 된다. -7 + 2*4 = 1 이므로 -7 ≡ 1 (mod 4) 이기에, 위 식을 x ≡ 1 (mod 4) 로 써도 된다.
그래서 답은 [math(xequiv1left(text{mod},4right))]이다.
[math(4xequiv0left(text{mod},4right)quadcdotsleft(1right))]
[math(3xequiv7left(text{mod},4right)quadcdotsleft(2right))]
그리고, (1) 식에서 (2)식을 빼면, x ≡ -7 (mod 4) 가 된다. -7 + 2*4 = 1 이므로 -7 ≡ 1 (mod 4) 이기에, 위 식을 x ≡ 1 (mod 4) 로 써도 된다.
그래서 답은 [math(xequiv1left(text{mod},4right))]이다.
3.2.3. 잉여역수 이용
법 4에 대한 곱셈표는 아래와 같다.[16]
×
| 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(3cdot3equiv1left(text{mod},4right))]이다.
원래 식 [math(3xequiv7left(text{mod},4right) )] 의 양변에 3을 곱하면 [math(3 cdot 3xequiv 3 cdot 7left(text{mod},4right) )] 이 되는데, [math(3cdot3equiv1left(text{mod},4right))]이고, [math( 21equiv1left(text{mod},4right))] 이므로 이를 정리하면
[math(xequiv 1left(text{mod},4right) )] 이 나온다.
원래 식 [math(3xequiv7left(text{mod},4right) )] 의 양변에 3을 곱하면 [math(3 cdot 3xequiv 3 cdot 7left(text{mod},4right) )] 이 되는데, [math(3cdot3equiv1left(text{mod},4right))]이고, [math( 21equiv1left(text{mod},4right))] 이므로 이를 정리하면
[math(xequiv 1left(text{mod},4right) )] 이 나온다.
4. 예제
합동식을 다룰줄 안다면 여러 경이로운 문제들의 답을 생각보다 쉽게 찾을 수 있다. 연습해보자!
4.1. 예제 1
[math(7^{242})]의 10과 1의 자리수를 합동식을 이용하여 구하시오.
[힌트]
[math(7^4)]
[풀이]
[math(7^4 = 2401 equiv 1 , (text{mod} , 100) rightarrow (7^4)^{60} equiv 1^{60} ,(text{mod} , 100) rightarrow 7^{240} equiv 1 , (text{mod} , 100))]
[math(7^{242} = 7^{240} times 7^2)]이니, [math(7^{242} equiv 7^2 , (text{mod} , 100))].
그러므로 답은 [math(49)]이다.
[math(7^{242} = 7^{240} times 7^2)]이니, [math(7^{242} equiv 7^2 , (text{mod} , 100))].
그러므로 답은 [math(49)]이다.
4.2. 예제 2
[math(7^{7^{777}})]의 1의 자리수를 합동식을 이용하여 구하시오.
[풀이]
[math(7 equiv -1 , (text{mod} , 4) , rightarrow , 7^{777} equiv (-1)^{777} , (text{mod} , 4) rightarrow 7^{777} equiv -1 ,(text{mod} , 4))].
그렇다면, [math(7^{7^{777}}=7^{4n+(4-1)}=7^{4n+3})]을 만족하는 자연수 [math(n)]이 존재한다.
[math(7^4 equiv 1 , (text{mod} , 10))]이므로 [math(7^{4n} equiv 1 , (text{mod} , 10))]다. 따라서 [math(7^{4n+3} equiv 7^3 equiv 3 , (text{mod} , 10))]이다.
답은 [math(3)]이다.
그렇다면, [math(7^{7^{777}}=7^{4n+(4-1)}=7^{4n+3})]을 만족하는 자연수 [math(n)]이 존재한다.
[math(7^4 equiv 1 , (text{mod} , 10))]이므로 [math(7^{4n} equiv 1 , (text{mod} , 10))]다. 따라서 [math(7^{4n+3} equiv 7^3 equiv 3 , (text{mod} , 10))]이다.
답은 [math(3)]이다.
4.3. 예제 3
[math( displaystyle 1^2 + 2^2 + ...)] [math( 98^2 + 99^2)] 의 1의 자리수를 합동식을 이용하여 구하시오.
[풀이]
[math( displaystyle 1^2 + 2^2 + ...)] [math( 98^2 + 99^2 equiv n, (text{mod} , 10))]이라 하자.
[math( 1^2 equiv 11^2 equiv , ... , equiv 91^2 ,(text{mod},10))]이며, [math( 2^2 equiv 12^2 equiv , ... , equiv 92^2 ,(text{mod},10))]등등 이니까
[math(1^2+2^2+...,9^2equiv 11^2+12^2+...,19^2equiv...equiv 91^2+92^2+...,99^2equiv frac{n}{10},(text{mod},10))]다.
따라서 [math(n)]은 [math(10)]의 배수가 되는것이니, 답은 [math(0)]이다.
[math( 1^2 equiv 11^2 equiv , ... , equiv 91^2 ,(text{mod},10))]이며, [math( 2^2 equiv 12^2 equiv , ... , equiv 92^2 ,(text{mod},10))]등등 이니까
[math(1^2+2^2+...,9^2equiv 11^2+12^2+...,19^2equiv...equiv 91^2+92^2+...,99^2equiv frac{n}{10},(text{mod},10))]다.
따라서 [math(n)]은 [math(10)]의 배수가 되는것이니, 답은 [math(0)]이다.
4.4. 예제 4
합동식 [math(a equiv b , (text{mod} , m))]에 대하여 [math(a)]와 [math(m)]이 서로소일 때, [math(b)]와 [math(m)]이 서로소임을 보이시오.
[풀이]
먼저 [math(b)]와 [math(m)]이 서로소가 아니라고 가정해보자. 그렇다면 [math(a equiv cd , (text{mod} , cn))]이 성립한다 (단, [math(c > 1)]). 그렇다면 [math(cn,|,(a - cd) , rightarrow cn,|,c(frac{a}{c}-d) , rightarrow , n , | , (frac{a}{c}-d))] 다. 이게 성립하려면 [math(a)]는 [math(c)]의 배수여야하니, [math(a)]와 [math(m)]도 서로소가 아니다.
여기까지 우리가 증명한 건 "[math(b)]와 [math(m)]이 서로소가 아니라면, [math(a)]와 [math(m)]도 서로소가 아니다"인데, 이건 예제에 나오는 명제의 대우다. 따라서 예제의 명제 "[math(a)]와 [math(m)]이 서로소라면, [math(b)]와 [math(m)]역시 서로소다"도 참이다.
여기까지 우리가 증명한 건 "[math(b)]와 [math(m)]이 서로소가 아니라면, [math(a)]와 [math(m)]도 서로소가 아니다"인데, 이건 예제에 나오는 명제의 대우다. 따라서 예제의 명제 "[math(a)]와 [math(m)]이 서로소라면, [math(b)]와 [math(m)]역시 서로소다"도 참이다.