서문

소수는 그 양의 약수가 1과 자기 자신 이외에 존재하지 않고 1보다 큰 양의 정수이다. 예컨대, 7의 양의 약수는 1과 7이고 그 밖에 양의 약수는 존재하지 않으므로 7은 소수이다. 한편, 3은 57 = 3·19 의 양의 약수이다. 57은 소수가 아니다. 1보다 크고 소수가 아닌 양의 정수를 합성수라고 부른다. 57은 합성수이다.

소수는 무한히 많이 존재한다. 이 사실을 소수의 무한성^{infinitude of primes}이라고 부른다. 이 글은 소수의 무한성의 여러가지 증명에 대해 소개한다.

유클리드^Euclid의 증명

결론을 부정하여 소수의 무한성이 거짓이라고 가정하자. 를 모든 소수로 이루어진 의 부분집합이라고 하자. 모든 소수의 곱에 1을 더한 수

를 생각하자. 는 유한집합이므로 는 잘 정의된다. 모든 에 대해

이므로, 는 에 포함되지 않는다. 를 의 소수인 양의 약수라고 하자. 는 모든 의 원소 에 대해, 를 로 나누었을 때 나머지가 1이 남고, 1은 의 배수가 아니므로 는 의 약수가 아니다. 따라서 인데, 이는 보조정리에 의해 가 소수가 되어야 한다는 점과 모순이다. 따라서 소수의 무한성은 참이다.

에르되시^Erdős의 증명

수열 에는 모든 소수가 정확히 한 번씩 등장하고, 임의의 에 대해 를 만족한다고 하자. 만약 소수의 무한성이 거짓이어서 소수가 정확히 개 존재할 경우, 모든 에 대해 로 정의하자. 으로 정의하자.

모든 소수 역수의 합 무한합 는 발산한다.

증명 결론을 부정하여 이 실수 에 수렴한다고 가정하자. 를 만족하는 가장 작은 정수 를 선택하자. 이므로 , 특히 임을 관찰하자. 또한 조건에서 의 최소성에 의해 번째 소수 는 존재하고, 특히 임을 관찰하자. 양의 정수 에 대해, 보다 작거나 같은 양의 정수 중 그 소인수분해 가 와 같이 나타나는 것들의 개수와 관련된 부등식을 세우고 이에서 모순을 이끌어낼 것이다. 소인수분해가 위 조건과 같이 나타나는 의 원소를 좋은 수라고 하자. 의 원소 중 좋은 수가 아닌 것을 나쁜 수라고 하자.

• 의 원소 중 좋은 수의 개수는 많아야 이다. 를 선택하는 경우의 수는 이다. 소인수분해로 를 갖는 수를 각각 라고 할 때, 을 만족하므로 각 에 대해 좋은 수는 많아야 개 존재한다.
• 의 원소 중 나쁜 수의 개수는 많아야 이다. 에 대해, 의 원소 중 의 배수는 개 존재한다. 어떤 정수가 나쁜 수라는 것은 어떤 에 대해 이 홀수인 것과 동치이고, 이때 그 수는 의 배수가 된다. 따라서 나쁜 수들의 부분집합은 에 대해 의 배수의 부분집합의 합집합에 속하게 된다. 합집합 상한을 사용하면 나쁜 수의 개수에 대한 상한 을 얻는다.

좋은 수의 부분집합과 나쁜 수의 부분집합의 합집합은 이므로, 부등식 을 얻는다. 이를 정리하면 인데, 이는 명백히 어떤 양의 정수에 대해 성립하지 않는 부등식이다. 을 선택하여 위 논증을 반복하면 모순을 얻게 되므로, 무한합 가 수렴한다는 가정은 잘못되었다. 따라서 무한합 은 발산한다.

퍼스턴버그^Furstenberg의 증명

위상수학을 사용한 이 증명은 수학자 퍼스턴버그가 학부생 때 떠올렸다고 전해진다.

집합 에 대해 의 부분집합을 원소로 갖는 집합 가 다음 조건을 만족할 때, 을 의 위상^topology이라고 한다.

2. 임의의 집합 에 대해, 이면 이다.
3. 임의의 양의 정수 에 대해, 이면 이다.

인 의 부분집합 을 열린집합이라고 한다. 인 의 부분집합 를 닫힌집합이라고 한다.

, 에 대해 으로 정의한다. 임의의 첨수 집합 과 , 에 대해 으로 표현가능한 를 원소로 갖는 의 부분집합들의 집합 을 정의할 수 있다.

가 위상임을 보이자.

1. 일 때 는 빈 합집합이므로 이다. , , 일 때 으로 이다.

2. 에 대해 라고 하자. 일 때 는 집합이고 이다.

3. 는 공집합이거나, 어떤 정수 에 대해 와 같다.

   • 가 공집합이라면, 그냥 공집합이다.
   • 가 공집합이 아니라면, 를 이 집합의 원소라고 하고, 는 의 최소공배수라고 하자. 이때 임을 보이자. 이면 어떤 정수 에 대해 이다. 이므로 는 의 배수이고, 따라서 의 배수이다. 를 만족하는 정수 가 존재하므로 이고, 따라서 이다. 이면 , 이므로 이고 이다.

   두 경우 모두 는 의 열린 집합이다. 두 열린 집합 , 의 교집합 는 열린 집합이다.

이 위상에서 부분집합 가 열린집합임과 닫힌집합임은 동치이다. 또한, 공집합이 아닌 열린집합은 항상 무한집합이다. 소인수분해의 존재에 의해, 이다. 은 유한집합이므로 열린집합이 아니고, 특히 은 닫힌집합이 아니다. 가 유한하다고 가정하면 좌변은 닫힌집합의 유한합집합이므로 닫힌집합이고, 이때 등식은 닫힌집합과 닫히지 않은 집합이 같음을 의미하므로 (즉 어떤 집합 에 대해 와 를 동시에 함의하므로) 모순이다.