소수는 1과 자기 자신만을 약수로 갖는 수입니다. 정의에 의해서 1은 소수도 합성수에도 속하지 않지요. 가장 작은 소수는 2입니다.

2 = 2 X 1
3 = 3 x 1
5 = 5 x 1
7 = 7 x 1
…

반면에 소수가 아닌 합성수는 소수의 곱으로만 나타낼 수 있습니다. 예를 들어 합성수 4를 볼 것 같으면 소수인 2의 곱으로 나타낼 수 있지요.

4 = 2 x 2 (소수 2로 나누면 나머지는 0)

합성수 6을 볼까요? 역시 소수들의 곱으로 나타낼 수 있지요.

6 = 2 x 3 (소수 2나 3으로 나누면 나머지는 0)

합성수 500도 한 번 알아봅시다.

500 = 2 x 2 x 5 x 5 x 5 (소수 2나 5로 나누면 나머지는 0)

그러므로 어떠한 수가 특정 소수로 나누어서 나머지가 0이 된다면 그 수는 합성수라고 봐야 하는 거지요.

그런데 정말로 소수의 개수는 무한한 걸까요?

예를 들어서 수학자 “나수학”씨가 가장 큰 소수는 1327만 자릿수(숫자가 1327만이 아니라 자릿수가!!!)를 가진 한 특정한 수가 가장 큰 소수고 그 뒤로는 아무리 숫자가 늘어나도 소수는 나오지 않는다”라고 주장할 경우 우리는 어떻게 이를 반박해야 할까요?
1327만 자릿수의 해당 소수 이후로 소수가 하나라도 나오는 지 계속해서 점검해 보는 것은 한도 끝도 없는 어리석은 일일 것입니다.

그런데 유클리드가 아주 오래 전에 이를 멋있게 증명해 보였습니다.
아래는 유클리드가 소수의 무한성을 증명한 방법입니다.

소수의 개수가 유한하다고 가정해봅시다. 예를 들어 소수가

P1, P2, P3, P4, …, Pn

밖에 없고 가장 큰 소수 Pn 다음부터는 합성수들만 계속 나온다고 가정합니다.

이제 이 소수들을 다 곱해서 나오는 새로운 수를 N이라고 해봅시다.

N = P1 x P2 x P3 x P4 x … x Pn

N이 가장 큰 소수인 Pn 보다 큰 수라는 것은 자명합니다. 곱한 수들 가운데 가장 작은 수인 P1 만 해도 2 이니까요.

이제 N에다가 1을 더합니다.

N+1 = P1 x P2 x P3 x P4 x … x Pn + 1

제일 큰 소수가 Pn 이었는데 N+1은 Pn 보다 더 큰 수인 것은 당연합니다.
이 수가 합성수라면 정의에 의해서 어떤 특정한 소수로 나누었을 때 나머지가 0이 되어야 합니다.

그런데 N+1은 소수 P1 부터 Pn 까지 어떠한 소수로 나누어도 항상 나머지가 1이 남습니다.
1을 더하지 않았다면 나머지 없이 몫이 딱 떨어지는데 1이 더해짐으로서 항상 1이 남게 되지요...

소수 P1으로 나누면 나머지는 1이 남고
소수 P2로 나누면 나머지가 1이 남고
소수 P3으로 나누면 나머지가 1이 남고
…
소수 Pn으로 나누면 나머지가 1이 남습니다...

이 경우 N+1의 가능성은 두 가지 입니다.

1. N+1이 합성수가 아니라면 N+1은 소수이거나 아니면

2. N+1이 합성수라면 애초에 있던 리스트 (P1, P2, P3,...,Pn)의 소수가 아닌 다른 소수로 나누어 지는 수일 수 밖에 없고

어느 경우든 새로운 소수가 등장하게 되므로

그렇다면 아까 Pn 이 가장 큰 소수라는 주장(소수는 유한하다)은 깨어지게 되는 것입니다.