| 정수론 Number Theory | |||
| {{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin: -5px -1px -11px" | 공리 | ||
| 페아노 공리계 · 정렬 원리 · 수학적 귀납법 · 아르키메데스 성질 | |||
| 산술 | |||
| 나눗셈 | 약수·배수 | 배수 · 약수(소인수) · 소인수분해(목록 · 알고리즘) · 공배수 · 공약수 · 최소공배수 · 최대공약수 | |
| 약수들의 합에 따른 수의 분류 | 완전수 · 부족수 · 과잉수 · 친화수 · 사교수 · 혼약수 · 반완전수 · 불가촉 수 · 괴짜수 | ||
| 정리 | 베주 항등식 · 산술의 기본정리 · 나눗셈 정리 | ||
| 기타 | 유클리드 호제법 · 서로소 | ||
| 디오판토스 방정식 | 페르마의 마지막 정리 · 피타고라스 세 쌍 · 버치-스위너턴다이어 추측(미해결) | ||
| 모듈러 연산 | |||
| 잉여역수 · 2차 잉여 · 기약잉여계 · 완전잉여계 · 중국인의 나머지 정리 · 합동식 · 페르마의 소정리 · 오일러 정리 · 윌슨의 정리 | |||
| 소수론 | |||
| 수의 분류 | 소수 · 합성수 · 메르센 소수 · 쌍둥이 소수(사촌 소수 · 섹시 소수) · 페르마 소수 · 레퓨닛 수 | ||
| 분야 | 대수적 정수론(대수적 정수론/심화) · 해석적 정수론 | ||
| 산술함수 | 뫼비우스 함수 · 소수 계량 함수 · 소인수 계량 함수 · 약수 함수 · 오일러 파이 함수 · 폰 망골트 함수 · 체비쇼프 함수 · 소수생성다항식 | ||
| 정리 | 그린 타오 정리 · 페르마의 두 제곱수 정리 · 디리클레 정리 · 소피 제르맹의 정리 · 리만 가설(미해결) · 골드바흐 추측(미해결)(천의 정리) · 폴리냑 추측(미해결) · 소수 정리 | ||
| 기타 | 에라토스테네스의 체 · 윌런스의 공식 | ||
Bézout's Identity[1]
1. 개요
베주 항등식(Bézout's Identity)은 두 정수와 그 최대공약수 사이의 관계를 보여주는 항등식이다. 그 내용은 다음과 같다.| 적어도 둘 중 하나는 0이 아닌 정수 [math(a, b)]가 있다. 그리고 [math(a)]와 [math(b)]의 최대공약수를 [math(d)]라고 하자. 이때, 다음 세 명제가 성립한다. 1. [math(d= ax + by)] 를 만족하는 정수 [math(x, y)]가 반드시 존재한다. 2. [math(d)]는 정수 [math(x, y)]에 대하여 [math(ax+by)] 형태로 표현할 수 있는 가장 작은 자연수이다. 3. 정수 [math(x, y)]에 대하여 [math(ax+by)] 형태로 표현되는 모든 정수는 [math(d)]의 배수이다. |
위 세 명제 중 메인은 1번이며, 1번을 증명하는 과정에서 2번 명제와 3번 명제가 따라서 증명된다.
2. 증명
증명은 다음과 같은 순서로 진행된다. 자세한 과정은 아래에 있다.| 1. [math(ax + by)] 꼴로 표현할 수 있는 가장 작은 자연수가 존재함을 밝힌다. 그것을 [math( d)] 라고 하자. 2. [math( d )]는 [math( a)]와 [math( b )]의 공약수임을 밝힌다. 3. [math( a)]와 [math( b )]의 공약수는 [math( d )]의 약수가 되어야 함을 밝힌다. |
2.1. 단계 1
둘 중 적어도 하나는 0이 아닌 정수 [math(a)], [math(b)]가 있다. 이때 다음과 같은 집합 [math(S)]를 정의하자.[math(S = \left\{ m | m = ax + by > 0, x \in \mathbb{Z}, y\in \mathbb{Z} \right\})]
먼저 [math(S \ne \varnothing)]임을 보이자. 만약 [math( a > 0)]라면 [math( \left| a \right| = a \times 1 + b \times 0 \in S)]이다. 만약 [math( a < 0)]라면 [math( \left| a \right| = a \times (-1) + b \times 0 \in S)]이다. 만약 [math( a = 0)]라면 [math( b \ne 0)]이라서 앞서 a의 경우와 같은 논리로 [math( \left| b \right| \in S)] 이다. 따라서 집합 [math( S )] 는 [math( \left| a \right|)]와 [math( \left| b \right|)] 중 적어도 하나를 원소로 가지므로 [math(S \ne \varnothing)]이다.
집합 [math(S)]는 정의에 따라서 자연수의 부분집합이다. [math(S \ne \varnothing)]이므로 자연수의 정렬성(Well-ordering Principle)[2]에 의해 집합 [math(S)]는 가장 작은 원소를 가진다.
[math(\therefore)] 집합 [math(S)]의 최소 원소, 즉 [math(ax + by)] 꼴로 나타낼 수 있는 가장 작은 자연수는 존재한다. 그것을 [math(d)]라고 부르자.
2.2. 단계 2
[math(S)]의 정의에 의해, 어떤 정수 [math(k, l)]에 대하여 [math(d = ak +bl)]이다.[math( S )]에 속하는 임의의 원소 [math( x )] 에 대하여 만약 [math( x )] 가 [math( d)]의 배수가 아니라고 가정하자.[3] 나눗셈 정리에 의해, [math( x = qd + r (0 \le r < d))]라고 할 수 있다. 그렇다면 나머지 [math( r )] 은 0이 아닌 [math(0 < r < d)]인 자연수이다. 그리고 [math( x )] 는 집합 [math( S )] 의 원소이므로 [math( x = au + bv, u \in \mathbb{Z} , v \in \mathbb{Z})] 라고 할 수 있다.
| [math(r = x - qd = (au + bv) - q(ak + bl) = au - aqk + bv - bql = a(u - qk) + b(v - ql) \in S)] [4] |
[math( r )] 은 [math( x )] 를 [math( d )] 로 나누었을 때 나머지이므로 [math( d )] 보다 작다. 앞서 [math( d )] 를 집합 [math( S )] 에서 가장 값이 작은 원소로 정의했음에도 [math( d )] 보다 작은 [math( S )] 의 원소인 [math( r )] 이 존재하는 것은 [math( d )]의 최소성을 위반하므로 모순이다. 따라서 처음의 가정인 "[math( x )] 가 [math( d )] 의 배수가 아니다."는 거짓이다. 따라서 [math( x )] 는 [math( d )] 의 배수이다.
[math( x )] 는 집합 [math( S )] 의 임의의 원소이므로 집합 [math( S )] 의 모든 원소는 [math( d )] 의 배수이다. 따라서 [math( a )] 혹은 [math( b )] 가 0이 아닌 정수 일 경우 [math( |a| )] 혹은 [math( |b| )] 가 집합 [math( S)]의 원소이기 때문에 [math( d )] 를 약수로 갖는다. 한편 [math( a )] 혹은 [math( b )] 가 0일 경우 0이 아닌 모든 수는 0의 약수이기 때문에 [math( d )] 를 약수로 갖는다. 따라서 [math( d )] 는 [math( a )] 와 [math( b )] 의 공약수이다.
2.3. 단계 3
만약 [math(e)]가 [math(a,b)]의 공약수라고 하자. [math( a=a'e, b = b'e)]이면 [math(d = ak+bl = e(a'k+b'l))]이므로, [math(e)]는 [math(d)]의 약수이다. 따라서 [math(a,b)]의 모든 공약수는 [math(d)]의 약수이므로, [math(d)]는 약수 중에서 가장 큰 최대공약수이다.3. 유클리드 호제법과의 연관성
유클리드 호제법을 수행한 뒤 그 과정을 따라가면 [math(d = ax+by)]를 만족하는 정수 [math(x, y)]를 직접 계산할 수 있는데, 이 알고리즘을 확장된 유클리드 호제법(extended Euclidean algorithm)이라 부르기도 한다. 유클리드 호제법이[math( a = b q_1 + r_1, b = r_1 q_2 + r_2, r_1 = r_2 q_3 + r_3, \cdots,)]
즉
[math(a = r_{-1}, b = r_{0}, r_i = r_{i+1} q_{i+2} + r_{i+2} (0 \le r_{i+2} < r_{i+1}) )]
의 알고리즘으로 진행되고, 마지막에 [math(r_n = \gcd(a,b)=d)] (즉 [math(r_{n+1} = 0)])으로 종결되었다고 하자. 이 때 수열 [math(x_i, y_i)]를 다음과 같이 귀납적으로 정의한다.
[math( (x_{-1}, y_{-1}) = (1,0), (x_0, y_0) = (0,1), (x_{i+2}, y_{i+2}) = (x_{i} - q_i x_{i+1}, y_i - q_i y_{i+1} ) )]
이렇게 정의하면 귀납법을 이용해 항상 [math( r_i = a x_i + b y_i)]가 됨을 보일 수 있고, 최종적으로 [math(d = r_n = a x_n + b y_n )]을 얻을 수 있다.
항목 2의 증명을 보면 [math(d=ax+by)]를 만족하는 정수 [math(x,y)]가 존재한다는 것만 알려줄 뿐, 그 [math(x,y)]를 계산하는 방법은 전혀 알려주지 않는다는 것에서 확장된 유클리드 호제법의 진가가 나온다. 알고리즘 정수론적인 관점에서 보면 그런 [math(x,y)]를 실제로 계산하는 것은 잉여역수를 구하는 등 합동식 연산의 기초가 되기 때문에 중요하고, 또한 호제법 알고리즘의 시간 복잡도도 [math(O( (\log a)^2 ))]로 (나눗셈 횟수만 고려하면 [math(O(\log a))]) 나름 괜찮으니만큼 훌륭한 필수 알고리즘인 것이다.
3.1. 예시
기호로 적으면 어려워 보이지만, '나머지를 a와 b의 일차결합으로 나타낸다'의 아이디어만 생각하면 손으로 계산하기도 생각보단 할만하다.a = 6192, b = 1012
6192 = 6*1012 + 120, 120 = a - 6b
1012 = 8*120 + 52, 52 = 1012 - 8*120 = b - 8(a-6b) = -8a + 49b
120 = 2*52 + 16, 16 = 120 - 2*52 = (a-6b) - 2(-8a+49b) = 17a -104b
52 = 3*16 + 4, 4 = 52 - 3*16 = (-8a+49b) - 3(17a-104b) = -59a + 361b
gcd(a,b) = 4 = -59a + 361b
4. 일차 부정방정식과의 연관성
베주 항등식과 위의 확장된 유클리드 호제법은 다음 꼴의 일차 부정방정식을 완벽히 푸는 방법을 제공한다.| 정수 [math(a,b,c (a^2+b^2>0))]에 대해, 방정식 [math(ax + by = c)]가 정수해를 가질 필요충분조건은 [math(d=\gcd(a,b))]가 [math(c)]를 나누는 것이다. 만약 방정식이 특수한 해 [math((x_0,y_0))]을 가진다면, 방정식의 모든 해는 정수 [math(k)]에 대해 [math((x,y)=(x_0,y_0) + k(-b/d, a/d))] 꼴로 나타나진다. |
5. 확장
베주 항등식은 변수가 하나인 다항식에 대해서도 성립한다. 위의 [math(a, b, d)]를 모두 최고차항이 1인(monic) 다항식으로 바꾸고, '가장 작은 자연수' 를 '차수가 가장 작은 다항식'으로 바꾸자. 물론 [math(x,y)]는 monic일 필요는 없다. 다만 위의 증명은 유리수, 실수, 복소수 계수에서만 성립한다. 정확히는 계수가 체의 범위에 있을 때. 증명도 위와 거의 동일한데, [math(S)]의 정의를 [math(ax+by)]꼴의 모든 다항식으로 놓고, 차수가 가장 작은 monic 다항식을 [math(d)]로 고르면 된다.[5] 다항식에서도 나눗셈 정리가 나머지 정리라는 이름으로 그대로 먹히기 때문.다항식 버전의 베주 항등식은 사실 교과과정에서 부분분수분해를 할 수 있는 암묵적인 근거가 된다. 정수론 버전의 베주 항등식은 유사하게 중국인의 나머지 정리의 근거가 되지만, 이건 교과에 안나오니까...
추상대수학 중 특히 환론을 안다면 단항이데알정역(PID)들이 베주 항등식을 만족시킨다는 것을 알 수 있는데, 단순히 이데알 [math(S=(a,b))]의 생성원을 [math(d)]로 놓으면 된다. 나눗셈 정리와 유클리드 호제법이 성립하는 유클리드정역(ED)은 당연히 된다. 다만 역은 성립하지 않는데, 심지어는 유일인수분해정역(UFD)도 아닌데 베주 항등식은 되는 것들도 있다고 한다...
[1] 프랑스 수학자 에티엔 베주의 이름에서 따 왔다.[2] 자연수의 정렬성(Well-ordering Principle)이란 자연수 전체 집합의 부분집합 중 공집합이 아닌 집합은 값이 가장 작은 원소를 가진다는 원리이다. 첫 번째 원소를 가진다고 말해도 좋다. 자세한 증명은 ProofWiki를 참조하자.[3] 귀류법이 사용되고 있다.[4] 첫 번째 등호에서는 [math( x = qd + r )]에서 [math( qd )] 를 이항하였다. 두 번째 등호에서는 [math( x )] 에 [math( au + bv )] 를 대입하고 [math( d )] 에 [math( ak + bl )] 을 대입하였다. 세 번째 등호에서는 분배법칙을 이용하여 전개한 후 항의 위치를 바꾸었다. 네 번째 등호에서는 [math( a )] 와 [math( b )] 를 인수로 가진 항끼리 묶어냈다. 그럼 [math( S )] 의 정의에 따라 [math( r )] 은 [math( S )] 의 원소가 된다.[5] 이러한 다항식이 두 개 이상일 경우 차수가 더 작은 다항식을 만들어낼 수 있기 때문에 이러한 다항식은 유일하다