‘알고리즘 산책’ 책 요약이다. 공측도라는 개념이나, 귀류법을 사용한 증명 등의 내용을 까먹지 않으려고 정리한다. 물론 이미 다 어릴 적 배웠겠지만, 다시 공부한다는 마음으로 정리하는 것이다.

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

그런데 19세기 조지 크리스털이 증명한 것은, 정사각형의 변과 대각선의 변을 동시에 측정할 수 있는 선분은 없다는 것이다. 왜일까? (다시 말하지만 공측도는 자연수이다.)

귀류법을 통해, 정사각형의 변과 대각선의 변을 동시에 측정할 수 있는 선분이 있다고 가정해보자. 요약하자면, 이 선분으로 정사각형을 그리고, 또 그 정사각형에서 한 변과 대각선을 측정할 수 있는 선분 (공측도) 이 있고, 계속 이런 식으로 정사각형을 그려나가다 보면, 어느 순간 가장 작은 정사각형이 나올 것이다. 하지만 가정에 따르면, 이 경우에도 대각선과 공측도가 되는 선분이 존재할 수 있게 된다. 그렇다면 더 작은 정사각형을 그릴 수 있게 되므로 모순이 생긴다.

그래서 대각선은 자연수가 아니라는 단서가 되었고, 이로 인해 무리수 $\sqrt{2}$ 를 발견할 수 있게 되었다고 한다.