서로 素[1], Relatively prime, Coprime
정수론
수론에서의 서로소란, 어떤 두 정수에 대해, 최대공약수가 1인 경우를 말한다. 즉, [math]\displaystyle{ \gcd\left(a,b\right)=1 }[/math]인 경우. 만약 세 개 이상의 정수가 있을 때, 어느 두 정수를 골라도 서로소이면 그 정수들은 쌍끼리 서로소(pairwise coprime)이라 부른다.
성질
서로소인 두 정수 [math]\displaystyle{ a,b }[/math]에 대해,
- 그 어떤 소수도 [math]\displaystyle{ a,b }[/math]를 동시에 나누지 못한다.
- 적당한 정수 [math]\displaystyle{ x,y }[/math]에 대해, [math]\displaystyle{ ax+by=1 }[/math]이 성립한다.[2]
- 법 [math]\displaystyle{ b }[/math]에 대해, [math]\displaystyle{ a }[/math]는 반드시 잉여 역수를 가진다. 즉, 적당한 정수 [math]\displaystyle{ x }[/math]에 대해, [math]\displaystyle{ ax\equiv1\pmod b }[/math].[3]
- 최소공배수는 [math]\displaystyle{ ab }[/math].
- [math]\displaystyle{ a\mid bc }[/math]이면, [math]\displaystyle{ a\mid c }[/math]이다.[4]
- 너비 [math]\displaystyle{ a }[/math], 높이 [math]\displaystyle{ b }[/math]의 격자점을 찍고, 대각선을 그으면, 그 대각선은 시점과 종점을 제외한 다른 격자점을 지나지 않는다.[5]
각 성질의 증명은 각 항목에 있으니 생략한다.
임의의 두 자연수를 뽑았을 때, 그 두 자연수가 서로소일 확률도 구할 수 있다. 두 자연수 [math]\displaystyle{ a,b }[/math]가 서로소라는 명제는 [math]\displaystyle{ a,b }[/math]를 동시에 나누는 소수가 존재하지 않는다는 명제와 동치이다. 이제, 적당한 소수 [math]\displaystyle{ p }[/math]에 대해, [math]\displaystyle{ a }[/math]와 [math]\displaystyle{ p }[/math]가 서로소일 확률은 [math]\displaystyle{ \frac{1}{p} }[/math]이다.[6] 그럼 곱의 법칙에 의해, [math]\displaystyle{ a,b }[/math]가 동시에 [math]\displaystyle{ p }[/math]의 배수가 아닐 확률은 [math]\displaystyle{ \frac{1}{p^2} }[/math]이다. 따라서 둘 중 적어도 하나는 [math]\displaystyle{ p }[/math]로 나누어 떨어지지 않을 확률은 [math]\displaystyle{ \left(1-\frac{1}{p^2}\right) }[/math]이다. 이제 어떤 자연수가 다른 소수 [math]\displaystyle{ q }[/math]로 나누어 떨어질 확률은 [math]\displaystyle{ p }[/math]로 나누어 떨어질 확률과는 독립이기 때문에, 이를 활용하면 임의의 두 자연수가 서로소일 확률은,
- [math]\displaystyle{ \prod_{\text{prime }p}^{\infty}\left(1-\frac{1}{p^2}\right)=\left(\prod_{\text{prime }p}^{\infty}\frac{1}{1-p^{-2}}\right)=\frac{1}{\zeta\left(2\right)}=\frac{6}{\pi^2}\approx61% }[/math]
이다.[7] 여기서 [math]\displaystyle{ \zeta }[/math]는 리만 제타 함수이다.
대수학
어떤 두 다항식에 대해, 그 두 다항식이 상수 이외의 공통 인수를 가지지 않을 경우, 두 다항식을 서로소라 한다.
집합론
어떤 두 집합 [math]\displaystyle{ A,B }[/math]의 교집합이 공집합인 경우, 두 집합을 서로소(disjoint sets)라 한다. 즉, [math]\displaystyle{ A\cap B=\emptyset }[/math]인 경우. 정수와 마찬가지로, 세 개 이상의 집합들 중, 임의의 두 집합의 교집합이 공집합인 경우, 그 집합들을 쌍끼리 서로소(pairwise disjoint sets)라 할 수 있다.
성질
- 임의의 집합과 공집합은 서로소이다.
- 공집합은 자기 자신과 서로소인 유일한 집합이다.
