Školjka

%V0 Iz surjektivnosti znamo da postoji $x$ takav da $f(x)=1$. $f(x) \mid f(n)$ $\forall n \Rightarrow x \mid n$ $ \forall n \Rightarrow x=1$ Pokazimo prvo injektivnost. Pretpostavimo da $f(a)=f(b)$ Kako tada $f(a) \mid f(b)$ i $f(b) \mid f(a)$ vrijedi i $ a\mid b$ i $b \mid a$. Dakle $a=b$ Broj $f(p)$ mora imati tocno 2 djeljitelja (jedan od kojih je 1) za svaki prost broj $p$. Dakle $f(p)$ je prost. Pretpostavimo da vrijedi $f(p^n)=f^n(p)$ (baza indukcije ce biti $n=1$) $p^n \mid p^{n+1} \Rightarrow f^n(p) \mid f(p^{n+1})$ $f(p^{n+1})=kf^n(p)$ Iz uvjeta zadatka znamo da je $k=f^x(p)$ Ako je $x > 1$ tada postoji broj $a \neq 1,p,...,p^n$ takav da $f(a)=f^{n+1}(p)$ pa ocito $f(a) \mid f(p^{n+1}$ ali $a$ ne dijeli $p^{n+1})$ kontradikcija! Dakle $f(p^{n+1})=f^{n+1}(p)$ Pokazimo jos i da $f(a)=p$, $p$ prost implicira $a$ prost. (potrebno je samo pogledati broj djeljitelja brojeva $p$ i $a$) Sada pronadimo formulu za sve prirodne brojeve Ako $p^n \mid \mid a$ onda $f(a)=f^n(p)k$ uz $\gcd({k},{f(p)})=1$ Kako to vrijedi za svaki $p$ takav da $p \mid a$, dobivamo da je $f(a)=f(p_1^{\alpha_1}p_2^{\alpha_2}...p_n^{\alpha_n})=f^{\alpha_1}(p_1)...f^{\alpha_n}(p_n)$ Dakle, sada jos samo preostaje definirati $f(p)$ za sve proste $p$. Lagano provjerom dobiva se da za svaku bijektivnu funkciju $g: P \rightarrow P$ (gdje je skup $P$ skup prostih brojeva) i $f(p)=g(p)$ za sve proste $p$ zadatak vrijedi.