| 정수론 Number Theory | |||
| {{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin: -5px -1px -11px" | 공리 | ||
| 페아노 공리계 · 정렬 원리 · 수학적 귀납법 · 아르키메데스 성질 | |||
| 산술 | |||
| 나눗셈 | 약수·배수 | 배수 · 약수(소인수) · 소인수분해(목록 · 알고리즘) · 공배수 · 공약수 · 최소공배수 · 최대공약수 | |
| 약수들의 합에 따른 수의 분류 | 완전수 · 부족수 · 과잉수 · 친화수 · 사교수 · 혼약수 · 반완전수 · 불가촉 수 · 괴짜수 | ||
| 정리 | 베주 항등식 · 산술의 기본정리 · 나눗셈 정리 | ||
| 기타 | 유클리드 호제법 · 서로소 | ||
| 디오판토스 방정식 | 페르마의 마지막 정리 · 피타고라스 세 쌍 · 버치-스위너턴다이어 추측(미해결) | ||
| 모듈러 연산 | |||
| 잉여역수 · 2차 잉여 · 기약잉여계 · 완전잉여계 · 중국인의 나머지 정리 · 합동식 · 페르마의 소정리 · 오일러 정리 · 윌슨의 정리 | |||
| 소수론 | |||
| 수의 분류 | 소수 · 합성수 · 메르센 소수 · 쌍둥이 소수(사촌 소수 · 섹시 소수) · 페르마 소수 · 레퓨닛 수 | ||
| 분야 | 대수적 정수론(국소체) · 해석적 정수론 | ||
| 산술함수 | 뫼비우스 함수 · 소수 계량 함수 · 소인수 계량 함수 · 약수 함수 · 오일러 파이 함수 · 폰 망골트 함수 · 체비쇼프 함수 · 소수생성다항식 | ||
| 정리 | 그린 타오 정리 · 페르마의 두 제곱수 정리 · 디리클레 정리 · 소피 제르맹의 정리 · 리만 가설(미해결) · 골드바흐 추측(미해결)(천의 정리) · 폴리냑 추측(미해결) · 소수 정리 | ||
| 기타 | 에라토스테네스의 체 · 윌런스의 공식 | ||
1. 개요
홀수인 소수 [math(p)], [math(q)]에 대하여, 다음이 성립한다. 분수에 괄호를 씌운 것처럼 생긴 [math(\left(\dfrac{q}{p}\right))] 기호를 르장드르 기호라 하며, 이 기호의 의미에 대해서는 후술한다.[math(\left(\dfrac{q}{p}\right)=\begin{cases} \left(\dfrac{p}{q}\right) & p \equiv 1 (\text{mod } 4) \text{ or } q \equiv 1 (\text{mod } 4) \\ -\left(\dfrac{p}{q}\right) & p \equiv 3 (\text{mod } 4) \text{ and } q \equiv 3 (\text{mod } 4) \end{cases})]
2. 이차잉여와 이차비잉여
홀수인 소수 [math(p)]에 대하여, 법 [math(p)]에 대한 이차잉여(quadratic residue modulo [math(p)])와 이차비잉여(quadratic nonresidue modulo [math(p)])를 다음과 정의할 수 있다. 정수 [math(a \left ( \not\equiv 0 \left(\text{mod } p \right) \right ))]에 대하여 다음을 만족시키는 정수 [math(b)]가 존재할 때, 정수 [math(a)]가 법 [math(p)]에 대한 이차잉여라 하며, 다음을 만족시키는 정수 [math(b)]가 존재하지 않을 때, 정수 [math(a)]가 법 [math(p)]에 대한 이차비잉여라 한다.[* [math(a \equiv 0 \left(\text{mod } p \right)), 즉, [math(a)]가 [math(p)]의 배수이면, [math(a)]는 법 [math(p)]에 대한 이차잉여도 이차비잉여도 아니다.][math(a \equiv b^2 \left(\text{mod } p \right))]
예를 들어, 2가 법 7에 대한 이차잉여인지 아닌지 확인해 보자. 우선 2가 7의 배수가 아님은 명백하고, 다음이 성립하므로, 2는 법 7에 대한 이차잉여이다.
[math(2 \equiv 3^2 \left(\text{mod } 7 \right))]
그러나 3은 법 7에 대한 이차잉여가 아니다. 1부터 6까지의 자연수를 제곱한 후 7로 나눈 나머지를 구하면 아래 표와 같은데, 이 중 3과 합동인 수가 없기 때문이다.
| [math(b)] | 1 | 2 | 3 | 4 | 5 | 6 |
| [math(b^2)] | 1 | 4 | 9 | 16 | 25 | 36 |
| [math(b^2 ~ mod ~ 7)] | 1 | 4 | 2 | 2 | 4 | 1 |
법 7에 대하여 1, 2, 4는 이차잉여이고, 3, 5, 6은 이차비잉여임을 알 수 있다. 여기에서 주목할 것은, 첫째로 위 표의 마지막 행에 나타난 수인 1, 4, 2, 2, 4, 1이 대칭적이라는 점이며, 둘째로 이로 인해 이차잉여와 이차비잉여의 수가 같다는 것이다. (물론 1≤a≤6의 범위에서.) 이를 요약하면 다음과 같다.
홀수인 소수 [math(p)]에 대하여, [math(1)]부터 [math(p-1)]까지의 정수 중 법 [math(p)]에 대한 이차잉여와 이차비잉여의 수는 각각 [math(\dfrac{p-1}{2})]이다.
- 증명 펼치기·접기
- 먼저, 앞서 그린 것과 비슷한 표를 그린다고 생각하자. 홀수인 소수 [math(p)]를 고정할 때, [math(b=k)]와 [math(b=p-k)]에 대하여 [math(k^2 \equiv (p-k)^2)]이므로 표의 대칭성을 확인할 수 있다. 따라서 표의 마지막 행에 나타나는 값의 개수(=이차잉여인 수의 개수)은 많아야 [math(\dfrac{p-1}{2})]이다.
다음으로, [math(1^2,~ 2^2,~ 3^2,~ … \left(\frac{p-1}{2}\right)^2)]이 법 [math(p)]에 대해 모두 다르다는 것을 확인하자. 즉 표의 마지막 행에 나타나는 값의 개수(=이차잉여인 수의 개수)이 정확하게 [math(\dfrac{p-1}{2})]임을 확인해 보자. 만일 [math(1)]부터 [math(\dfrac{p-1}{2})]까지의 자연수 중 서로 다른 두 수 [math(b_1,~b_2)]가 [math({b_1}^2 \equiv {b_2}^2 \left(\text{mod } p \right))]를 만족시킨다면, [math({b_1}^2 - {b_2}^2 \equiv 0 \left(\text{mod } p \right))]이다. 좌변을 인수분해하면 [math(\left(b_1+b_2\right)\left(b_1 - b_2 \right) \equiv 0 \left(\text{mod } p \right))]인데, 이때 [math(b_1,~ b_2)]는 [math(\dfrac{p-1}{2})] 이하의 자연수이므로, [math(2≤\left(b_1+b_2\right) < p )]가 되며, 이 값은 0과 합동일 수 없다. 또한 [math(1≤\left(b_1-b_2\right) < \dfrac{p-1}{2} )]이므로 이 수도 0과 합동일 수 없다. 법수가 소수일 때 0과 합동이 아닌 두 수를 곱하더라도 0과 합동이 되지 않으므로, 이는 모순이다. 따라서 이러한 [math(b_1,~b_2)]는 존재하지 않는다.
그러므로 홀수인 소수 [math(p)]에 대한 이차잉여의 개수는 [math(\dfrac{p-1}{2})]이며, 이차비잉여의 개수는 [math((p-1)-\dfrac{p-1}{2} = \dfrac{p-1}{2})]이다.
다른 예로, 법 11에 대한 경우를 살펴보자. 15는 법 11에 대하여 이차잉여일까? 즉, 제곱했을 때 15와 합동이 되는 정수가 있을까? 그런데 15는 법 11에 대하여 4와 합동이므로, 15가 법 11에 대하여 이차잉여인지 확인하는 것은 4가 법 7에 대하여 이차잉여인지 확인하는 것과 같다.
[math(15 \equiv 4 \equiv 2^2 \left(\text{mod } 11 \right))]
이므로, 4는 법 11에 대하여 이차잉여이고, 15 역시 그러하다.[1]2.1. 르장드르 기호
정수 [math(a)]가 홀수인 소수 [math(p)]에 대해 이차잉여인 경우와 이차비잉여인 경우를 간단히 나타내기 위하여, 르장드르 기호(Lesendre symbol)를 사용한다. 정의는 다음과 같다.[math(\left(\dfrac{a}{p}\right)=\begin{cases} 1 & a \text{가 법 } p \text{에 대한 이차잉여일 때 } \\ -1 & a \text{가 법 } p \text{에 대한 이차비잉여일 때 } \end{cases})]
앞 문단에서 살펴본 예에서, [math(\left(\dfrac{2}{7}\right)=1)], [math(\left(\dfrac{3}{7}\right)=-1)], [math(\left(\dfrac{15}{11}\right)=1)]이다.
르장드르 기호를 사용하는 것은 왜일까? 바로 합성수의 이차잉여 여부를 편리하게 판단하기 위해서인데, 가령 6이 법 [math(p)]에 대해 이차잉여인지 확인한다고 생각하자. 앞 문단에서 그린 것과 유사한 표를 그려서 해결할 수도 있지만, 1부터 [math(p-1)]까지의 수를 제곱한 후 [math(p)]로 나눈 나머지를 구해서 표를 그리는 것은 쉽지 않다. 그런데 [math(6=2 \times 3)]을 이용하면, 2와 3의 법 [math(p)]에 대한 이차잉여 여부를 확인하면 된다. 즉 합성수의 이차잉여 여부를 판단하기 위해서는, 소수의 이차잉여 여부만 판단하면 된다는 것이다. 그 방법은 아래와 같다.
먼저 2와 3이 모두 이차잉여라면, 6 역시 이차잉여일 것이다.[2]
한편 만일 2와 3 중 하나만 이차잉여라면, 6은 이차비잉여일 것이다.[3]
[1] 참고로 4는 2의 제곱이므로, 모든 홀수인 소수 [math(p)]에 대하여 이차잉여이다.[2] [math(2 \equiv {b_1}^2 \left(\text{mod } p \right) )], [math(3 \equiv {b_2}^2 \left(\text{mod } p \right) )]인 정수 [math(b_1, ~ b_2)]가 존재하므로, [math(6 \equiv 2 \times 3 = (b_1 b_2)^2 \left(\text{mod } p \right) )]이다. 따라서 6은 법 p에 대한 이차잉여.[3] 귀류법을 사용하자. 만일 법 p에 대하여 2는 이차잉여이고 3은 이차비잉여인데, 6은 이차잉여라고 가정하자. 그러면 [math(2 \equiv b^2 \left(\text{mod } p \right) )], [math(6 \equiv c^2 \left(\text{mod } p \right) )]인 정수 [math(b,~c)]가 존재한다. 여기에서 법 [math(p)]에 대한 b의 역원 [math(k)]가 존재하므로, 이 식의 양변에 [math(k^2)]를 곱하면, 좌변은 [math(6k^2 \equiv 2 \times 3 \times k^2 \equiv 3b^2 k^ 2 \equiv 3 (bk)^2 \equiv 3 \left(\text{mod } p \right) )]이고, 우변은 [math(c^2 k^2 \equiv (ck)^2 \left(\text{mod } p \right))]이다. 따라서 [math(3 = (ck)^2 \left(\text{mod } 17 \right))]이 성립하며, 이는 3이 법 17에 대해 이차비잉여라는 점에 모순이다. 따라서 법 p에 대하여 2가 이차잉여, 3은 이차비잉여일 때, 6은 이차비잉여가 된다. 마찬가지로 2가 이차비잉여이고 3만 이차잉여이더라도 동일한 과정을 따를 수 있다. 그러므로 2와 3 중 하나만 이차잉여라면 6은 이차비잉여이다. 보다 직관적으로 이해하자면, 제곱수에 제곱수가 아닌 수를 곱하면 제곱수가 될 수 없다고 생각할 수도 있다.