임의로 뽑은 두 자연수가 서로 소일 확률이 얼마나 될까? 대충 짐작해보시라. 1/2는 넘을까. 넘지 않을까?

해석적 정수론에 관한 지식이 없는 사람에게는 '아니 이런걸 정말 계산이나 할 수 있는 것일까?' 하고 놀랄지도 모르겠다. 근데 계산이 된다. 정답은 6/π²로서 구글링해보면 대략 0.607927102근방의 수임을 알 수 있다. 그러니까 거의 절반이 넘는 확률을 가지고 있다.

그런데 6/π²는 어디서 낯이 익은 수 같다. (수에 낯은 없지만-_- 큭 썰렁) 당근 1/ζ(2)의 값이다. 리만 제타함수가 나오긴 하지만 증명의 전체적인 내용은 어렵지 않게 이해할 수 있으므로 소개한다.

다음 증명은 '오일러 상수 감마' p117-119에 있는 내용임.

---

0. notation >
[x]는 x를 넘지 않는 최대 정수를 의미한다.

1-1. fact >
다음 등식이 성립한다. 이것은 증명없이 이용한다.그러니까 제곱의 역수의 총합은 π²/6 이라는 말이다. 이것은 너무 유명한 결과라서 링크로 때우고 넘어간다.ㅋㅋ
http://en.wikipedia.org/wiki/Basel_problem

1-2. fact >
다음 극한이 성립한다.이건 뭐 당연하다. 증명도 쉽다.

2. proof >
N 이하의 자연수들 중에서 적어도 하나의 소수로 나누어 떨어지는 수의 개수는 다음과 같다.표기가 약간 거시기한데, 의미는 대충 짐작 될 것이다. p₁이 어떤 특정한 소수를 가리키는 것이 아니라, 여러 개의 p들과 구분하기 위해 한 개짜리 소수의 의미로 인덱스를 붙인 것이다. N 이하의 모든 소수에 대해 싸그리 더한 것을 의미한다.

마찬가지로 N 이하의 자연수들 중에서 두 개의 소수로 나누어 떨어지는 수의 개수는 다음과 같다.마찬가지로 N 이하 두 소수의 쌍에 대해 싸그리 더했다는 의미이다. 세 개, 네 개의 경우도 마찬가지로 된다.

N 이하 두 자연수를 고르는 경우의 수는 N²이 되고, 이들 가운데 어느 소수 p₁을 인수로 공유하는 것은 [N/p₁]²이 된다. 고로 한 개의 인수를 공유하는 쌍의 개수는 다음과 같다.두 개, 세 개를 공유하는 쌍의 개수도 마찬가지가 된다.

여기서 포함-배제의 원리(Inclusion–exclusion principle)를 이용하여 다음 등식이 성립함을 알 수 있다.마지막 텀 ∏_N은 N 이하 서로 소인 쌍의 개수가 된다. 중간에 쩜쩜쩜 하며 생략했지만 이 합들은 본질적으로 모두 유한합이다.

∏_N을 제외한 나머지 항을 반대편으로 이항하여 양변을 N²으로 나누면 다음 식을 얻는다.마찬가지로 각 항도 유한합이고 텀의 개수도 유한이다. 여기서 N을 무한대로 보내는데, fact 1-2 때문에 성립하는 다음 등식을 활용한다.그러므로 우변은 다음과 같이 된다.

---

2009.12.24
참고
두 자연수가 서로소일 확률은? by 비상

---

2017.2.14
The probability that two random integers are relatively prime. in Algorithmic Mathematics