| 정수론 Number Theory | |||
| {{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin: -5px -1px -11px" | 공리 | ||
| 페아노 공리계 · 정렬 원리 · 수학적 귀납법 · 아르키메데스 성질 | |||
| 산술 | |||
| 나눗셈 | 약수·배수 | 배수 · 약수(소인수) · 소인수분해(목록 · 알고리즘) · 공배수 · 공약수 · 최소공배수 · 최대공약수 | |
| 약수들의 합에 따른 수의 분류 | 완전수 · 부족수 · 과잉수 · 친화수 · 사교수 · 혼약수 · 반완전수 · 불가촉 수 · 괴짜수 | ||
| 정리 | 베주 항등식 · 산술의 기본정리 · 나눗셈 정리 | ||
| 기타 | 유클리드 호제법 · 서로소 | ||
| 디오판토스 방정식 | 페르마의 마지막 정리 · 피타고라스 세 쌍 · 버치-스위너턴다이어 추측(미해결) | ||
| 모듈러 연산 | |||
| 잉여역수 · 2차 잉여 · 기약잉여계 · 완전잉여계 · 중국인의 나머지 정리 · 합동식 · 페르마의 소정리 · 오일러 정리 · 윌슨의 정리 | |||
| 소수론 | |||
| 수의 분류 | 소수 · 합성수 · 메르센 소수 · 쌍둥이 소수(사촌 소수 · 섹시 소수) · 페르마 소수 · 레퓨닛 수 | ||
| 분야 | 대수적 정수론(국소체) · 해석적 정수론 | ||
| 산술함수 | 뫼비우스 함수 · 소수 계량 함수 · 소인수 계량 함수 · 약수 함수 · 오일러 파이 함수 · 폰 망골트 함수 · 체비쇼프 함수 · 소수생성다항식 | ||
| 정리 | 그린 타오 정리 · 페르마의 두 제곱수 정리 · 디리클레 정리 · 소피 제르맹의 정리 · 리만 가설(미해결) · 골드바흐 추측(미해결)(천의 정리) · 폴리냑 추측(미해결) · 소수 정리 | ||
| 기타 | 에라토스테네스의 체 · 윌런스의 공식 | ||
서로素[1]
1. 정수론 (relatively prime, coprime)
중학교 1학년 때 배우는 수학 개념. 여러 개의 수들 사이에서 [math(1)] 이외의 공약수가 없음을 이르는 말이다. 따라서 두 수의 공약수가 [math(1)]밖에 없다고 나타낼 수도 있다.두 정수 [math(a)], [math(b)]에 대해, 아래의 세 명제는 서로 동치이다.
서로소를 나타내는 방법은 수직 표현과 같은 [math(\perp)]를 써서 a[math(\perp)]b 로 적거나, 지시함수와 최대공약수의 합성 [math(({\bold 1}_{\{1\}} \circ \gcd)(a,\,b))]를 쓰는 방법이 있다.
1.1. 상세
중1 과정의 유리수의 정의에서도 써먹고, 고등학교 단골 증명 문제인 [math(sqrt{2})]는 무리수임을 증명할 때도 쓰는 등 생각보다 많이 쓰이는 개념이다. 이것을 집합으로 표현하면 이해하기가 어렵지 않다.[2]예를 하나 들어보자. 집합 [math(D_{n})]을 [math(n)]의 양의 약수의 집합이라 하자. 즉
집합 [math(D_{128})]는 [math(128 = 2^7)]의 약수의 집합,
집합 [math(D_{729})]는 [math(729 = 3^6)]의 약수의 집합,
집합 [math(D_{15625})]는 [math(15625 = 5^6)]의 약수의 집합이 된다.
세 집합을 원소나열법으로 나타내면
[math(D_{128} = \left\{1, 2, 4, 8, 16, 32, 64, 128\right\})]
[math(D_{729} = \left\{1, 3, 9, 27, 81, 243, 729\right\})]
[math(D_{15625} = \left\{1, 5, 25, 125, 625, 3125, 15625\right\})]
이 되고,
여기서 교집합 [math(D_{128}\cap D_{729}\cap D_{15625}=\left\{1\right\})]이다.
위의 예처럼 집합 [math(D_{a}\cap D_{b}\cap D_{c}\cap ... =\left\{1\right\})]이면 서로소 당첨. 벤 다이어그램으로 그려보면 아주 명확하게 알 수 있다. 사실, [math(1)]은 모든 자연수의 공약수이고, 따라서 모든 자연수의 약수의 집합에 빠짐없이 들어간다. 왜냐하면 곱셈의 항등원이 [math(1)]이기 때문이다.
당연히 짝수끼리는 서로소가 아니다. 짝수끼리는 기본적으로 공약수 [math(2)]를 갖고 있기 때문이다.
단, 홀수끼리는 서로소일 수도 있고, 아닐 수도 있다. 홀수끼리는 기본적으로 공약수 [math(1)]을 갖고 있고, 경우에 따라서는 [math(1)] 이외의 공약수를 더 갖고 있을 수도 있기 때문이다.[3]
홀수와 짝수의 집합 역시 서로소일 수도 있고, 아닐 수도 있다. 홀수와 짝수의 집합도 기본적으로 공약수 [math(1)]을 갖고 있고, 경우에 따라서는 [math(1)] 이외의 공약수를 더 갖고 있을 수도 있기 때문이다.[4]
유리수의 정의는 [math(\displaystyle {m\over n})]([math(m)]과 [math(n)]은 서로소인 정수, [math(n \neq 0)])의 꼴로 나타낼 수 있는 수이다. 여기서 [math(m)]과 [math(n)]은 [math(1)]을 제외한 공약수를 갖지 않음에 주의. 이 성질을 가지고 [math(\sqrt{2})]가 무리수임을 증명할 수 있다. 증명 방법은 해당 문서에 나와있으니 참조.
소수도 서로소로 정의할 수 있는데, [math(m)]이 소수라는 사실은 [math(0<n<m)]를 만족하는 임의의 정수 [math(n)]에 대해서 [math(n)]과 [math(m)]이 서로소라는 것과 같다.
수학 걸이라는 소설에서는 2편에서 서로소를 직교표시로 사용한다.[5][6]
서로소를 잘만 이용하면 피타고라스 정리의 예시도 초등적[7]으로 찾아낼 수 있다. 근데 유도하는 과정에서 서로소라는 조건을 주도없이 이용하고, 증명해야 돼서 귀찮다.[8]
2. 집합론 (disjoint)
어떤 집합들의 교집합이 공집합일 때, 그 집합들을 서로소라고 한다. 확률론에서 어떤 사건들에 해당하는 집합들이 서로소이면, 그 사건들은 배반사건이다.3. 관련 문서
[1] '서로'와 '소'를 띄어 쓰는지에 견해 차이가 있으나, 검정교과서 등 공신력 있는 출판물에서 대부분 붙여 쓴다. 이 문서에서도 붙여 쓴다.[2] 집합론에서도 서로소 개념을 쓰는데 집합 A와 집합 B의 교집합의 원소가 없을 때, 즉 공집합일 때 'A와 B는 서로소'라고 한다.[3] 예로 3과 9는 [math(1)] 이외에도 [math(3)]이란 공약수를 가지고 있기에 서로소가 아니고, 3과 5는 공약수가 [math(1)]밖에 없기에 서로소다.[4] 예로 6과 27은 [math(1)] 이외에도 [math(3)]이란 공약수를 가지고 있기에 서로소가 아니고, 6과 11은 공약수가 [math(1)]밖에 없기에 서로소다.[5] 여기서는 각각의 수를 소인수분해 해서 [math(2^{a_1}3^{a_2}\cdots)] 라는 식으로 나타낸뒤, 이 수를 [math(\left(a_1,\,a_2\,\cdots\right))] 라는 식으로 나타내서 직교표시가 서로소를 표시하는데 적합함을 보여준다. 근데 이거 한번 익숙해지면 의외로 치기 어렵다.[6] 무한한 차원의 벡터를 사용한다. 참고로 여기서 미르카는 '벡타'라고 부르지만.[7] Elementary. 초등적이라는 소리지 간단하다(Simply)는 소리는 아니다.[8] 이를 이용하면 세 수가 서로 서로소인 피타고라스 수가 무한함을 보일 수 있다.