소수는 무한히 많다

수학 관련 첫 포스팅은 무조건 소수로 하자고 마음을 먹었기 때문에 가장 간단하면서도 흥미로운 문제를 선택했다.

명제 자체는 초등학생도 이해할 수 있을만큼 단순하다(사실 증명도 그렇다).

Theorem.

There are infinitely many primes.

이 단순한 명제의 증명은 사실 기원전 300년에 벌써 유클리드가 해냈다. 수학자들이 고대 그리스의 수학자들의 업적을 보고 있으면 그저 옛 수학자가 아니라 마치 현재 같이 일하는 동료처럼 느껴진다는 말이 있다. 그만큼 고대 그리스의 수학적 발전은 눈부셨다. 

유클리드의 간단한 증명을 보자.

Proof.

Suppose that p₁=2 < p₂ = 3 < ... < p_r are all of the primes. Let P = p₁p₂...p_r+1 and let p be a prime dividing P; then p can not be any of p₁, p₂, ..., p_r, otherwise p would divide the difference P-p₁p₂...p_r=1, which is impossible. So this prime p is still another prime, and p₁, p₂, ..., p_r would not be all of the primes.

간단히 말해 소수가 유한하다고 가정하고, 그 유한한 소수를 모두 곱한 뒤 1을 더한 수 P 는 현재 존재하는 소수들이 아닌 새로운 소수 p로 나눠져야만 한다는 뜻이다. 만약 P 자체가 새로운 소수라면 P =p가 된다. 이로써 처음 가정의 모순을 이끌어내 소수는 무한하다는 결론으로 귀결된다(이런 증명법을 귀류법이라한다).

Kummer라는 수학자가 이 증명을 조금 더 짧고 우아하게 restatement한 증명을 보자.

Proof.

Suppose that there exist only finitely many primes p₁ < p₂ < ... < p_r. Let N = p₁^.p₂^....^.p_r.   The integer N-1, being a product of primes, has a prime divisor p_i in common with N; so, p_i divides N - (N-1) =1, which is absurd!

마찬가지로 원하는 결과를 부정하고 시작해 모순을 이끌어내는 귀류법을 사용하지만 마무리가 약간 다르다. N을 모든 소수의 곱으로 만들면 N-1은 당연히 소수가 될 수 없으므로(소수는 자연수이기때문) 현재 존재하는 어떤 소수 p_i 로 나누어 떨어져야만 한다. 그런데 N은 모든 소수의 곱이라고 정의했으므로 역시 p_i 로 나눠 떨어진다.

정수는 소수로 unique factorization을 만들 수 있기 때문에 N과 N-1의 선형결합 N - (N-1) =1 역시 p_i 로 나눠 떨어진다. which is absurd, 모순이 발생해 증명이 마무리된다.

수학은 답이 정해져 있어도 그 목표에 도달하는 방법이 무한히 많기 때문에 매력적인 것 같다. 소수의 무한성을 증명하는 다른 증명들을 몇 개 더 소개하고 글을 마무리할까 한다.

Saidak의 증명(2005)

Proof.

Let n > 1 be a positive integer.  Since n and n+1 are consecutive integers, they must be coprime, and hence the number N₂ = n(n + 1) must have at least two different prime factors.  Similarly, since the integers n(n+1) and n(n+1)+1 are consecutive, and therefore coprime, the number N₃ = n(n + 1)[n(n + 1) + 1] must have at least 3 different prime factors.  This can be continued indefinitely.

Goldbach의 증명(1730) 이 증명은 특이하게 lemma(보조정리)를 하나 먼저 증명하고 본 증명에 들어간다. 조금 복잡하지만 고등학교 이상의 수학은 사용되지 않았다.

Lemma.

The Fermat numbers F_n =  are pairwise relatively prime.

Proof of Lemma.

It is easy to show by induction that F_m-2 = F₀^.F₁^....^.F_m-1.  This means that if d divides both F_n and F_m (withn < m), then d also divides F_m-2; so d divides 2.  But every Fermat number is odd, so d is one.

Proof of Thm.

Choose a prime divisor p_n of each Fermat number F_n.  By the lemma we know these primes are all distinct, showing there are infinitly many primes.

Note that any sequence that is pairwise relatively prime will work in this proof.  This type of sequence is easy to construct.  For example, choose relatively prime integers a and b, then define a_n as follows.

a₁=a,
a₂=a₁+b,
a₃=a₁a₂+b,
a₄=a₁a₂a₃+b,
...

This includes both the Fermat numbers (with a=1,b=2) and Sylvester's sequence (with a=1,b=2):

a₁=2 and a_n+1= a_n²-a_n+1.

In fact, the proof really only needs a sequence which has a subsequence which is pairwise relatively prime, e.g., the Mersenne numbers.

마지막으로 정말 특이하게도 topology를 사용해 정말 clever하게 증명을 한 Furstenverg의 증명이다(첫 u는 움라이트. 1955년에 증명되었다). 학부 위상수학을 들어야 간신히 이해가 된다.

Proof.

Define a topology on the set of integers by using the arithmetic progressions (from -infinity to +infinity) as a basis.  It is easy to verify that this yields a topological space.  For each prime p let A_p consists of all multiples of p.  A_p is closed since its complement is the union of all the other arithmetic progressions with difference p.  Now let A be the union of the progressions A_p.  If the number of primes is finite, then A is a finite union of closed sets, hence closed.  But all integers except -1 and 1 are multiples of some prime, so the complement of A is {-1, 1} which is obviously not open.  This shows A is not a finite union and there are infinitely many primes.