소수 공장의 불량품
프로그램을 입력 몇 개로 돌려 보고 맞았다고, 모든 입력에 맞다고 할 수 있을까요? 테스트는 틀리는 입력을 찾아 줄 수는 있어도, 틀리는 입력이 없다는 것은 보여 주지 못합니다. 모든 경우에 옳다는 것을 확신하는 방법이 수학의 증명입니다.
참인지 거짓인지 분명하게 정해지는 문장을 명제(proposition)라 합니다. “7은 홀수다”는 참인 명제이고, “이 노래는 좋다”는 사람마다 답이 달라서 명제가 아닙니다.
명제의 예를 하나 들어 봅시다. 그러려면 소수가 필요합니다. 1과 자기 자신으로만 나누어떨어지는 1보다 큰 수를 소수(prime number)라 합니다. 2, 3, 5, 7이 소수이고 15는 3과 5로 나누어떨어지니 소수가 아닙니다.
“0 이상의 정수 n이 무엇이든 n² + n + 41은 소수다.” n = 0이면 41, n = 1이면 43, n = 2이면 47. 모두 소수입니다.
40번 연속으로 맞던 명제가 n = 40 하나 때문에 거짓이 됩니다. 이런 예를 반례(counterexample)라 합니다. 거짓임을 보이는 데는 반례 하나면 충분합니다.
반대로 참임을 보이기는 어렵습니다. n은 끝없이 많아서 전부 확인할 수 없으니, 하나하나 확인하지 않고도 모든 n에서 참임을 보이는 방법이 필요합니다.
“소수는 끝없이 많다”를 증명해 봅시다. 먼저 반대인 “소수는 개수가 정해져 있다”를 참이라고 가정합니다. 여기서 출발해 말이 안 되는 결론, 곧 모순에 도착하면 가정이 틀렸다는 뜻이고, 원래 명제가 참입니다. 이런 증명 방법을 귀류법(proof by contradiction)이라 합니다.
소수가 2, 3, 5뿐이라고 가정해 봅시다. 모두 곱하고 1을 더하면 31입니다.
31을 2, 3, 5 중 어느 것으로 나눠도 1이 남습니다. 목록의 소수로는 31이 나누어떨어지지 않습니다.
그런데 1보다 큰 수는 반드시 어떤 소수로 나누어떨어집니다. 소수가 아닌 수는 더 작은 두 수의 곱으로 쪼개지고, 쪼갠 수도 소수가 아니면 또 쪼개다 보면 결국 소수에 닿기 때문입니다. 31은 1과 31로만 나누어떨어지니 31 자신이 그런 소수입니다.
그런 소수는 목록에 없으니 소수가 2, 3, 5뿐이라는 가정과 맞지 않습니다. 이 논리는 목록에 어떤 소수가 있든 그대로 통하니, 소수를 모두 담은 목록은 있을 수 없습니다. 소수는 끝없이 많습니다.
소수를 골라 목록을 바꿔 봅시다. 여섯 개를 모두 골라도 됩니다.
컴퓨터공학에서 “그런 프로그램은 만들 수 없다”를 보일 때도 귀류법을 자주 씁니다.
“모든 경우에 참”이라는 명제는 반례 하나로 깨지고, 참임을 보이려면 귀류법처럼 경우를 하나씩 보지 않는 논리가 필요합니다. 다음 글에서는 n이 하나씩 커지는 명제를 도미노처럼 증명하는 수학적 귀납법을 다룹니다.
귀류법 증명에서는 목록의 소수를 모두 곱해 1을 더했습니다. 목록이 가장 작은 소수부터 빠짐없이 p까지(2, 3, 5, …, p)일 때, 그렇게 만든 수에 대해 다음 중 언제나 참인 것은 무엇일까요?