공측도와 무리수

‘알고리즘 산책’ 책 요약이다. 까먹지 않으려고 정리한다.

최대공측도는 최대공약수 같은 개념이다. 선분 A와 B가 특정한 길이로 측정이 가능할 때, 이 길이 중 가장 긴 길이를 최대공측도라고 하는 것이다. 이 값을 구하는 코딩 역시 최대공약수 계산과 다르지 않다. 여기서 공측도 값이 되는 선분 길이는 자연수이다.

그런데 19세기 조지 크리스털이 증명한 것은, 정사각형의 변과 대각선의 변을 동시에 측정할 수 있는 선분은 없다는 것이다. 왜일까? 귀류법을 통해, 정사각형의 변과 대각선의 변을 동시에 측정할 수 있는 선분이 있다고 가정하면 된단다. 여기 다 정리할 수는 없고 요약만 하자면, 동시에 측정할 수 있는 선분으로 그린 정사각형을 계속 생각하다 보면, 어느 순간 가장 작은 정사각형이 나올 것이다. 하지만 이 경우에도 선분이 있다고 가정해버리면, 더 작은 정사각형을 그릴 수 있게 되므로 모순이다.

그래서 대각선은 유리수가 아니라는 단서가 되었고, 무리수 \sqrt{2} 를 발견할 수 있었다.