심화 격자점과 서로소

* 유클리드의 과수원

좌표평면에서 두 좌표가 모두 정수인 점을 격자점이라 한다.제1사분면의 모든 격자점에 나무를 심고 원점에서 바라본다고 하자. 나무의 굵기는 무시한다.

자연수 $\displaystyle a$, $\displaystyle b$에 대하여 $\displaystyle (a,b)$의 나무가 보이려면 선분 $\displaystyle \overline{OP}$의 양 끝점 사이에 다른 격자점이 없어야 한다. 여기서 $\displaystyle O$는 원점이고 $\displaystyle P(a,b)$이다.

$\displaystyle a$, $\displaystyle b$의 공약수 $\displaystyle d>1$이 있으면 $\displaystyle \left(\frac{a}{d},\frac{b}{d}\right)$도 격자점이다. 이 점의 나무가 $\displaystyle (a,b)$의 나무를 가린다.

* 격자점과 서로소

두 자연수 $\displaystyle a$, $\displaystyle b$의 최대공약수를 $\displaystyle d$라 하고 $\displaystyle a=du$, $\displaystyle b=dv$로 놓으면 $\displaystyle u$, $\displaystyle v$는 서로소이다.

직선 $\displaystyle OP$의 방정식은 $\displaystyle uy=vx$이다. 이 직선 위의 격자점에서는 $\displaystyle u$, $\displaystyle v$가 서로소이므로 $\displaystyle x$는 $\displaystyle u$의 배수이고, $\displaystyle x=ku$를 대입하면 $\displaystyle y=kv$이다.

따라서 선분 $\displaystyle \overline{OP}$ 위의 격자점은$\displaystyle (ku,kv)\quad(k=0,1,2,\ldots,d)$이고, 양 끝점을 제외하면 $\displaystyle d-1$개이다.

그러므로 원점에서 보이는 나무는 두 좌표가 서로소인 격자점에 있는 나무이다.

* 반사 경로에의 적용

한 변의 길이가 $\displaystyle 1$인 정사각형의 한 꼭짓점에서 내부로 빛을 쏜다고 하자. 빛은 변에서 입사각과 반사각이 같게 반사하며, 꼭짓점에 도달하면 멈춘다.

빛이 변에 닿을 때마다 그 변을 대칭축으로 정사각형을 뒤집어 이어 붙이면, 꺾인 경로를 하나의 직선으로 펼칠 수 있다.이때 정사각형의 꼭짓점들은 격자점이 된다.

출발점을 원점으로 놓고 두 변을 좌표축으로 잡자. 처음 진행하는 방향의 기울기가 $\displaystyle \frac{q}{p}$이고 $\displaystyle p$, $\displaystyle q$가 서로소인 자연수이면, 펼친 경로에서 원점을 떠난 뒤 처음 만나는 격자점은 $\displaystyle (p,q)$이다.

따라서 원래 정사각형의 꼭짓점에 처음 도달할 때까지 이동한 거리는$\displaystyle \sqrt{p^2+q^2}$이다.

* 선분이 지나는 정사각형의 개수

좌표평면을 한 변의 길이가 $\displaystyle 1$인 정사각형들로 나누자. 각 정사각형의 꼭짓점은 격자점이다.두 자연수 $\displaystyle a$, $\displaystyle b$에 대하여 $\displaystyle O(0,0)$, $\displaystyle P(a,b)$라 하고, 선분 $\displaystyle \overline{OP}$가 내부를 지나는 정사각형의 개수를 구해보자. 꼭짓점에 닿기만 하는 정사각형은 세지 않는다.

처음 들어가는 정사각형을 $\displaystyle 1$개로 세고, 격자선을 지날 때마다 새로운 정사각형으로 들어간다고 생각하면 된다.

선분의 양 끝점 사이에서 세로 격자선은 $\displaystyle a-1$개, 가로 격자선은 $\displaystyle b-1$개를 지난다.그런데 격자점을 지날 때는 세로선과 가로선을 동시에 지나지만 새로운 정사각형은 $\displaystyle 1$개만 늘어난다.

두 수 $\displaystyle a$, $\displaystyle b$의 최대공약수를 $\displaystyle d$라 하면, 양 끝점 사이의 격자점은 앞에서 구한 대로 $\displaystyle d-1$개이다.따라서 중복해서 센 횟수를 빼면 정사각형의 개수는$\displaystyle 1+(a-1)+(b-1)-(d-1)=a+b-d$이다.

특히 $\displaystyle a$, $\displaystyle b$가 서로소이면 지나는 정사각형은 $\displaystyle a+b-1$개이다.

앞의 반사 경로에서 $\displaystyle p$, $\displaystyle q$가 서로소이면 펼친 경로가 지나는 정사각형은 $\displaystyle p+q-1$개이다.따라서 출발점과 마지막 꼭짓점을 제외하고 변에서 반사하는 횟수는 $\displaystyle p+q-2$번이다.