자연계열 3번

[문제 3-1] $\displaystyle d=\gcd(n,2025)$라 하고 $\displaystyle n=du$, $\displaystyle 2025=dv$라 하면 $\displaystyle u$와 $\displaystyle v$는 서로소이다.$\displaystyle nk$가 $\displaystyle 2025$의 배수일 필요충분조건은 $\displaystyle uk$가 $\displaystyle v$의 배수인 것이다.$\displaystyle u$와 $\displaystyle v$가 서로소이므로 이는 $\displaystyle k$가 $\displaystyle v$의 배수인 것과 같다.따라서 가장 작은 자연수 $\displaystyle k$는 $\displaystyle v$이므로$\displaystyle f(n)=\frac{2025}{\gcd(n,2025)}$이다.

$\displaystyle 2025=3^{4}5^{2}$이고 $\displaystyle n=3^{\alpha}5^{\beta}m$이라 하자.여기서 $\displaystyle \alpha$, $\displaystyle \beta$는 음이 아닌 정수이고 $\displaystyle m$은 $\displaystyle 15$와 서로소인 자연수이다.$\displaystyle a$와 $\displaystyle b$ 중 크지 않은 값을 $\displaystyle \min(a,b)$라 하면$\displaystyle \begin{aligned}\gcd(n,2025)&=3^{\min(\alpha,4)}5^{\min(\beta,2)}\\\gcd(n^{2},2025)&=3^{\min(2\alpha,4)}5^{\min(2\beta,2)}\end{aligned}$따라서 $\displaystyle f(n)=f(n^{2})$일 필요충분조건은$\displaystyle \alpha=0\text{ 또는 }\alpha\ge4,\qquad\beta=0\text{ 또는 }\beta\ge2$이다.

$\displaystyle 1\le n\le2025$에서(i) $\displaystyle 3$의 배수도 $\displaystyle 5$의 배수도 아닐 때: $\displaystyle 2025-675-405+135=1080$개(ii) $\displaystyle 81$의 배수이면서 $\displaystyle 5$의 배수가 아닐 때: $\displaystyle 25-5=20$개(iii) $\displaystyle 25$의 배수이면서 $\displaystyle 3$의 배수가 아닐 때: $\displaystyle 81-27=54$개(iv) $\displaystyle 81$과 $\displaystyle 25$의 공배수일 때: $\displaystyle n=2025$의 $\displaystyle 1$개이 네 경우는 서로 겹치지 않으므로 구하는 개수는$\displaystyle 1080+20+54+1=1155$이다.

[문제 3-2] 다시 $\displaystyle d=\gcd(n,2025)$라 하자.$\displaystyle d$는 $\displaystyle n$과 $\displaystyle 2025$의 최대공약수이므로 $\displaystyle 2025=dq$로 둘 수 있고,이때 $\displaystyle q=2025/d$는 $\displaystyle 2025$의 약수이다.앞에서 구한 식에 따라 $\displaystyle f(n)=q$이다.$\displaystyle q$가 $\displaystyle 2025$의 약수이므로 $\displaystyle q$와 $\displaystyle 2025$의 최대공약수는 $\displaystyle q$ 자체이다.따라서$\displaystyle \begin{aligned}f(f(n))&=\frac{2025}{\gcd(q,2025)}\\&=\frac{2025}{q}=d=\gcd(n,2025)\end{aligned}$이다.

$\displaystyle d=\gcd(n,2025)$는 $\displaystyle n$의 약수이므로어떤 자연수 $\displaystyle m$에 대하여 $\displaystyle n=dm$으로 쓸 수 있다.따라서 $\displaystyle d\le n$이고,$\displaystyle d=n$인 경우는 $\displaystyle m=1$, 즉 $\displaystyle n=d$인 경우이다.그런데 $\displaystyle d=\gcd(n,2025)$이므로$\displaystyle n=d$일 필요충분조건은 $\displaystyle n$이 $\displaystyle 2025$의 약수인 것이다.따라서 $\displaystyle f(f(n))<n$일 필요충분조건은 $\displaystyle n$이 $\displaystyle 2025$의 약수가 아닌 것이다.

$\displaystyle 2025=3^{4}5^{2}$의 양의 약수는 $\displaystyle (4+1)(2+1)=15$개이다.따라서 구하는 자연수의 개수는$\displaystyle 2025-15=2010$이다.