최근 수정 시각 : 2022-02-18 23:16:27

서로소

정수론
Number Theory
{{{#!wiki style="margin:0 -10px -5px"
{{{#!folding [ 펼치기 · 접기 ]
{{{#!wiki style="margin:-6px -1px -11px"
공리
페아노 공리계 · 정렬 원리 · 수학적 귀납법
산술
나눗셈 약수·배수 배수 · 약수( 소인수) · 소인수분해( 목록) · 공배수 · 공약수 · 최소공배수 · 최대공약수
약수들의 합에 따른 수의 분류 완전수 · 부족수 · 과잉수 · 친화수 · 사교수 · 부부수 · 반완전수 · 불가촉 수 · 괴짜수
정리 베주 항등식 · 산술의 기본정리 · 나눗셈 정리
기타 유클리드 호제법 · 서로소
디오판토스 방정식 페르마의 마지막 정리 · 피타고라스 세 쌍 · 버츠와 스위너톤-다이어 추측(미해결)
모듈러 연산
잉여역수 · 2차 잉여 · 기약잉여계 · 완전잉여계 · 중국인의 나머지 정리 · 합동식 · 페르마의 소정리 · 오일러 정리 · 윌슨의 정리
소수론
수의 분류 소수 · 합성수 · 메르센 소수 · 쌍둥이 소수( 사촌 소수 · 섹시 소수) · 페르마 소수 · 레퓨닛 수
분야 대수적 정수론 · 해석적 정수론
함수 뫼비우스 함수 · 소수 계량 함수 · 소인수 계량 함수 · 약수 함수 · 오일러 파이 함수 · 폰 망골트 함수· 체비쇼프 함수 · 소수생성다항식
정리 그린 타오 정리 · 페르마의 두 제곱수 정리 · 디리클레 정리 · 소피 제르맹의 정리 · 리만 가설(미해결) · 골드바흐 추측(미해결)( 천의 정리) · 폴리냑 추측(미해결) · 소수 정리
기타 에라토스테네스의 체 · 윌런스의 공식
}}}}}}}}} ||

1. 정수론 (relatively prime, coprime)
1.1. 상세
2. 집합론 (disjoint)


서로

1. 정수론 (relatively prime, coprime)

중학교 1학년 때 배우는 수학 개념. 여러 개의 수들 사이에서 [math(1)] 이외의 공약수가 없음을 이르는 말이다. 따라서 두 수의 공약수가 [math(1)]밖에 없다고 나타낼 수도 있다.

두 정수 [math(a)], [math(b)]에 대해, 아래의 세 명제는 서로 동치이다.
서로소를 나타내는 방법은 수직 표현과 같은 [math(\perp)]를 쓰거나, 집합 판별 함수 최대공약수 합성 [math(({\bold 1}_{\{1\}} \circ \gcd)(a,\,b))]를 쓰는 방법이 있다.

1.1. 상세

중1 과정의 유리수의 정의에서도 써먹고, 고등학교 단골 증명 문제인 [math(sqrt{2})]는 무리수임을 증명할 때도 쓰는 등 생각보다 많이 쓰이는 개념이다. 이것을 집합으로 표현하면 이해하기가 어렵지 않다.[1]

예를 하나 들어보자. 집합 [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)] 이외의 공약수를 더 갖고 있을 수도 있기 때문이다.[2]

유리수의 정의는 [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편에서 서로소를 직교표시로 사용한다.[3][4]

서로소를 잘만 이용하면 피타고라스 정리의 예시도 초등적[5]으로 찾아낼 수 있다. 근데 유도하는 과정에서 서로소 라는 조건을 주도없이 이용하고, 증명해야 돼서 귀찮다.[6]

2. 집합론 (disjoint)

어떤 집합들의 교집합이 공집합일 때, 그 집합들을 서로소라고 한다. 어떤 사건들에 해당하는 집합들이 서로소이면, 그 사건들은 배반사건이다.

[1] 집합론에서도 서로소 개념을 쓰는데 집합 A와 집합 B의 교집합의 원소가 없을 때, 즉 공집합일 때 'A와 B는 서로소'라고 한다. [2] 예로 3과 9는 1 이외에도 3이란 공약수를 가지고 있기에 서로소가 아니고, 3과 5는 공약수가 1밖에 없기에 서로소이다. [3] 여기서는 각각의 수를 소인수분해 해서 [math(2^{a_1}3^{a_2}\cdots)] 라는 식으로 나타낸뒤, 이 수를 [math(\left(a_1,\,a_2\,\cdots\right))] 라는 식으로 나타내서 직교표시가 서로소를 표시하는데 적합함을 보여준다. 근데 이거 한번 익숙해지면 의외로 치기 어렵다. [4] 무한한 차원의 벡터를 사용한다. 참고로 여기서 미르카는 '벡타'라고 부르지만. [5] Elementary. 초등적이라는 소리지 간단하다(Simply)는 소리는 아니다. [6] 이를 이용하면 세 수가 서로 서로소인 피타고라스 수가 무한함을 보일 수 있다.