자연계열 3번

(가) 임의의 자연수 $\displaystyle n$이 주어졌을 때, $\displaystyle 1$부터 $\displaystyle n$까지의 ($\displaystyle 1$과 $\displaystyle n$을 포함한) 자연수 중 $\displaystyle n$과 서로 소인 자연수의 개수를 $\displaystyle \phi(n)$이라 하자. 이렇게 정의된 함수를 오일러의 $\displaystyle \phi$ 함수라 한다. 예를 들어, $\displaystyle 1$부터 $\displaystyle 10$까지의 자연수 중 $\displaystyle 10$과 서로 소인 수는 $\displaystyle 1$, $\displaystyle 3$, $\displaystyle 7$, $\displaystyle 9$ 이므로 $\displaystyle \phi(10)=4$ 이다. 또한, 오일러의 $\displaystyle \phi$ 함수는 다음 성질을 만족함이 알려져 있다.

(1) 임의의 서로 소인 두 자연수 $\displaystyle m$, $\displaystyle n$에 대하여,$\displaystyle \phi(mn)=\phi(m)\phi(n).$

(2) 임의의 소수 $\displaystyle p$와 자연수 $\displaystyle n$에 대하여,$\displaystyle \phi(p^n)=p^{n-1}(p-1).$

(나) 중심에 원두막이 있고 그림과 같이 가로 세로 $\displaystyle 1$미터 간격으로 나무를 심을 수 있는 과수원이 있다. 이곳에 매일 다음과 같은 방법으로 나무를 심는다.

위 그림과 같이, $\displaystyle n$번째 날에는 원두막을 중심으로 갖고 변의 길이가 $\displaystyle 2n$미터인 정사각형의 변 위에 나무를 심되 중심에서 보았을 때 이전에 심은 나무에 의해 가려지지 않는 위치에만 심는다. 이때 나무의 굵기는 무시할 수 있을 만큼 작다고 가정한다.