유클리드의 증명 방식은 너무나 간단하고 유명하니 다른 증명을 소개해 보겠다. 

논리적으로 귀류법을 쓰는 건 비슷하다. 

1.소수가 유한하다고 해 보자.

그러면 모든 소수를 p_1, p_2, .... , p_n이라고 놓을 수 있다.

살짝 엄밀한 증명을 생략하고 싶다면, 바로 맨 밑에 노란색 바탕의 글만 읽으면 된다.

그러면 

모든 자연수는 (p_1^a)(p_2^b)....(p_n^z)   (a, b, ... z는 0 이상의 정수) 로 표현할 수 있다.    (만약 그렇게 표현할 수 없는 자연수가 있으면 그런 자연수 중에 최솟값 m을 찾을 수 있고, 그 m은 p_1, p_2, ..., p_n과 공약수가 1이어야 하므로, m보다 작은 자연수들과의 공약수도 1이어야 한다. 그리고 그 m의 약수는 m과 1 밖에 없다. 이때, 1은 (p_1^a)(p_2^b)....(p_n^z)   (a, b, ... z는 0 이상의 정수) 로 표현할 수 있으므로, m은 1이 아니다. 따라서 m의 약수는 2개이고, m은 소수여야 한다. 모순이다.)

그리고 (k=0에서 무한) ∑1/p_i^k 은 수렴한다.  (왜냐하면, p_i는 2 이상의 실수이기 때문이다.)

따라서, (∑1/p_1^k )(∑1/p_2^k).....(∑1/p_n^k) 은 수렴한다. 

이때, 여기서 

모든 항이 양수인 무한 급수가 수렴할 때는, 항의 순서를 자유롭게 바꿔도 (일대일 대응 함수를 이용해서 바꿈.) 그 급수는 수렴한다는 정리가 있다. 

그리고 (n은 0부터 무한)∑a_n 와 (b는 0부터 무한)∑b_n이 각각 모든 항이 양수이고 수렴할 때, AB=(n, m은 0 이상의 정수)∑a_n*b_m이라는 정리가 있다.

(특히, 각 항의 절댓값들을 더해도 수렴하는 경우를 절대수렴한다고 한다. 위의 정리에서 모든 항이 양수이고, 수렴한다는 조건을 그냥 절대 수렴이라고 바꿔도 된다.)

그러면,  

(∑1/p_1^k )(∑1/p_2^k)= (a, b는 0 이상의 정수) ∑1/( (p_1^a)(p_2^b) )

(∑1/p_1^k )(∑1/p_2^k)(∑1/p_3^k)=∑1/( (p_1^a)(p_2^b) ) * (∑1/p_3^k) =(a, b, c는 0 이상의 정수) ∑1/( (p_1^a)(p_2^b)....(p_n^c) )

.

.

.

(∑1/p_1^k )(∑1/p_2^k).....(∑1/p_n^k)= (a, b, ... z는 0 이상의 정수) ∑1/( (p_1^a)(p_2^b)....(p_n^z) )   가 성립한다. 

만약 (a, b, ... z는 0 이상의 정수)를 ∑의 index로 놓는 게 불편하다면,  (a=0에서 무한)∑(b=0에서 무한)∑......(z=0에서 무한0)∑1/( (p_1^a)(p_2^b)....(p_n^z) ) 이라고 놓아도 된다. 

이때, 모든 자연수는 (p_1^a)(p_2^b)....(p_n^z)   (a, b, ... z는 0 이상의 정수) 로 표현할 수 있다.  

따라서 

 (∑1/p_1^k )(∑1/p_2^k).....(∑1/p_n^k)= (a, b, ... z는 0 이상의 정수) ∑1/( (p_1^a)(p_2^b)....(p_n^z) ) =1+1/2+1/3+1/4+..... =∑1/k 이다. 

 (∑1/p_1^k )(∑1/p_2^k).....(∑1/p_n^k)=∑1/k 이 성립하고 여기서

(참고로 우변은 조화 급수라고 한다.)

우변은 무한으로 발산하고, 좌변은 하나의 실수값으로 수렴한다.  모순이다. 

따라서 소수는 무한하다.