| 정수론 Number Theory | |||
| {{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin: -5px -1px -11px" | 공리 | ||
| 페아노 공리계 · 정렬 원리 · 수학적 귀납법 · 아르키메데스 성질 | |||
| 산술 | |||
| 나눗셈 | 약수·배수 | 배수 · 약수(소인수) · 소인수분해(목록 · 알고리즘) · 공배수 · 공약수 · 최소공배수 · 최대공약수 | |
| 약수들의 합에 따른 수의 분류 | 완전수 · 부족수 · 과잉수 · 친화수 · 사교수 · 혼약수 · 반완전수 · 불가촉 수 · 괴짜수 | ||
| 정리 | 베주 항등식 · 산술의 기본정리 · 나눗셈 정리 | ||
| 기타 | 유클리드 호제법 · 서로소 | ||
| 디오판토스 방정식 | 페르마의 마지막 정리 · 피타고라스 세 쌍 · 버치-스위너턴다이어 추측(미해결) | ||
| 모듈러 연산 | |||
| 모듈러 역원 · 2차 잉여 · 기약잉여계 · 완전잉여계 · 중국인의 나머지 정리 · 합동식 · 페르마의 소정리 · 오일러 정리 · 윌슨의 정리 | |||
| 소수론 | |||
| 수의 분류 | 소수 · 합성수 · 메르센 소수 · 쌍둥이 소수(사촌 소수 · 섹시 소수) · 페르마 소수 · 레퓨닛 수 | ||
| 분야 | 대수적 정수론(국소체) · 해석적 정수론 | ||
| 산술함수 | 뫼비우스 함수 · 소수 계량 함수 · 소인수 계량 함수 · 약수 함수 · 오일러 파이 함수 · 폰 망골트 함수 · 체비쇼프 함수 · 소수생성다항식 | ||
| 정리 | 그린 타오 정리 · 페르마의 두 제곱수 정리 · 디리클레 정리 · 소피 제르맹의 정리 · 리만 가설(미해결) · 골드바흐 추측(미해결)(천의 정리) · 폴리냑 추측(미해결) · 소수 정리 | ||
| 기타 | 에라토스테네스의 체 · 윌런스의 공식 | ||
1. 개요
合同式 / congruence정수 [math(a)], [math(b)], [math(m)]에 대하여, [math(mmid(a-b))]일 때[1],
[math(a)] is congruent to [math(b)] modulo [math(m)].
[math(a)]는 법 [math(m)]에 대하여 [math(b)]와 합동[2]이다.
라고 하고, 이를 기호로는[math(a)]는 법 [math(m)]에 대하여 [math(b)]와 합동[2]이다.
| [math(a\equiv b\pmod m)][3] |
일반적으로 나머지는 나누는 수보다 작지만, 합동식에서는 [math(b)]값에 제한이 없다는 차이점은 존재한다. 다시 말해 [math(a\equiv b\pmod m)]에서 [math(b)]에 들어갈 수 있는 수 자체는 많이 있고, 그중에 가장 작은 자연수가 초등학교 때 배운 '나머지'이다.
나머지라는 개념 자체가 초등학교 시절 초반에 배우던 것이어서 보통 마치 분수라는 가르치기 어려운 개념을 회피하기 위해 만들어진 것 같아 보인다. 그러나 천만의 말씀. 나머지는 수학에서 가장 신비로운 개념 중 하나로, 덧셈이나 곱셈에만 적용되는 줄 알았던 연산개념이 신기하게도 나머지에서 완전 같은 방법으로 적용된다는 점을 깨닫게 되면 정수론에 대한 관심이 꽃피게 되는 일이 많다.
대학교의 정수론 수업이나 특정 수학 과목의 정수론 파트를 듣지 않는 한 배울 일이 없지만, KMO를 비롯한 수학 경시대회를 준비한다면 반드시 알아놔야 할 것 중 하나. 2차 잉여까지는 알 필요 없지만 아래 기본적인 성질은 모두 숙지하는 것이 좋다.
2. 성질
1. 반사성(reflexivity)| [math(a\equiv a\pmod m)] |
2. 대칭성(symmetry) (교환법칙)
| [math(a\equiv b\pmod m \implies b\equiv a\pmod m)] |
3. 추이성(transitivity)
| [math(\begin{cases} a\equiv b\pmod m \\ b\equiv c\pmod m\end{cases} \implies a\equiv c\pmod m)] |
또한 정수 [math(k)]에 대하여 다음과 같은 법 호환성(compitibility)[5]이 있다.
4. 정수 평행이동에 대한 호환성(compatibility with translation)
| [math(a+k\equiv b+k\pmod m)] |
5. 정수배에 대한 호환성(compatibility with scaling)
| [math(ka\equiv kb\pmod m)] |
특히 [math(k)]가 음이 아닌 정수일 경우 다음과 같이 지수 연산에 대해서도 법이 불변이다.
6. 지수 연산에 대한 호환성(compatibility with exponentiation)
| [math(a^k\equiv b^k\pmod m)] (단, [math(k\ge0)]) |
| [math(a^k-b^k =(a-b){\left(a^{k-1} + a^{k-2}b+\cdots +ab^{k-2}+b^{k-1}\right)})] |
아래는 두 합동식이 법 [math(m)]으로 같을 때, 즉 [math(\begin{cases} a\equiv b\pmod m \\ c\equiv d\pmod m\end{cases})]일 경우 성립하는 호환성이다.
7. 덧셈/뺄셈 연산에 대한 호환성(compatibility with addition/subtraction)
| [math(a\pm c\equiv b\pm d\pmod m)] |
8. 곱셈 연산에 대한 호환성(compatibility with multiplication)
| [math(ac\equiv bd\pmod m)] |
아래 세 성질은 상기 정수배에 대한 호환성과 관련이 깊다.
9. [math(ab\equiv ac\pmod m)]이고, [math(d=\gcd(a,\,m))]이면, [math(b\equiv c\mathrel{\biggl(\mathrel{\bmod}\dfrac md\biggr)})]이다.[7]
{{{#!folding 증명
[math(ab\equiv ac\pmod m \implies m\mid a(b-c))]인데, [math(d=\gcd(a,\,m))]이므로, [math(a=dx_1)], [math(m=dx_2)]를 만족하는 정수 [math(x_1)], [math(x_2)]가 존재하며 [math(dx_2\mid dx_1(b-c))]이다. 또, [math(d = \gcd(a,\,m))]으로부터 [math(x_1)]과 [math(x_2)]가 서로소이므로 [math(x_2\mid(b-c))]이다. 그런데, [math(x_2=\cfrac md)]이므로, [math(\cfrac md\Bigm|(b-c))]이다. 따라서, [math(b\equiv c\mathrel{\biggl(\mathrel{\bmod}\cfrac md\biggr)})]이다.}}}
10. [math(a\equiv b\pmod m)]이고, [math(n)]이 [math(m)]의 약수이면, [math(a\equiv b\pmod n)]이다.
{{{#!folding 증명
[math(a\equiv b\pmod m \implies m\mid(a-b))]이고 [math(n\mid m \implies n\mid(a-b))]이므로 [math(a\equiv b\pmod n)]이다.}}}11. [math(a\equiv b\pmod m)]이고, [math(d>0)]이 [math(a)], [math(b)], [math(m)]의 공약수이면, [math(\cfrac ad\equiv\cfrac bd\mathrel{\biggl(\mathrel{\bmod}\cfrac md\biggr)})]이다.[8]
{{{#!folding 증명
[math(a\equiv b\pmod m \implies m\mid(a-b))]이고, [math(d)]가 [math(a)], [math(b)], [math(m)]의 공약수이므로 [math(a=dx_1)], [math(b=dx_2)], [math(m=dx_3)]를 만족하는 정수 [math(x_1)], [math(x_2)], [math(x_3)]가 존재하며 [math(dx_3\mid d(x_1-x_2))]에서 [math(x_3\mid(x_1-x_2))]이다. 그런데, [math(x_1 = \cfrac ad)], [math(x_2 = \cfrac bd)], [math(x_3 = \cfrac md)]이므로, [math(\cfrac md\Bigm|\biggl(\cfrac ad-\cfrac bd\biggr))]이다. 따라서, [math(\cfrac ad\equiv\cfrac bd\mathrel{\biggl(\mathrel{\bmod}\cfrac md\biggr)})]이다.}}}3. 일차합동식
3.1. 일차합동식의 정의
일차합동식이란, 일차방정식과 비슷하게 미지수의 차수가 1인 합동식을 의미한다. 수식으로 간단하게 표현하면 [math(ax\equiv b\pmod m)]인 형태인 모든 합동식이 일차합동식이다. 일차방정식에 해가 존재할 조건이 있듯이, 일차합동식에도 해가 존재할 조건이 있다. [math(d=\gcd(a,\,m))], 즉 [math(d)]가 [math(a)]와 [math(m)]의 최대공약수라 했을 때, [math(b)]가 [math(d)]로 나누어 떨어지지 않으면([math(d\nmid b)]) 합동식은 정수해를 갖지 않고, [math(b)]가 [math(d)]로 나누어 떨어지면([math(d\mid b)]) 법 [math(m)]에 대해 정확히 [math(d)]개의 서로 다른 해를 갖게된다. 해의 존재성에 대한 증명은 다음과 같다.- [math(d\nmid b)]인데 해가 존재한다고 가정하자. 그럼 적당한 정수 [math(y)]에 대하여 [math(ax+my=b)]가 성립한다. 그런데 [math(d\mid ax+my=b)]이므로 [math(d\mid b)]이다. 이는 가정에 모순되므로 주어진 합동식의 해는 존재하지 않는다.
- [math(ax+my=b)]의 한 해를 [math(x_0)], [math(y_0)]라 하면, 일반해는 임의의 정수 [math(k)]에 대해 [math(begin{cases}x_k = x_0+cfrac{mk}d \ y_k = y_0-cfrac{ak}dend{cases})]의 꼴이다. 여기서 [math(x_k)]가 합동식 [math(ax\equiv b\pmod m)]을 만족시키는 모든 해이다. 나눗셈 정리에 의해 [math(k=qd+r ~(0\le r<d))]이고, 이를 [math(x_k)]에 대입하면, [math(x_k\equiv x_0 + \cfrac{m(qd+r)}d\equiv x_0+\cfrac{mr}d \equiv x_r\pmod m)]이다. 이것은 곧 모든 [math(x_k)]가 [math(x_0,\,x_1,\,\cdots,\,x_{d-1})] 중 하나와 법 [math(m)]에 대해 합동임을 의미한다. 이제 [math(x_i\equiv x_j\pmod m)], ([math(0\le i,\,j\le d-1)])라 가정하면, [math(\cfrac{im}d\equiv\cfrac{jm}d\pmod m)]이다. 그런데 [math(\gcd\biggl(\cfrac md,\,m\biggr)=\cfrac md)]이므로 위 성질 7번에 의해 [math(i\equiv j\pmod d)]이다. 이는 곧 [math(x_0,\,x_1,\,\cdots,\,x_{d-1})]이 법 [math(m)]에 대해 서로 합동이 아님을 의미한다. ||
3.2. 일차합동식의 해법
크게 디오판토스 방정식, 유클리드 호제법, 잉여역수를 이용하는 방법으로 나눌 수 있다. 여기서는 다음 예제의 해법을 소개한다.| 일차합동식 [math(3x\equiv7\pmod4)]의 해를 구하시오. |
3.2.1. 디오판토스 방정식 이용
적당한 정수 [math(y)]에 대하여 [math(3x+4y=7)]이다. 여기서 [math(x_0=1)], [math(y_0=1)]은 한 해(특수해)임을 쉽게 알 수 있다. [math(\gcd(3,\,4)=1)]이므로 일반해는 [math(\begin{cases} x=1+4t \\ y=1-3t\end{cases})]이다. 우리가 구하는 것은 [math(x)]와 관련된 것이므로 [math(x\equiv1\pmod4)]가 해이다.3.2.2. 유클리드 호제법 이용
[math(\gcd(3,\,4)=1)]이므로, 적당한 정수 [math(a)], [math(b)]에 대해 [math(3a+4b=1)]이다(최대공약수 참고). 실제로, [math((-1){\cdot}3+1{\cdot}4=1)]이다. 이 사실은 우리에게 [math(1\cdot x)]를 얻기 위하여 [math(x)]의 계수를 바꿀 수 있음을 암시한다. 즉, 아래와 같이 된다.| [math(\begin{aligned} 4x\equiv0\pmod4 &&\cdots(1) \\ 3x\equiv7\pmod4 &&\cdots(2)\end{aligned})] |
그래서 답은 [math(x\equiv1\pmod4)]이다.
3.2.3. 잉여역수 이용
법 4에 대한 곱셈표는 아래와 같다.[9]| [math(\times)] | 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(3x\equiv7\pmod4)] 의 양변에 3을 곱하면 [math(3{\cdot}3x\equiv 3{\cdot}7 \pmod4)]가 되는데, [math(3{\cdot}3\equiv1\pmod4)]이고, [math(21\equiv1\pmod4)] 이므로 이를 정리하면 [math(x\equiv1\pmod4)]가 나온다.
4. 다항 합동식
4.1. 다항 합동식의 정의
일차 합동식과 마찬가지로 미지수의 최대 차수가 2 이상이 되어 항을 여러개를 갖는 합동식을 말한다. 원래는 미지수가 여러개가 있는 방정식처럼 다원다차 합동식같은 형태로 표기해야 하나, 기본적으로는 일원다차 합동식. 즉 미지수가 한 개만 존재하는 합동식을 위주로 탐구하게 된다. 수식으로 따지면| [math(\displaystyle \sum_{k=0}^na_kx^k\equiv b\pmod m)] |
풀이 과정에 대한 명백한 알고리즘이 있는 것은 아니나, 특수한 경우에 따라 합동식의 근이 가져야 할 성질이 많이 밝혀져 있다.
4.2. 중국인의 나머지 정리
법 [math(\bm m)] 위주로 풀이하는 쪽에서 사용한다.[math(m)]이 쌍마다 서로소인 [math(m_1,\,m_2,\,m_3,\,\cdots,\,m_t)]의 최소공배수라고 하면, 중국인의 나머지 정리는 다음과 같이 사용된다.
[math(\displaystyle f(x) = \sum_{k=0}^na_kx^k)]일 때, [math(f(x)\equiv0\pmod m)]를 만족한다면, 다음 관계가 성립한다.
또한 [math(m={p_1}^{a_1}{p_2}^{a_2}\cdots{p_t}^{a_t})]의 표준분해를 가질 경우, 위의 내용에 따라 다음이 자동적으로 성립한다.
| [math(f(x)\equiv0\pmod m\Leftrightarrow \begin{cases}\begin{aligned} f(x)&\equiv0\pmod{m_1} \\ f(x)&\equiv0\pmod{m_2}\\ &\vdots \\ f(x)&\equiv0\pmod{m_t} \end{aligned}\end{cases})] |
| [math(f(x)\equiv0\pmod m\Leftrightarrow \begin{cases}\begin{aligned} f(x)&\equiv0\pmod{{p_1}^{a_1}}\\ f(x)&\equiv0\pmod{{p_2}^{a_2}} \\ &\vdots \\ f(x)&\equiv0\pmod{{p_t}^{a_t}}\end{aligned} \end{cases})] |
4.3. 헨젤 보조정리
5. 예제
합동식을 다룰줄 안다면 여러 경이로운 문제들의 답을 생각보다 쉽게 찾을 수 있다.5.1. 예제 1
[math(7^{242})]의 10과 1의 자리수를 합동식을 이용하여 구하시오.- [힌트]
- [math(7^4)]
- [풀이]
- [math(7^4 = 2401 \equiv 1\pmod{100} \rightarrow (7^4)^{60} \equiv 1^{60}\pmod{100} \rightarrow 7^{240} \equiv 1\pmod{100})]
[math(7^{242} = 7^{240} \times 7^2)]이니, [math(7^{242}\equiv7^2\pmod{100})].
그러므로 답은 [math(49)]이다.
또 다른 풀이: [math(7^2 = 49 \equiv 1\pmod4 \rightarrow (7^2)^{121} \equiv 1^{121}\pmod4)]
[math(7^2 = 49 \equiv -1\pmod{25} \rightarrow (7^2)^{121} \equiv (-1)^{121} = -1 = 24\pmod{25})]
[math(7^{242} \equiv 24 \pmod{25} \rightarrow 7^{242} = 25k + 24 \rightarrow 25k + 24 \equiv 1\pmod4 \rightarrow k \equiv 1 \pmod4 \rightarrow k = 4n + 1)], [math(7^{242} = 100n +49)]
따라서 답은 [math(49)]이다.
5.2. 예제 2
[math(7^{7^{777}})]의 1의 자리수를 합동식을 이용하여 구하시오.- [풀이]
- [math(7 \equiv -1 \pmod4 \rightarrow 7^{777} \equiv (-1)^{777} \pmod4 \rightarrow 7^{777} \equiv -1 \pmod4)].
그렇다면, [math(7^{7^{777}} = 7^{4n+(4-1)} = 7^{4n+3})]을 만족하는 자연수 [math(n)]이 존재한다.
[math(7^4 \equiv 1 \pmod{10})]이므로 [math(7^{4n} \equiv 1 \pmod{10})]다. 따라서 [math(7^{4n+3} \equiv 7^3 \equiv 3 \pmod{10})]이다.
답은 [math(3)]이다.
5.3. 예제 3
[math(1^2 + 2^2 + \cdots + 98^2 + 99^2)] 의 1의 자리수를 합동식을 이용하여 구하시오.- [풀이]
- [math(1^2 + 2^2 + \cdots + 98^2 + 99^2 \equiv n \pmod{10})]이라 하자.
[math(1^2 \equiv 11^2 \equiv \cdots \equiv 91^2 \pmod{10})]이며, [math(2^2 \equiv 12^2 \equiv \cdots \equiv 92^2 \pmod{10})]등등 이니까
[math(1^2+2^2+\cdots9^2\equiv 11^2+12^2+\cdots19^2\equiv \cdots \equiv 91^2+92^2+\cdots99^2\equiv \cfrac n{10} \pmod{10})]이다.
따라서 [math(n)]은 [math(10)]의 배수가 되는것이니, 답은 [math(0)]이다.
5.4. 예제 4
합동식 [math(a\equiv b\pmod m)]에 대하여 [math(a)]와 [math(m)]이 서로소일 때, [math(b)]와 [math(m)]이 서로소임을 보이시오.- [풀이]
- 먼저 [math(b)]와 [math(m)]이 서로소가 아니라고 가정해보자. 그렇다면 [math(a\equiv cd \pmod{cn})](단, [math(c>1)])이 성립한다. 그렇다면 [math(cn\mid(a - cd) \rightarrow cn\biggm|c\biggl(\cfrac ac-d\biggr) \rightarrow n \biggm|\biggl(\cfrac ac-d\biggr))] 다. 이게 성립하려면 [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(k)]에 대하여 [math(a-b=km)]일 때.[2] 기하학의 합동과는 다르다.[3] [math(a\mathrel{\color{red}=}b\color{blue}\bmod m)]와는 다르니 혼동에 주의. 등호([math(=)]) 대신에 합동 기호([math(\equiv)]) 기호가 쓰였고 법 부분에 괄호가 씌워져 있다. [math(a=b\bmod m)]은 '[math(b)]를 [math(m)]으로 나눈 나머지가 [math(a)]'라는 뜻이며, [math(a\equiv b\pmod m \iff b = a\bmod m)]이다.[4] 혹은 자연수 [math(n)]에 대하여 [math(a-b=nm)].[5] 쉽게 얘기하자면 법이 [math(m)]으로 일정한 법 불변성.[6] 후술할 곱셉 연산에 대한 호환성을 반복 적용해서도 증명할 수 있다.[7] 특히 [math(a)], [math(m)]이 서로소일 때, [math(b\equiv c\pmod m)]이다.[8] 특히 합동식 풀이에서 흔히 하기 쉬운 실수중 하나가 여기서 유래되는데, [math(aux\equiv bu\pmod{mu})]를 [math(ax\equiv b\pmod{mu})]로 약분해버리는 것. 이런 실수가 일어나면 최대 [math(u-1)]개의 근이 증발한다.[9] 직접 구해야 한다.