Točno
9. veljače 2013. 17:52 (11 godine, 5 mjeseci)
Upozorenje: Ovaj zadatak još niste riješili!
Kliknite ovdje kako biste prikazali rješenje.
Kliknite ovdje kako biste prikazali rješenje.
Iz surjektivnosti znamo da postoji
takav da
.
Pokazimo prvo injektivnost.
Pretpostavimo da![f(a)=f(b)](/media/m/b/2/d/b2d2f062ee54daad8c67ed47ddddfc7a.png)
Kako tada
i
vrijedi i
i
. Dakle ![a=b](/media/m/a/9/2/a92b57ffecf4f08b70899188d461ba5f.png)
Broj
mora imati tocno 2 djeljitelja (jedan od kojih je 1) za svaki prost broj
. Dakle
je prost.
Pretpostavimo da vrijedi
(baza indukcije ce biti
)
![p^n \mid p^{n+1} \Rightarrow f^n(p) \mid f(p^{n+1})](/media/m/b/2/1/b215044c67cfa33d918a6f5dd171735d.png)
![f(p^{n+1})=kf^n(p)](/media/m/7/f/d/7fd698d17d640f2407fdb7fe1a79e0dc.png)
Iz uvjeta zadatka znamo da je![k=f^x(p)](/media/m/4/a/4/4a431a466c304543120da426619c7024.png)
Ako je
tada postoji broj
takav da
pa ocito
ali
ne dijeli
kontradikcija!
Dakle![f(p^{n+1})=f^{n+1}(p)](/media/m/a/5/2/a52ec02adf32f03f8d95ca0e9bf5525f.png)
Pokazimo jos i da
,
prost implicira
prost. (potrebno je samo pogledati broj djeljitelja brojeva
i
)
Sada pronadimo formulu za sve prirodne brojeve
Ako
onda
uz ![\gcd({k},{f(p)})=1](/media/m/e/c/8/ec825c345ca4e1b97d5fbc839a6ccc62.png)
Kako to vrijedi za svaki
takav da
, 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)](/media/m/2/b/5/2b5f08314b9605fa83aeb99765bbc7ae.png)
Dakle, sada jos samo preostaje definirati
za sve proste
. Lagano provjerom dobiva se da za svaku bijektivnu funkciju
(gdje je skup
skup prostih brojeva) i
za sve proste
zadatak vrijedi.
![x](/media/m/f/1/8/f185adeed9bd346bc960bca0147d7aae.png)
![f(x)=1](/media/m/5/6/8/5685983392512f8e884b5d13250f697f.png)
![f(x) \mid f(n)](/media/m/d/a/a/daa0bb5b81e792833a14272b1cc4dce0.png)
![\forall n \Rightarrow x \mid n](/media/m/6/0/2/602ad83b94401611a3e565d076048d8f.png)
![\forall n \Rightarrow x=1](/media/m/7/8/9/789194a330056f3064c96f21a9c3e8a3.png)
Pokazimo prvo injektivnost.
Pretpostavimo da
![f(a)=f(b)](/media/m/b/2/d/b2d2f062ee54daad8c67ed47ddddfc7a.png)
Kako tada
![f(a) \mid f(b)](/media/m/4/a/2/4a221390e8f9a2bb4e5f6e06787f6101.png)
![f(b) \mid f(a)](/media/m/c/7/6/c76ad90fd6381bbfa667b360360ebe58.png)
![a\mid b](/media/m/e/3/c/e3cedf8012f017366aa16aa65bde12aa.png)
![b \mid a](/media/m/f/f/0/ff057fad343ad9f07398e6f79af0281d.png)
![a=b](/media/m/a/9/2/a92b57ffecf4f08b70899188d461ba5f.png)
Broj
![f(p)](/media/m/3/2/c/32cf34b61b038dfc952696fb002b4e8b.png)
![p](/media/m/1/c/8/1c85c88d10b11745150467bf9935f7de.png)
![f(p)](/media/m/3/2/c/32cf34b61b038dfc952696fb002b4e8b.png)
Pretpostavimo da vrijedi
![f(p^n)=f^n(p)](/media/m/2/b/d/2bd31ef84e664131304b7f3f0181be29.png)
![n=1](/media/m/4/e/4/4e466fe58c2a8f6389234c5c673f069c.png)
![p^n \mid p^{n+1} \Rightarrow f^n(p) \mid f(p^{n+1})](/media/m/b/2/1/b215044c67cfa33d918a6f5dd171735d.png)
![f(p^{n+1})=kf^n(p)](/media/m/7/f/d/7fd698d17d640f2407fdb7fe1a79e0dc.png)
Iz uvjeta zadatka znamo da je
![k=f^x(p)](/media/m/4/a/4/4a431a466c304543120da426619c7024.png)
Ako je
![x > 1](/media/m/d/1/0/d10f790752364f9d9315a207e2741ec0.png)
![a \neq 1,p,...,p^n](/media/m/d/b/d/dbd21fb8495dfeb5c138f1ea48a96f4d.png)
![f(a)=f^{n+1}(p)](/media/m/a/b/d/abdc98f3477a117092ffc6757564f6a4.png)
![f(a) \mid f(p^{n+1}](/media/m/9/2/8/9289fc3fe246e37604ca4b14f9048400.png)
![a](/media/m/6/d/2/6d2832265560bb67cf117009608524f6.png)
![p^{n+1})](/media/m/4/a/8/4a859f2807ad6346ec1f1c463965b887.png)
Dakle
![f(p^{n+1})=f^{n+1}(p)](/media/m/a/5/2/a52ec02adf32f03f8d95ca0e9bf5525f.png)
Pokazimo jos i da
![f(a)=p](/media/m/9/0/e/90e7fc1b1f7b240e84e6b28b79ea7b39.png)
![p](/media/m/1/c/8/1c85c88d10b11745150467bf9935f7de.png)
![a](/media/m/6/d/2/6d2832265560bb67cf117009608524f6.png)
![p](/media/m/1/c/8/1c85c88d10b11745150467bf9935f7de.png)
![a](/media/m/6/d/2/6d2832265560bb67cf117009608524f6.png)
Sada pronadimo formulu za sve prirodne brojeve
Ako
![p^n \mid \mid a](/media/m/2/4/f/24f06cc3d73a7b04f48e97d89c35f143.png)
![f(a)=f^n(p)k](/media/m/3/c/8/3c8e776e3d6ce3afcb1094b4122f27d0.png)
![\gcd({k},{f(p)})=1](/media/m/e/c/8/ec825c345ca4e1b97d5fbc839a6ccc62.png)
Kako to vrijedi za svaki
![p](/media/m/1/c/8/1c85c88d10b11745150467bf9935f7de.png)
![p \mid a](/media/m/e/8/9/e8970236a61e5731b31a62baf6e741d8.png)
![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)](/media/m/2/b/5/2b5f08314b9605fa83aeb99765bbc7ae.png)
Dakle, sada jos samo preostaje definirati
![f(p)](/media/m/3/2/c/32cf34b61b038dfc952696fb002b4e8b.png)
![p](/media/m/1/c/8/1c85c88d10b11745150467bf9935f7de.png)
![g: P \rightarrow P](/media/m/2/a/c/2acc9b177849ae2fbe2c925d7a2dc854.png)
![P](/media/m/9/6/8/968d210d037e7e95372de185e8fb8759.png)
![f(p)=g(p)](/media/m/c/9/1/c91f351f8c307a5d42c2ba160bfd0a57.png)
![p](/media/m/1/c/8/1c85c88d10b11745150467bf9935f7de.png)