| 정수론 Number Theory | |||
| {{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin: -5px -1px -11px" | 공리 | ||
| 페아노 공리계 · 정렬 원리 · 수학적 귀납법 · 아르키메데스 성질 | |||
| 산술 | |||
| 나눗셈 | 약수·배수 | 배수 · 약수(소인수) · 소인수분해(목록 · 알고리즘) · 공배수 · 공약수 · 최소공배수 · 최대공약수 | |
| 약수들의 합에 따른 수의 분류 | 완전수 · 부족수 · 과잉수 · 친화수 · 사교수 · 혼약수 · 반완전수 · 불가촉 수 · 괴짜수 | ||
| 정리 | 베주 항등식 · 산술의 기본정리 · 나눗셈 정리 | ||
| 기타 | 유클리드 호제법 · 서로소 | ||
| 디오판토스 방정식 | 페르마의 마지막 정리 · 피타고라스 세 쌍 · 버치-스위너턴다이어 추측(미해결) | ||
| 모듈러 연산 | |||
| 잉여역수 · 2차 잉여 · 기약잉여계 · 완전잉여계 · 중국인의 나머지 정리 · 합동식 · 페르마의 소정리 · 오일러 정리 · 윌슨의 정리 | |||
| 소수론 | |||
| 수의 분류 | 소수 · 합성수 · 메르센 소수 · 쌍둥이 소수(사촌 소수 · 섹시 소수) · 페르마 소수 · 레퓨닛 수 | ||
| 분야 | 대수적 정수론(국소체) · 해석적 정수론 | ||
| 산술함수 | 뫼비우스 함수 · 소수 계량 함수 · 소인수 계량 함수 · 약수 함수 · 오일러 파이 함수 · 폰 망골트 함수 · 체비쇼프 함수 · 소수생성다항식 | ||
| 정리 | 그린 타오 정리 · 페르마의 두 제곱수 정리 · 디리클레 정리 · 소피 제르맹의 정리 · 리만 가설(미해결) · 골드바흐 추측(미해결)(천의 정리) · 폴리냑 추측(미해결) · 소수 정리 | ||
| 기타 | 에라토스테네스의 체 · 윌런스의 공식 | ||
1. 개요
정수론에서 매우 중요한 문제 중 하나로서, 다항방정식의 정수해 또는 유리수해를 찾는 것이다. 정리하자면 정수 혹은 유리수 계수를 갖는 다항식 [math(F_1, F_2, \cdots, F_k)]에 대해[math( F_1(x_1, \cdots, x_m) = \cdots = F_k(x_1, \cdots, x_m) = 0, \quad x_i \in \mathbb{Z} \text{ or } \mathbb{Q} )]
의 해를 찾는 것으로 생각할 수 있다.교과과정에는 부정방정식 테마 안에 디오판토스 방정식이 소개되긴 하는데, 정확히 말하면 다른 개념이다. 대부분의 디오판토스 방정식은 부정방정식이긴 하다. 부정방정식이 아닌 경우 일반적인 방정식으로 생각해도 무리가 없기 때문. 물론 일반적인 부정방정식은 정수 혹은 유리수 다항식에 관련될 필요도 없고, 정수/유리수해에 국한되어야 하는 것도 아니다. 자세한 것은 부정방정식 참고. 정수해를 찾는 부정방정식에는 [math(2^x + 3^y = 5^z )] 같은 디오판토스 방정식이 아닌 것들도 포함된다. 저런 형태의 것들을 '지수 디오판토스 방정식'이라고 부르기도 하지만, 엄밀하게는 디오판토스 방정식은 아니다.
방정식처럼 딱히 분류가 되어있진 않고, 수학자들이 중요하게 연구하는 몇몇 디오판토스 방정식에는 제각각인 이름이 붙어 있다.
- 일차 부정방정식: [math(ax + by = c)]의 정수해. 풀이는 베주 항등식을 참조.
- 피타고라스 세 쌍 문제: [math(x^2 + y^2 = z^2)]의 정수해/유리수해. 피타고라스 정리에서 나온 방정식이다. 정확히는 세 변의 길이가 모두 정수인 직각삼각형을 찾는 문제.
- 펠 방정식[1]: [math(x^2 - D y^2 = k)]의 정수해
- 페르마의 마지막 정리: [math(x^n + y^n = z^n)] ([math(n \ge 3)]) 의 정수해/유리수해. 문서 참조.
- 타원곡선: [math(y^2 = x^3 + Ax + B)] 의 정수해/유리수해.
- 합동수 문제: 변의 길이가 유리수인 삼각형의 넓이가 주어진 유리수 [math(k)]가 될 수 있는지의 문제. 타원곡선의 유리수해 문제로 귀결된다.
디오판토스 방정식은 같은 수준의 방정식에 비해 어렵다는 것이 중론이다. 당장에 저 페르마의 마지막 정리만 봐도 그렇고, 한때 인터넷에서 나돌았던 과일 분수방정식 문제
[math( \dfrac x{y+z} +\dfrac y{z+x} +\dfrac z{x+y} = 4 \qquad (x,y,z \in \N) )] |
- (디오판토스)일차방정식: 쉬움
- 이차방정식: 완전히 이해된 수준으로 꽤나 기초적인 수준에서 해결 가능
- 삼차방정식: 심오한 이론의 거대한 바다와 수백만 가지의 미해결 문제[5]
- 사차 이상의 방정식: 정말... 정말로 어렵다.
[math(\dfrac{x}{y+z} + \dfrac{y}{z+x} + \dfrac{z}{x+y} = n \ \ (x, y, z \in \mathbb{N}))]
이 꼴의 방정식 형태와 풀이도 지금은 은퇴한 수학자인 Allan MacLeod가 겨우 몇 년 전에야 제시했고 Alon Amit이 본 것 가운데 가장 훌륭한 형태의 디오판토스 방정식이라고. [math(n)]이 홀수일 경우의 정수해는 없다고 한다. SNS에 나도는 어이없는 "과일 문제"[6]들을 풍자하기 위해 공들여 만든 문제라 한다.
다항방정식의 경우 복소수 위에서는 항상 해가 있다는 것이 대수학의 기본정리로 증명되었고, 지수방정식도 해의 유무는 미분으로 판정할 수 있지만, 디오판토스 방정식의 해가 존재하는지 아닌지 알 수 있는 일반적인 알고리즘은 없다는 것이 증명되었다. (힐베르트의 10번째 문제의 마티아셰비치의 풀이) 일반적인 경우는 고사하고 저 단순해 보이는 타원곡선도 해의 개수를 구하는 문제는 몇백여년 동안 미해결이라, 지금도 밀레니엄 문제 중 하나인 버치-스위너턴다이어 추측이란 이름으로 수학자들을 괴롭히고 있다. 어떻게 보면 편미분방정식하고 느낌이 비슷하다. 중요하다고 생각해서 연구는 많이 했지만 해가 있는지 없는지도 모르고, 수치계산은 하지만 그게 해인지는 장담할 수 없고...
대신에 많은 이/공학 분야의 핵심 도구인 편미분방정식과 다르게, 현실세계에서의 쓰임새가 정보기술이 발달하기 전엔 잉여스러운 건 사실이다. 모든 물리량을 실수로 생각하는 현실에서 정수방정식이 자연스럽게 나오는 것도 아니고, 방정식의 해가 정수로 맞아떨어지는 것도 심미성 이상의 딱히 큰 의미를 갖진 않는다. 덕분에 디오판토스 방정식은 그 정수론 중에서도 가장 순수한 분야로 취급받아 왔다. 다만 근/현대에 들어서 컴퓨터와 이산수학의 발전으로 이 디오판토스 방정식마저 응용되는 분야가 등장하기 시작했다. 당장에 타원곡선이 암호에 응용되고, 소인수분해 문제 등을 계기로 디오판토스 방정식의 빠른 풀이가 중요시되는 알고리즘 정수론(algorithmic number theory)이 급부상하며, 최적화 문제에서도 정확한 정수해가 필요한 정수계획법(integer programming) 문제가 산업현장에서 나오는 걸 보면, 그동안 순수한 학문으로 취급되었던 정수론마저 응용수학이라는 영역에 차츰차츰 편입되고 있다고 볼 수 있다.
물론 많은 수학자들, 특히 대수적 정수론 덕후들에게는 그런 거 없고, 인류가 수천 년 동안 연구했던 근본적인 문제와 그 아름다움에 대한 탐구만이 있을 뿐이다.
2. 역사
기원전 1800년경의 것으로 추정되는 고대 바빌로니아의 Plimpton 322 석판(콜롬비아 대학의 Plimpton 소장품)에는 다양한 피타고라스의 세 쌍(즉 [math(a^2 + b^2 = c^2)]의 정수해)들이 60진법 쐐기문자로 적혀 있다. 저 석판의 의미가 무엇인지는 논쟁의 여지가 있지만, 단순히 (3,4,5)나 (5,12,13) 이런 작은 숫자가 아니라 [math(4961^2 + 6480^2 = 8161^2)] 같은 큰 숫자들이 랜덤하게 적혀 있는 걸 봐서는 이들이 자연수 길이로 직각삼각형을 만드는 체계적인 방법을 알았을 것으로 추정된다. 2의 제곱근의 근사값이 적혀있는 다른 석판에서 드러나듯 바빌로니아인들은 제곱근과 피타고라스 정리에 대해 확실히 알고 있었다. 고대 이집트의 수학에 대해선 바빌로니아보다는 남아 있는 자료가 없지만, 이들이 밥먹듯이 하는게 단위분수 분해였니 만큼[7] 정수문제도 많이 연구했을 것이다. 사실 고전 그리스 까지만 해도 자연수말고 다른 수는 (거의) 없었기 때문에 "방정식=정수방정식"이긴 했다.고대 그리스의 수학은 기하학이 주였지만 수론에 대해서도 당연히 많은 발전이 이루어졌다. 유클리드의 원론은 소인수분해(즉 산술의 기본정리 증명)와 유클리드 호제법, 약수/배수의 성질 등을 기초정수론 수준으로 다루고 있고, 그리고 우리가 알고 있는 피타고라수 세 쌍의 일반적인 풀이 [math((a,b,c)=k(m^2-n^2, 2mn, m^2 +n^2))] (원론 원전에는 서로소인 풀이, 즉 [math(k=1)]의 풀이만이 나와있다)가 제시된다. 정수방정식에 대해 더욱 집중적으로 연구한 것은 이 항목의 이름을 만들어준 디오판토스로, 그의 '산학'(Arithmetica, Ἀριθμητικῶν) 책에선 최초로 미지수를 문자로 사용하고 이차 정수방정식에 대한 일반적인 고찰을 하였다. 디오판토스 방정식을 사실상 처음 체계적으로 연구한 셈이다. 중세를 거쳐 산학을 포함한 그리스 서적들이 번역되어 아라비아, 인도로 흘러가며 디오판토스 방정식의 연구도 실전(失傳)과 수복을 반복하며 띄엄띄엄 이어졌다.
고대 중국 수학에서는 서구권과는 다르게 정수에 딱히 큰 의미를 갖지 않았다. 원론과 비슷하게 동양산학의 기원으로 꼽히는 3세기 경의 구장산술(九章算术)은 체계화된 연립일차방정식과 이차방정식의 해법을 담고 있지만 정수해만을 취급하진 않는다. 방정식의 이름 '방정(方程)'이 이 구장산술 8장의 이름에서 따온 것으로, 계수들을 정방형으로(지금으로 치면 행렬처럼) 써놓고 풀었다고 해서 붙여졌다고 한다. 다만 이 구장산술에서도 다량의 정수 부정방정식 문제가 등장하는데, 모두 실제로 정수해가 필요할 물류와 상거래에 관한 문제들이다. 요즘 말하는 정수계획법 느낌의 실용적인 문제를 중요시한 것으로 보인다. 그래도 물론 체계적으로 방정식을 분류하고 그러진 않았고, 이후에도 중화권의 수학은 일반적 분수/소수, 실수로의 근사를 생각하는 수치해법 쪽으로 주로 발전하여 정수방정식과는 영영 멀어진다.
디오판토스 방정식이 다시 유럽 수학의 주무대에 등장한 것은 디오판토스의 '산학' 책이 프랑스의 어느 법률가한테 들어가고 나서일 것이다. 페르마가 '산학'에서 발굴하고 일반화한 여러 문제들은 당대 수학자들의
그 뒤로는 쿰머의 아이디얼, 디리클레/데데킨트의 대수적 정수 개념 등 대수적 정수론의 역사를 따라간다. 20세기~21세기의 현재 디오판토스 방정식 연구는 대수학, 해석학, 기하학을 망라하는 현대의 모든 수학이 집대성되어 있다고 볼 정도로 거대해졌고, 많은 수학자들이 관심을 갖는 수학계의 중심 분야 중 하나로 간주되고 있다.
3. 풀이
중등과정 및 경시대회에서 몇 가지의 유형이 등장하고는 한다. 체계적으로 공부하려면 대학수학인 정수론이 필요하기 때문에 몇몇 경시대회 학생들은 정수론을 상당히 심화해서 공부하기도 한다.3.1. 부등식법
부등식을 이용하여 변수의 범위를 좁히는 방법. 부등식을 세울때 미지수의 개수를 줄이고필요없는 항은 과감히 지워버림으로써 양변중 더 큰쪽을 작게하거나, 더 작은쪽을 크게 만든다.
특별히 a,b,c 가 대칭적인 경우 a<b<c(등호생략) 등의 순서배열이 가능하고 보통의경우 가장작은 a 의 범위를 좁히게 된다.
정말 유용하다. 일단 대칭식일 경우 무조건 부등식법을 이용해라.
| 대칭식[9]인 디오판틴 방정식일 경우 무조건 부등식법을 의심해봐야 한다. |
| 부등식법을 이용해 디오판틴 방정식을 풀기 위해서는 WLOG [10] 을 알아야 한다. |
- WLOG는 정해지지 않은 미지수의 대소관계를 정하는 것이다. 예를 들어 [math(a + b = 3)] 일때 일반성을 잃지 않고 [math(a ≤ b)] 라고 쓸 수 있다는 것이다. [11]
3.1.1. 예제
[math( a^3 + b^3 +c^3 = 2001 )] 를 만족하는 자연수 해를 모두 구해라.
|
- 부등식을 이용해서 미지수가 가능한 값의 후보들을 추려내는 것이 바로 디오판토스 방정식의 부등식법이다.
3.2. 인수분해 및 식의 변형
흔히 부정방정식이라 부르는 풀이법이다.예를 들면, 다음과 같은 문제를 보자.
"[math(x+y=xy)]를 만족하는 정수해의 순서쌍 [math((x, y))]를 모두 구하시오."
풀이 : 주어진 방정식의 좌변을 전부 이항하면 [math(xy-x-y=0)]이고, 양변에 1을 더하면 [math(xy-x-y+1=1)]이다.
좌변을 인수분해하면 [math((x-1)(y-1)=1)]이고 [math(x, y)]가 모두 정수이므로 [math((x-1, y-1)=(1, 1), (-1, -1))]일 수밖에 없다. 즉, [math((x, y)=(2, 2), (0, 0))]이다.
3.3. 잉여계를 이용하는 방법
정수론에서 이용되는 [math(\bmod)][12]을 사용한다. 예로는 완전제곱수는 [math(\bmod\, 4)]로는 0또는 1이 될 수밖에 없고, 세 제곱수는 [math(\bmod\, 9)]로 -1, 0, 1 중 하나임 등을 사용한다.예시 : [math(x^2-3y^2=17)]를 만족하는 정수해는 존재하지 않음을 보이시오.
풀이 : 양변은 [math(\bmod\, 3)]으로 해석해 보면, [math(x^2)]≡[math(2 (\bmod\, 3))]이 되어야 이는 모순이다. 즉, 이와 같은 부정방정식의 정수해는 존재하지 않는다[13]
3.4. 판별식법
정수 계수 이차방정식 이 정수근을 가진다면 그 판별식 는 항상 제곱수여야 한다. [14]- 판별식법은 복잡한 이차 디오판토스 방정식을 풀때 아주 효과적이다.
- 위 정리의 역은 성립하지 않는다. 즉, 판별식이 제곱수라고 무조건 정수근이 나오지는 않는다.[15]
예제. 이 정수근을 가질 때 자연수 의 값을 구해라.
}}}3.5. 피타고라스 방정식을 이용한 방법
3.6. 무한강하법
방정식의 양변이 짝수밖에 나올 수 없다는 사실을 토대로 약분을 무한번 하여도 계속해서 짝수가 나와야함을 통해 답이 0뿐이라는 방법예시: [math(x^2+y^2+z^2=x^2y^2)]을 만족하는 정수해를 모두 구하시오.
풀이: [math(x, y, z)]가 모두 홀수이면 [math(3)]≡[math(1 (\bmod\, 4))]가 되어 모순이고 셋 중 하나가 홀수이면 좌변은 홀수, 우변은 짝수가되어 모순이다. 또한, [math(x, y)]가 홀수이고 [math(z)]가 짝수이면 [math(2)]≡[math(1 (\bmod\, 4))]가 되어 모순이다. 거기에 [math(x, y)]중 하나만 홀수이고 [math(z)]가 홀수이면 [math(2)]≡[math(0 (\bmod\, 4))]가 되어 또 모순이다.
이 뜻은 곧, [math(x, y, z)]가 모두 짝수이란 말이고, [math(x=2x_1, y=2y_1, z=2z_1)]로 놓으면 [math(x_1^2+y_1^2+z_1^2=x_1^2y_1^2)]이 되어 무한강하법을 사용할 수 있다. 즉, [math(x=y=z=0)]이다.
3.7. 타원곡선
[math(y^2 = ax^3 + bx + c)] 꼴로 정리한 뒤 푸는 방법. 3차 이상의 디오판토스 방정식에서 사용하는 방법이다.4. 관련 문서
[1] 이 방정식을 푼 윌리엄 브라운커(William Brounker)의 해법을 소개한 존 펠(John Pell)의 저술을 오일러가 보고 펠이 푼 거로 착각하는 바람에 펠의 이름이 붙어버렸다.[2] 에르되시 번호가 2, 예루살렘 히브리 대학교 수학 박사.[3] Roughly 99.999995% of the people don’t stand a chance at solving it, and that includes a good number of mathematicians at leading universities who just don’t happen to be number theorists.[4] 이 문제의 가장 작은 해는 자그마치 79, 80, 81자리나 되는 숫자. 덧붙여서 우변의 상수항 값이 클수록 해의 자릿수가 눈덩이처럼 불어난다는 사실까지 밝혀냈다. 가령 4 대신 178을 대입해봤더니 거의 4억에 육박하는 자릿수가 튀어나왔다고 한다. 다만 엄밀하게는 상수항이 커질수록 자릿수가 증가하는 것이 아니라 줄어들기도 한다. 참고로 해는 {a, b, c}={4373612677928697257861252602371390152816537558161613618621437993378423467772036, 36875131794129999827197811565225474825492979968971970996283137471637224634055579, 154476802108746166441951315019919837485664325669565431700026634898253202035277999}이다. 집합 기호로 쓴 이유는 윤환식이기 때문이다.[5] 즉, 버치-스위너턴다이어 추측 같은 문제가 수백만 개씩이나 있다는 뜻이다.[6] 일명 Fruit math 밈. 미지수를 알록달록한 과일 그림으로 치환한 방정식 문제들로 약 2016년부터 페이스북 등을 중심으로 퍼져나갔다. 대다수는 일차연립방정식 수준의 간단한 문제임에도 불구하고 "오직 극소수의 사람들만이 이 문제를 풀 수 있다"나 "너무 어려워서 풀 수 없다"같은 문장들이 덤으로 달려 있다. 범람하고 있는 조악한 모바일 게임 광고들과 유사한 면이 있다. MacLeod의 문제 또한 원문에는 포도나 딸기 같은 과일 그림이 미지수 대신 나와 있어 얼핏 보기엔 걸려들기 좋게 되어 있다.[7] 고대 이집트인들에게 분수는 2/3을 제외하고는 모두 단위분수(분자가 1인 분수)였다. [math(\frac{1}{9} \cdot \frac{2}{3} = \frac{1}{18}+\frac{1}{54})] 이런 식의 계산이 일상적이었던 것.[8] 중세 인도와 아라비아에서 정수론이 어느 수준까지 발전했는지는 분명하지 않다. 6세기 경 브라마굽타가 [math(x^2-61y^2=1)]의 (1,0)이 아닌 정수해를 찾았다고 전하기는 하지만 그것이 일반적인 방법인지는 알 수 없다. 어찌되었건 이러한 업적들이 근대 유럽의 수학자들에게는 전달되지 않은 것으로 보인다. 중국인의 나머지 정리 같은 경우도 처음에는 오일러가 발견했다고 생각했으니.[9] 대칭식이란 서로의 미지수를 바꿔도 식이 변하지 않는 식을 의미한다. 예를 들면 [math(x + y + z = n )] 일때 [math(x )] 를 [math(y )] 로 바꿔도 식은 변함이 없고 같은 방법으로 [math(y )] 를 [math(z )] 로 바꿔도 식은 변하지 않는다. 이런식을 대칭식이라고 부른다.[10] "일반성을 잃지 않고" 라는 뜻으로 사용된다. 약자는 Without Loss Of Generality[11] 처음 접하면 이상할 수 있지만 전혀 이상하지 않다. 예를 들어 2+1=3 이였다면 자연스럽게 [math(a =1, b=2)] 로 자동결정 된다.[12] 합동식을 이용하는것이다,[13] 사실 이부분은 정수론을 많이 접해본 이가 아니면 알기 어렵다.[14] 증명할 필요가 있을까? [math(D)]가 제곱수가 아니라고 하자. 그렇다면 [math(\sqrt{D})]는 무리수이다. 이때 근은 [math(\dfrac{-b\pm \sqrt D}{2a})]이다. 이때 무리수와 정수의 합 [math(-b\pm \sqrt{D})]는 무리수이고 무리수와 0이 아닌 유리수의 곱은 무리수이므로 정수근을 가질 수 없다.[15] 근의 공식에 2a가 분모로 있기 때문이다.