[include(틀:정수론)]
[목차]
== 개요 ==
{{{+1 [[合]][[同]][[式]] / congruence}}}

정수 [math(a,b,m)]에 대하여, [[약수(수학)|[math(m\mid\left(a-b\right))]]]일 때[* [math(a-b)]가 [math(m)]으로 나누어 떨어질 때([math(m)] divides [math(a-b)]). 즉, 적당한 정수 [math(k)]에 대하여 [math(a-b=km)]], [math(a)]는 법 [math(m)]에 대하여 [math(b)]와 합동이다[* [[기하학]]의 [[합동]]과는 다르다.]라고 한다.[* 영어로는 [math(a)] is congruent to [math(b)] modulo [math(m)]라고 한다. ] 이때, 기호로는 [math(a\equiv b\left(\text{mod}\,m\right))][* [math(a=b\,{mod}\,m)]와는 다르니 혼동에 주의바란다. 이뜻은 b와 m을 나눈 나머지가 a라는 뜻이다.]라고 쓴다. [math(m)]를 합동의 법(modular)이라고 한다. 간단히 말해서, "[math(a)]를 [math(m)]으로 나눈 나머지는 [math(b)]"라는 문장을 수식으로 표현한 것. [* [math(0 \leq b < m)]일 때에][* 혹은 [math(a-b=nm)], [math(n)]은 자연수.]

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

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

대학교의 [[정수론]] 수업이나 [[이산수학#s-3|특정 수학 과목]]의 정수론 파트를 듣지 않는 한 배울 일이 없지만, [[KMO]]를 비롯한 수학 경시대회를 준비한다면 '''반드시''' 알아놔야 할 것 중 하나. [[2차 잉여]]까지는 알 필요 없지만 아래 기본적인 성질은 모두 숙지하는 것이 좋다. 

== 성질 ==
 1. 반사성(reflexivity) [math(a\equiv a\pmod{m})]이다.
 {{{#!folding  증명  
[math(a-a=0)]이고, [math(m\cdot0=0)]이므로 [math(m\mid0)]이다. 따라서, [math(a\equiv a\pmod{m})]이다.}}}
 1. 대칭성(symmetry) [math(a\equiv b\pmod{m})]이면 [math(b\equiv a\pmod{m})]이다. ([[교환법칙]])
 {{{#!folding 증명
[math(a\equiv b\pmod{m})]이면 [math(m\mid\left(a-b\right))]이다. 또, [math(m\mid\left(a-b\right))]이므로 [math(m\mid\left(b-a\right))]이다. 따라서, [math(b\equiv a\pmod{m})]이다.}}}
 1. 추이성(transtivity) [math(a\equiv b\pmod{m}, b\equiv c\pmod{m})]이면 [math(a\equiv c\pmod{m})]이다.
 {{{#!folding 증명
[math(a\equiv b\pmod{m})]이면 [math(m\mid\left(a-b\right))]이고, [math(b\equiv c\pmod{m})]이면 [math(m\mid\left(b-c\right))]이다. 그러므로 [math(m\mid{\left(a-b\right)+\left(b-c\right)})]이다. 즉, [math(m\mid\left(a-c\right))]이다. 따라서, [math(a\equiv c\pmod{m})]이다.}}}
 1. 복부호동순(compatibility with translation) [math(a\equiv b\pmod{m}, c\equiv d\pmod{m})]이면, [math(a\pm c\equiv b\pm d\pmod{m})]이다. 
 {{{#!folding 증명
[math(a\equiv b\pmod{m})]이면 [math(m\mid\left(a-b\right))]이고, [math(c\equiv d\pmod{m})]이면 [math(m\mid\left(c-d\right))]이다. 그러므로 [math(m\mid{\left(a-b\right)\pm\left(c-d\right)})]이다. 즉, [math(m\mid{\left(a\pm c\right)-\left(b\pm d\right)})]이다. 따라서, [math(a\pm c\equiv b\pm d\pmod{m})]이다.}}}
 1. compatibility with scaling [math(a\equiv b\pmod{m}, c\equiv d\pmod{m})]이면, [math(ac\equiv bd\pmod{m})]이다.
 {{{#!folding 증명
[math(a\equiv b\pmod{m})]이면 [math(m\mid\left(a-b\right))]이고, [math(c\equiv d\pmod{m})]이면 [math(m\mid\left(c-d\right))]이다. 그러므로 [math(m\mid{\left(a-b\right)c+\left(c-d\right)b})]이다. 즉, [math(m\mid\left(ac-bd\right))]이다. 따라서, [math(ac\equiv bd\pmod{m})]이다.}}}
 1.compatibility with exponentiation [math(a\equiv b\pmod{m})]이면, [math(a^k\equiv b^k\pmod{m})]이다.
 {{{#!folding 증명
[math(a\equiv b\pmod{m})]이면 [math(m\mid\left(a-b\right))]이다. 또, [math(k\geq2)]일 때, [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(m\mid\left(a^k-b^k\right))]이다. 따라서, [math(a^k\equiv b^k\pmod{m})]이다.[* [math(k=1)]일 때에는 자명하다.][* 사실 5의 증명을 반복 적용하면 된다.] }}}
 1. [math(ab\equiv ac\pmod{m})]이고, [math(d=\gcd\left(a,m\right))]이면, [math(b\equiv c\pmod{\frac{m}{d}})]이다.[* 특히 a, m이 서로소일 때, [math(b\equiv c)] (mod m)이다.]
 {{{#!folding 증명
[math(ab\equiv ac\pmod{m})]이면, [math(m\mid a\left(b-c\right))]이다. [math(d=\gcd\left(a,m\right))]이므로, [math(a=dx_1,m=dx_2)]를 만족하는 [[정수]] [math(x_1,x_2)]가 존재한다. 또한, [math(dx_2\mid dx_1\left(b-c\right))]이다. 또, [math(x_1)]과 [math(x_2)]가 [[서로소]]이므로 [math(x_2\mid\left(b-c\right))]이다. 그런데, [math(x_2=\frac{m}{d})]이므로, [math(\frac{m}{d}\mid\left(b-c\right))]이다. 따라서, [math(b\equiv c\pmod{\frac{m}{d}})]이다.
}}}
 1. [math(a\equiv b\pmod{m})]이고, [math(n)]이 [math(m)]의 [[약수(수학)|약수]]이면, [math(a\equiv b\pmod{n})]이다.
 {{{#!folding 증명
[math(a\equiv b\pmod{m})]이면 [math(m\mid\left(a-b\right))]이다. 또 [math(n\mid m)]이면, [math(n\mid\left(a-b\right))]이다. 따라서, [math(a\equiv b\pmod{n})]이다.}}}
 1. [math(a\equiv b\pmod{m})]이고, [math(d>0)]이 [math(a,b,m)]의 [[공약수]]이면, [math(\frac{a}{d}\equiv\frac{b}{d}\pmod{\frac{m}{d}})]이다.[* 특히 합동식 풀이에서 흔히 하기 쉬운 실수중 하나가 여기서 유래되는데, [math(aux\equiv bu\pmod{mu})]를 [math(ax\equiv b\pmod{mu})]로 약분해버리는 것. 이런 실수가 일어나면 최대 [math(u-1)]개의 근이 증발한다.]
 {{{#!folding 증명
[math(a\equiv b\pmod{m})]이면 [math(m\mid\left(a-b\right))]이다. 또, [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_3\mid d\left(x_1-x_2\right))]이다. 그러므로, [math(x_3\mid\left(x_1-x_2\right))]이다. 그런데, [math(x_1=\frac{a}{d},x_2=\frac{b}{d},x_3=\frac{m}{d})]이므로, [math(\frac{m}{d}\mid\left(\frac{a}{d}-\frac{b}{d}\right))]이다. 따라서, [math(\frac{a}{d}\equiv\frac{b}{d}\pmod{\frac{m}{d}})]이다.}}}

== 일차합동식 ==
=== 일차합동식의 정의 ===
일차합동식이란, 일차방정식과 비슷하게 미지수의 차수가 1인 합동식을 의미한다. 수식으로 간단하게 표현하면 [math(ax\equiv b\left(\text{mod}\,m\right))]인 형태인 모든 합동식이 일차합동식이다. 일차방정식에 해가 존재할 조건이 있듯이, 일차합동식에도 해가 존재할 조건이 있다. [math(d=\gcd\left(a,m\right))][* d가 a와 m의 최대공약수]라 했을 때, [math(d\nmid b)]이면[* b가 d로 나누어 떨어지지 않으면] 합동식은 정수해를 갖지 않고, [math(d\mid b)][* b가 d로 나누어 떨어지면]이면 법 [math(m)]에 대해 정확히 [math(d)]개의 서로 다른 해를 갖게된다. 해의 존재성에 대한 증명은 다음과 같다.
||
 1. [math(d\nmid b)]인데 해가 존재한다고 가정하자. 그럼 적당한 정수 [math(y)]에 대하여 [math(ax+my=b)]가 성립한다. 그런데 [math(d\mid ax+my=b)]이므로 [math(d\mid b)]이다. 이는 가정에 모순되므로 주어진 합동식의 해는 존재하지 않는다.
 1. [math(ax+my=b)]의 한 해를 [math(x_0,y_0)]라 하면, 일반해는 [math(x_k=x_0+\frac{mk}{d},y_k=y_0-\frac{ak}{d})]의 꼴이다 (단 [math(k)]는 임의의 정수).[* [[디오판토스 방정식]] 참조] 여기서 [math(x_k)]가 합동식 [math(ax\equiv b\left(\text{mod}\,m\right))]을 만족시키는 모든 해이다. [[나눗셈 정리]]에 의해 [math(k=qd+r,\,\left(0\leq r<d\right))]이고, 이를 [math(x_k)]에 대입하면, [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(x_k)]가 [math(x_0,x_1,\cdots,x_{d-1})] 중 하나와 법 [math(m)]에 대해 합동임을 의미한다. 이제 [math(x_i\equiv x_j\left(\text{mod}\,m\right))], ([math(0\leq i,j\leq d-1)])라 가정하면, [math(\frac{im}{d}\equiv\frac{jm}{d}\left(\text{mod}\,m\right))]이다. 그런데 [math(\gcd\left(\frac{m}{d},m\right)=\frac{m}{d})]이므로 위 성질 7번에 의해 [math(i\equiv j\left(\text{mod}\,d\right))]이다. 이는 곧 [math(x_0,x_1,\cdots,x_{d-1})]가 법 [math(m)]에 대해 서로 합동이 아님을 의미한다. ||

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

||일차합동식 [math(3x\equiv7\left(\text{mod}\,4\right))]의 해를 구하시오.||

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

==== [[유클리드 호제법]] 이용 ====
[math(\gcd\left(3,4\right)=1)]이므로, 적당한 정수 [math(a,b)]에 대해 [math(3a+4b=1)]이다.[* [[최대공약수]] 참조] 실제로, [math(\left(-1\right)\cdot3+1\cdot4=1)]이다. 이 사실은 우리에게 [math(1\cdot x)]를 얻기 위하여 [math(x)]의 계수를 바꿀 수 있음을 암시한다. 즉, 아래와 같이 된다.
[math(4x\equiv0\left(\text{mod}\,4\right)\quad\cdots\left(1\right))]
[math(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) 로 써도 된다.

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

==== 잉여역수 이용 ====
법 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(3x\equiv7\left(\text{mod}\,4\right) )] 의 양변에 3을 곱하면 [math(3 \cdot 3x\equiv 3 \cdot 7\left(\text{mod}\,4\right) )] 이 되는데, [math(3\cdot3\equiv1\left(\text{mod}\,4\right))]이고, [math( 21\equiv1\left(\text{mod}\,4\right))] 이므로 이를 정리하면

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

== 다항 합동식 ==
=== 다항 합동식의 정의 ===
일차 합동식과 마찬가지로 미지수의 최대 차수가 2 이상이 되어 항을 여러개를 갖는 합동식을 말한다. 원래는 미지수가 여러개가 있는 방정식처럼 다원다차 합동식. 같은 형태로 표기해야 하나, 기본적으로는 일원다차 합동식. 즉 미지수가 한 개만 존재하는 합동식을 위주로 탐구하게 된다. 수식으로 따지면 [math(\displaystyle \sum_{k=0}^{n}a_k x^k\equiv b\pmod{m})]의 형태를 띄게 된다.
풀이 과정에 대한 명백한 알고리즘이 있는 것은 아니나, 특수한 경우에 따라 '''합동식의 근이 가져야 할 성질'''이 많이 밝혀져 있다.
=== [[중국인의 나머지 정리]] ===
'''법 [math(m)] 위주로''' 풀이하는 쪽에서 사용한다.
[math(m)]이 쌍마다 서로소인 [math(m_1, m_2, m_3, \cdots, m_t)]의 최소공배수라고 하면, 중국인의 나머지 정리는 다음과 같이 사용된다.
 * [math(\displaystyle f(x)=\sum_{k=0}^{n}a_k x^k)]일 때, [math(f(x)\equiv 0\pmod{m})]를 만족한다면, 다음 관계가 성립한다.
 * [math(f(x)\equiv 0\pmod{m}\Leftrightarrow \begin{cases}f(x)\equiv 0\pmod{m_1}\\f(x)\equiv 0\pmod{m_2}\\\vdots\\f(x)\equiv 0\pmod{m_t} \end{cases})]
또한 [math(m=p_1^{a_1}p_2^{a_2}\cdots p_t^{a_t})]의 표준분해를 가질 경우, 위의 내용에 따라 다음이 자동적으로 성립한다.
 * [math(f(x)\equiv 0\pmod{m}\Leftrightarrow \begin{cases}f(x)\equiv 0\pmod{p_1^{a_1}}\\f(x)\equiv 0\pmod{p_2^{a_2}}\\\vdots\\f(x)\equiv 0\pmod{p_t^{a_t}} \end{cases})]
=== 헨젤 보조정리 ===
== 예제 ==
합동식을 다룰줄 안다면 여러 경이로운 문제들의 답을 생각보다 쉽게 찾을 수 있다.
=== 예제 1 ===
[math(7^{242})]의 10과 1의 자리수를 합동식을 이용하여 구하시오.

{{{#!folding [힌트]
[math(7^4)]
}}}
{{{#!folding [풀이]
[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^2 = 49 \equiv 1 \, (\text{mod} \, 4) \rightarrow (7^2)^{121} \equiv 1^{121} \,(\text{mod} \, 4))]
[math(7^2 = 49 \equiv -1 \, (\text{mod} \, 25) \rightarrow (7^2)^{121} \equiv (-1)^{121} = -1 = 24 \,(\text{mod} \, 25))]
[math(7^{242} \equiv 24 \, (\text{mod} \, 25) \rightarrow 7^{242} = 25k + 24 \rightarrow 25k + 24 \equiv 1 \, (\text{mod} \, 4) \rightarrow k \equiv 1 \, (\text{mod} \, 4) \rightarrow k = 4n + 1 , 7^{242} = 100n +49)]
따라서 답은 [math(49)]이다.
}}}


=== 예제 2 ===
[math(7^{7^{777}})]의 1의 자리수를 합동식을 이용하여 구하시오.

{{{#!folding [풀이]
[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)]이다.
}}}
=== 예제 3 ===
[math( \displaystyle 1^2 + 2^2 + ...)] [math( 98^2 + 99^2)] 의 1의 자리수를 합동식을 이용하여 구하시오.

{{{#!folding [풀이]
[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^2\equiv 11^2+12^2+...\,19^2\equiv...\equiv 91^2+92^2+...\,99^2\equiv \frac{n}{10}\,(\text{mod}\,10))]다. 
따라서 [math(n)]은 [math(10)]의 배수가 되는것이니, 답은 [math(0)]이다.
}}}

=== 예제 4 ===
합동식 [math(a \equiv b \, (\text{mod} \, m))]에 대하여 [math(a)]와 [math(m)]이 [[서로소]]일 때, [math(b)]와 [math(m)]이 서로소임을 보이시오.

{{{#!folding [풀이]
먼저 [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)]도 서로소가 아니다"인데, 이건 예제에 나오는 명제의 [[대우#s-4]]다. 따라서 예제의 명제 "[math(a)]와 [math(m)]이 서로소라면, [math(b)]와 [math(m)]역시 서로소다"도 참이다.
}}}

== 관련 문서 ==
 * [[중국인의 나머지 정리]]
 * [[윌슨의 정리]]
 * [[페르마의 소정리]]
 * [[오일러 정리]]
 * [[2차 잉여]]
 * [[이산 로그]]
 * [[수학 관련 정보]]
 * [[정수론]]

[[분류:한자어]][[분류:수학 용어]][[분류:정수론]]