3. Zadatak

Prvo rješenje.

Vrijedi da je prirodan broj $d$ djelitelj od $n^{m+1}$ koji je veći od $n^m$ ako i samo ako je $\frac{n^{m+1}}d$ djelitelj od $n^{m+1}$ koji je manji od $n$. Dakle, imamo bijekciju između skupa djelitelja od $n^{m+1}$ većih od $n^m$ i skupa djelitelja od $n^{m+1}$ manjih od $n$, pa je $f_m(n)$ broj djelitelja od $n^{m+1}$ manjih od $n$.

Neka su $p_1,p_2,\ldots,p_k$ svi prosti faktori od $n$. Tvrdimo da je $f_m(n)$ za svaki $m\ge n$ jednak broju svih brojeva manjih od $n$ koji nemaju prostih faktora izvan skupa $\{p_1,p_2,\ldots,p_k\}$.

Naime, svaki djelitelj od $n^{m+1}$ mora imati samo te proste faktore. S druge strane, svaki broj dobiven umnošcima od $p_1,p_2,\ldots,p_k$ koji je manji od $n$ je manje od $n$ puta djeljiv svakim od $p_1,p_2,\ldots,p_k$ jer je $p_i^n\ge2^n>n$. Zaključujemo da svaki takav broj dijeli $n^{m+1}$ za $m\ge n$.

Posebno, za svaki $m\ge n$, $f_m(n)$ je broj elemenata istog skupa, pa je $f_m(n)=f_{m+1}(n)$.

Drugo rješenje.

Neka je $d$ djelitelj od $n^{m+1}$ veći od $n^m$. Tada je $nd$ djelitelj od $n^{m+2}$ veći od $n^{m+1}$. Time smo svakom djelitelju od $n^{m+1}$ većem od $n^m$ injektivno pridružili djelitelj od $n^{m+2}$ veći od $n^{m+1}$, pa je $f_m(n)\le f_{m+1}(n)$ za svaki $m\ge1$. Jednakost se postiže ako i samo ako je svaki djelitelj od $n^{m+2}$ koji je veći od $n^{m+1}$ ujedno djeljiv s $n$.

Dakle, treba dokazati da za svaki prirodan broj $m$ osim konačno mnogo njih vrijedi da je svaki djelitelj od $n^{m+1}$ koji je veći od $n^m$ djeljiv s $n$. Dokazat ćemo da to vrijedi za svaki $m\ge n$.

Pretpostavimo suprotno. Onda postoji djelitelj $d$ od $n^{m+1}$ veći od $n^m$ i prost broj $p$ koji dijeli $n$ takav da $p^k$ dijeli $n$ i $p^k$ ne dijeli $d$. Međutim, onda je $n^{m+1}$ djeljiv s $p^{(m+1)k}$ a $d$ nije djeljiv s $p^k$, pa je njihov omjer djeljiv s $p^{mk+1}$, pa je

$$n^{m+1}\ge d\cdot p^{mk+1}>d\cdot(mk+1)>dn>n^{m+1},$$

kontradikcija.