mir.pe (일반/어두운 화면)
최근 수정 시각 : 2023-10-16 08:52:58

합동식

정수론
Number Theory
{{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)"
{{{#!folding [ 펼치기 · 접기 ]
{{{#!wiki style="margin: -5px -1px -11px" 		공리
페아노 공리계 · 정렬 원리 · 수학적 귀납법 · 아르키메데스 성질
산술
나눗셈 약수· 배수 배수 · 약수( 소인수) · 소인수분해( 목록 · 알고리즘) · 공배수 · 공약수 · 최소공배수 · 최대공약수
약수들의 합에 따른 수의 분류 완전수 · 부족수 · 과잉수 · 친화수 · 사교수 · 혼약수 · 반완전수 · 불가촉 수 · 괴짜수
정리 베주 항등식 · 산술의 기본정리 · 나눗셈 정리
기타 유클리드 호제법 · 서로소
디오판토스 방정식 페르마의 마지막 정리 · 피타고라스 세 쌍 · 버치-스위너턴다이어 추측(미해결)
모듈러 연산
잉여역수 · 2차 잉여 · 기약잉여계 · 완전잉여계 · 중국인의 나머지 정리 · 합동식 · 페르마의 소정리 · 오일러 정리 · 윌슨의 정리
소수론
수의 분류 소수 · 합성수 · 메르센 소수 · 쌍둥이 소수( 사촌 소수 · 섹시 소수) · 페르마 소수 · 레퓨닛 수
분야 대수적 정수론( 대수적 정수론/심화) · 해석적 정수론
산술함수 뫼비우스 함수 · 소수 계량 함수 · 소인수 계량 함수 · 약수 함수 · 오일러 파이 함수 · 폰 망골트 함수 · 체비쇼프 함수 · 소수생성다항식
정리 그린 타오 정리 · 페르마의 두 제곱수 정리 · 디리클레 정리 · 소피 제르맹의 정리 · 리만 가설(미해결) · 골드바흐 추측(미해결)( 천의 정리) · 폴리냑 추측(미해결) · 소수 정리
기타 에라토스테네스의 체 · 윌런스의 공식
}}}}}}}}} ||

1. 개요2. 성질3. 일차합동식
3.1. 일차합동식의 정의3.2. 일차합동식의 해법
3.2.1. 디오판토스 방정식 이용3.2.2. 유클리드 호제법 이용3.2.3. 잉여역수 이용
4. 다항 합동식
4.1. 다항 합동식의 정의4.2. 중국인의 나머지 정리4.3. 헨젤 보조정리
5. 예제
5.1. 예제 15.2. 예제 25.3. 예제 35.4. 예제 4
6. 관련 문서

1. 개요

合 同 式 / congruence

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

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

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

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

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})]이다.[7][8] }}}
  1. [math(ab\equiv ac\pmod{m})]이고, [math(d=\gcd\left(a,m\right))]이면, [math(b\equiv c\pmod{\frac{m}{d}})]이다.[9]
    {{{#!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}})]이다.[10]
    {{{#!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}})]이다.}}}

3. 일차합동식

3.1. 일차합동식의 정의

일차합동식이란, 일차방정식과 비슷하게 미지수의 차수가 1인 합동식을 의미한다. 수식으로 간단하게 표현하면 [math(ax\equiv b\left(\text{mod}\,m\right))]인 형태인 모든 합동식이 일차합동식이다. 일차방정식에 해가 존재할 조건이 있듯이, 일차합동식에도 해가 존재할 조건이 있다. [math(d=\gcd\left(a,m\right))][11]라 했을 때, [math(d\nmid b)]이면[12] 합동식은 정수해를 갖지 않고, [math(d\mid b)][13]이면 법 [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)]이다. 이는 가정에 모순되므로 주어진 합동식의 해는 존재하지 않는다.
  2. [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)]는 임의의 정수).[14] 여기서 [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)]에 대해 서로 합동이 아님을 의미한다. ||

3.2. 일차합동식의 해법

크게 디오판토스 방정식, 유클리드 호제법, 잉여역수를 이용하는 방법으로 나눌 수 있다. 여기서는 다음 예제의 해법을 소개한다.
일차합동식 [math(3x\equiv7\left(\text{mod}\,4\right))]의 해를 구하시오.

3.2.1. 디오판토스 방정식 이용

적당한 정수 [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))]가 해이다.

3.2.2. 유클리드 호제법 이용

[math(\gcd\left(3,4\right)=1)]이므로, 적당한 정수 [math(a,b)]에 대해 [math(3a+4b=1)]이다.[15] 실제로, [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))]이다.

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(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) )] 이 나온다.

4. 다항 합동식

4.1. 다항 합동식의 정의

일차 합동식과 마찬가지로 미지수의 최대 차수가 2 이상이 되어 항을 여러개를 갖는 합동식을 말한다. 원래는 미지수가 여러개가 있는 방정식처럼 다원다차 합동식. 같은 형태로 표기해야 하나, 기본적으로는 일원다차 합동식. 즉 미지수가 한 개만 존재하는 합동식을 위주로 탐구하게 된다. 수식으로 따지면 [math(\displaystyle \sum_{k=0}^{n}a_k x^k\equiv b\pmod{m})]의 형태를 띄게 된다.
풀이 과정에 대한 명백한 알고리즘이 있는 것은 아니나, 특수한 경우에 따라 합동식의 근이 가져야 할 성질이 많이 밝혀져 있다.

4.2. 중국인의 나머지 정리

법 [math(m)] 위주로 풀이하는 쪽에서 사용한다.
[math(m)]이 쌍마다 서로소인 [math(m_1, m_2, m_3, \cdots, m_t)]의 최소공배수라고 하면, 중국인의 나머지 정리는 다음과 같이 사용된다. 또한 [math(m=p_1^{a_1}p_2^{a_2}\cdots p_t^{a_t})]의 표준분해를 가질 경우, 위의 내용에 따라 다음이 자동적으로 성립한다.

4.3. 헨젤 보조정리

5. 예제

합동식을 다룰줄 안다면 여러 경이로운 문제들의 답을 생각보다 쉽게 찾을 수 있다.

5.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^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)]이다.


5.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)]이다.

5.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^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)]이다.

5.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)]역시 서로소다"도 참이다.

6. 관련 문서


[1] [math(a-b)]가 [math(m)]으로 나누어 떨어질 때([math(m)] divides [math(a-b)]). 즉, 적당한 정수 [math(k)]에 대하여 [math(a-b=km)] [2] 기하학의 합동과는 다르다. [3] 영어로는 [math(a)] is congruent to [math(b)] modulo [math(m)]라고 한다. [4] [math(a=b\,{mod}\,m)]와는 다르니 혼동에 주의바란다. 이뜻은 b와 m을 나눈 나머지가 a라는 뜻이다. [5] [math(0 \leq b < m)]일 때에 [6] 혹은 [math(a-b=nm)], [math(n)]은 자연수. [7] [math(k=1)]일 때에는 자명하다. [8] 사실 5의 증명을 반복 적용하면 된다. [9] 특히 a, m이 서로소일 때, [math(b\equiv c)] (mod m)이다. [10] 특히 합동식 풀이에서 흔히 하기 쉬운 실수중 하나가 여기서 유래되는데, [math(aux\equiv bu\pmod{mu})]를 [math(ax\equiv b\pmod{mu})]로 약분해버리는 것. 이런 실수가 일어나면 최대 [math(u-1)]개의 근이 증발한다. [11] d가 a와 m의 최대공약수 [12] b가 d로 나누어 떨어지지 않으면 [13] b가 d로 나누어 떨어지면 [14] 디오판토스 방정식 참조 [15] 최대공약수 참조 [16] 직접 구해야 한다.

분류