(새 문서: {{학술}} 서로 素<ref>소수의 그 소이다. 참고로 옛날에는 서로 소로 띄어 썼다.</ref>, Relatively prime, Coprime == 정수론 == 수론에서의 서로소...) |
잔글 (문자열 찾아 바꾸기 - "{{학술}}" 문자열을 "" 문자열로) |
||
(다른 사용자 한 명의 중간 판 2개는 보이지 않습니다) | |||
1번째 줄: | 1번째 줄: | ||
서로 素<ref>[[소수]]의 그 소이다. 참고로 옛날에는 서로 소로 띄어 썼다.</ref>, Relatively prime, Coprime | 서로 素<ref>[[소수]]의 그 소이다. 참고로 옛날에는 서로 소로 띄어 썼다.</ref>, Relatively prime, Coprime | ||
== 정수론 == | == 정수론 == | ||
수론에서의 서로소란, 어떤 두 정수에 대해, [[최대공약수]]가 1인 경우를 말한다. 즉, <math>\gcd\left(a,b\right)=1</math>인 경우. 만약 세 개 이상의 | 수론에서의 서로소란, 어떤 두 정수에 대해, [[최대공약수]]가 1인 경우를 말한다. 즉, <math>\gcd\left(a,b\right)=1</math>인 경우. 만약 세 개 이상의 정수 <math>a_1,a_2,\cdots,a_n</math>에 대해, <math>\gcd\left(a_1,a_2,\cdots,a_n\right)=1</math>인 경우에는 그 정수들을 mutually relatively prime {{ㅊ|서로서로소}} 라 부르며, 더욱이 어느 두 정수를 골라도 서로소이면 그 정수들은 쌍끼리 서로소(pairwise relatively prime)이라 부른다. 즉, 정수 <math>\gcd\left(a_i,a_j\right)=1,\,\forall i\neq j</math>이면 쌍끼리 서로소이다. 쌍끼리 서로소가 mutually relatively prime 보다 강한 조건임은 쉽게 알 수 있다. | ||
=== 성질 === | === 성질 === | ||
17번째 줄: | 17번째 줄: | ||
임의의 두 자연수를 뽑았을 때, 그 두 자연수가 서로소일 확률도 구할 수 있다. 두 자연수 <math>a,b</math>가 서로소라는 명제는 <math>a,b</math>를 동시에 나누는 소수가 존재하지 않는다는 명제와 동치이다. 이제, 적당한 소수 <math>p</math>에 대해, <math>a</math>와 <math>p</math>가 서로소일 확률은 <math>\frac{1}{p}</math>이다.<ref><math>p</math>번째 마다 <math>p</math>의 배수가 나타나므로</ref> 그럼 곱의 법칙에 의해, <math>a,b</math>가 동시에 <math>p</math>의 배수가 아닐 확률은 <math>\frac{1}{p^2}</math>이다. 따라서 둘 중 적어도 하나는 <math>p</math>로 나누어 떨어지지 않을 확률은 <math>\left(1-\frac{1}{p^2}\right)</math>이다. 이제 어떤 자연수가 다른 소수 <math>q</math>로 나누어 떨어질 확률은 <math>p</math>로 나누어 떨어질 확률과는 독립이기 때문에, 이를 활용하면 임의의 두 자연수가 서로소일 확률은, | 임의의 두 자연수를 뽑았을 때, 그 두 자연수가 서로소일 확률도 구할 수 있다. 두 자연수 <math>a,b</math>가 서로소라는 명제는 <math>a,b</math>를 동시에 나누는 소수가 존재하지 않는다는 명제와 동치이다. 이제, 적당한 소수 <math>p</math>에 대해, <math>a</math>와 <math>p</math>가 서로소일 확률은 <math>\frac{1}{p}</math>이다.<ref><math>p</math>번째 마다 <math>p</math>의 배수가 나타나므로</ref> 그럼 곱의 법칙에 의해, <math>a,b</math>가 동시에 <math>p</math>의 배수가 아닐 확률은 <math>\frac{1}{p^2}</math>이다. 따라서 둘 중 적어도 하나는 <math>p</math>로 나누어 떨어지지 않을 확률은 <math>\left(1-\frac{1}{p^2}\right)</math>이다. 이제 어떤 자연수가 다른 소수 <math>q</math>로 나누어 떨어질 확률은 <math>p</math>로 나누어 떨어질 확률과는 독립이기 때문에, 이를 활용하면 임의의 두 자연수가 서로소일 확률은, | ||
:<math>\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> | :<math>\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> | ||
이다.<ref>[[Wikipedia:Coprime integers #Probabilities]]</ref> 여기서 <math>\zeta</math>는 리만 제타 함수이다. | 이다.<ref>[[Wikipedia:Coprime integers #Probabilities]]</ref> 여기서 <math>\zeta</math>는 리만 제타 함수이다. | ||
2016년 12월 3일 (토) 00:00 판
서로 素[1], Relatively prime, Coprime
정수론
수론에서의 서로소란, 어떤 두 정수에 대해, 최대공약수가 1인 경우를 말한다. 즉, [math]\displaystyle{ \gcd\left(a,b\right)=1 }[/math]인 경우. 만약 세 개 이상의 정수 [math]\displaystyle{ a_1,a_2,\cdots,a_n }[/math]에 대해, [math]\displaystyle{ \gcd\left(a_1,a_2,\cdots,a_n\right)=1 }[/math]인 경우에는 그 정수들을 mutually relatively prime 서로서로소 라 부르며, 더욱이 어느 두 정수를 골라도 서로소이면 그 정수들은 쌍끼리 서로소(pairwise relatively prime)이라 부른다. 즉, 정수 [math]\displaystyle{ \gcd\left(a_i,a_j\right)=1,\,\forall i\neq j }[/math]이면 쌍끼리 서로소이다. 쌍끼리 서로소가 mutually relatively prime 보다 강한 조건임은 쉽게 알 수 있다.
성질
서로소인 두 정수 [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)라 할 수 있다.
성질
- 임의의 집합과 공집합은 서로소이다.
- 공집합은 자기 자신과 서로소인 유일한 집합이다.