[정보보안] Cardinality of Primes - 소수의 무한성 증명하기

가장 큰 소수보다 큰 수는 소수가 아니다.

합성수는 소수의 곱으로 나타낼 수 있다. 

 

N+1을 q의 배수라고 하면 모든 소수를 곱한 N도 q의 배수이다. 
(N+1 - N)도 q의 배수이다. 

-> 1은 q의 배수이다. 

 

따라서 q = 1인데 1은 정의에 의해서 소수가 아니다. 모순!