| Prethodna tema :: Sljedeća tema |
| Autor/ica |
Poruka |
Gost
|
|
| [Vrh] |
|
duje
Forumaš(ica)
Pridružen/a: 07. 11. 2002. (12:21:31)
Postovi: (55C)16
Spol: 
|
 Postano: 21:40 sri, 18. 1. 2006 Naslov: Re: fi(n)=12 :) |
    |
|
|
[quote]Zanima me kako se rjesava sljedeci zadatak:
Odredite sve prirodne brojeve n tako da je fi(n)=12.
[/quote]
Broj n prikazemo kao produkt prostih faktora:
n=p_1^(a_1)*p_2^(a_2)...p_k^(a_k).
Znamo da je tada
phi(n)= p_1^(a_1-1)*(p_1-1)p_2^(a_2-1)*(p_2-1)...p_k^(a_k-1)(p_k-1).
Uocavamo da faktori (p_i - 1) moraju biti dijelitelji od phi(n), sto je u nasem slucaju 12. Faktori broja 12 su 1,2,3,4,6,12. Odavde su mogucnosti za p_i: 2,3,4,5,7,13, od kojih su prosti 2,3,5,7,13.
I sad se "na prste" promatraju preostale mogucnost. U skripti je dan pokusaj sistematiziranja tih preostalih mogucnosti tako da se potrebno racunanje minimizira.
Ako nesto u preostalom dijelu nije jasno, pitajte.
| Citat: | Zanima me kako se rjesava sljedeci zadatak:
Odredite sve prirodne brojeve n tako da je fi(n)=12.
|
Broj n prikazemo kao produkt prostih faktora:
n=p_1^(a_1)*p_2^(a_2)...p_k^(a_k).
Znamo da je tada
phi(n)= p_1^(a_1-1)*(p_1-1)p_2^(a_2-1)*(p_2-1)...p_k^(a_k-1)(p_k-1).
Uocavamo da faktori (p_i - 1) moraju biti dijelitelji od phi(n), sto je u nasem slucaju 12. Faktori broja 12 su 1,2,3,4,6,12. Odavde su mogucnosti za p_i: 2,3,4,5,7,13, od kojih su prosti 2,3,5,7,13.
I sad se "na prste" promatraju preostale mogucnost. U skripti je dan pokusaj sistematiziranja tih preostalih mogucnosti tako da se potrebno racunanje minimizira.
Ako nesto u preostalom dijelu nije jasno, pitajte.
|
|
| [Vrh] |
|
Gost
|
|
| [Vrh] |
|
duje
Forumaš(ica)
Pridružen/a: 07. 11. 2002. (12:21:31)
Postovi: (55C)16
Spol:
|
| Postano: 20:25 čet, 19. 1. 2006 Naslov: |
|
|
|
[quote]Taj prvi dio mi je sad jasan, a bilo bi super kad bi mogli drugi dio jos malo pojasniti :)
Kako bi se provelo to racunanje, bez pokusaja minimizacije racuna? Pomoglo bi da znam sve korake, mozda onda shvatim koji su nepostrebni.[/quote]
Iz onog prvog dijela znamo da je dovoljno promatrati samo brojeve oblika n=2^a*3^b*5^c*7^d*13^e. Razliciti slucajevi koje treba promatrati ovise o tome koji od brojeva a,b,c,d,e su razliciti od 0. Sto se tice nepotrebnih slucajeva, pogledajmo npr. sto se dogadja ako je e>0. Tada se u phi(n) pojavi faktor 12*13^(e-1), koji bi trebao biti djelitelj od 12. Sada je jasno da e mora biti jednak 1. K tome, ako onaj prestali faktor od n, tj.- n/13 oznacimo sa k, onda mora biti phi(k)*phi(13)=12.
To znaci da je phi(k)=1, sto povlaci da je k=1 ili k=2, a to daje dva rjesenja: n=13 i n=26.
Tako smo rijesili slucaj e>0, pa u daljnjem mozemo pretpostaviti da je e=0. Sada ovaj postupak nastavimo s brojem d. Ako je d>0, onda se u phi(n) pojavljuje faktor 6*7^(d-1) koji mora biti djelitelj od 12, sto povlaci da je d=1; gledamo preostali faktor n/7, itd.
| Citat: | Taj prvi dio mi je sad jasan, a bilo bi super kad bi mogli drugi dio jos malo pojasniti 
Kako bi se provelo to racunanje, bez pokusaja minimizacije racuna? Pomoglo bi da znam sve korake, mozda onda shvatim koji su nepostrebni. |
Iz onog prvog dijela znamo da je dovoljno promatrati samo brojeve oblika n=2^a*3^b*5^c*7^d*13^e. Razliciti slucajevi koje treba promatrati ovise o tome koji od brojeva a,b,c,d,e su razliciti od 0. Sto se tice nepotrebnih slucajeva, pogledajmo npr. sto se dogadja ako je e>0. Tada se u phi(n) pojavi faktor 12*13^(e-1), koji bi trebao biti djelitelj od 12. Sada je jasno da e mora biti jednak 1. K tome, ako onaj prestali faktor od n, tj.- n/13 oznacimo sa k, onda mora biti phi(k)*phi(13)=12.
To znaci da je phi(k)=1, sto povlaci da je k=1 ili k=2, a to daje dva rjesenja: n=13 i n=26.
Tako smo rijesili slucaj e>0, pa u daljnjem mozemo pretpostaviti da je e=0. Sada ovaj postupak nastavimo s brojem d. Ako je d>0, onda se u phi(n) pojavljuje faktor 6*7^(d-1) koji mora biti djelitelj od 12, sto povlaci da je d=1; gledamo preostali faktor n/7, itd.
Zadnja promjena: duje; 20:50 čet, 19. 1. 2006; ukupno mijenjano 1 put.
|
|
| [Vrh] |
|
Gost
|
|
| [Vrh] |
|
Gost
|
|
| [Vrh] |
|
duje
Forumaš(ica)
Pridružen/a: 07. 11. 2002. (12:21:31)
Postovi: (55C)16
Spol:
|
|
| [Vrh] |
|
Gost
|
|
| [Vrh] |
|
Gost
|
|
| [Vrh] |
|
duje
Forumaš(ica)
Pridružen/a: 07. 11. 2002. (12:21:31)
Postovi: (55C)16
Spol:
|
| Postano: 15:16 uto, 9. 1. 2007 Naslov: |
|
|
|
[quote]
ako smo stavili da je k=n/7 ili 13 ili 5 zasto je onda k oblika K=2 na nesto x 3 na nesto a ne primjerice ako je k=n/13 k=2 na nesto x 3 na nesto x 5 na nesto x 7 na nesto?
[/quote]
Nadam se da sam uspio razumiti pitanje. Recimo za k=n/7 vrijedi phi(k)=2, pa za svaki prosti faktor p_i od k, broj p_i-1 mora dijeli 2; zato je p_i = 2 ili 3.
[quote]
otkuda ako je phi(k)=2 dolazimo do toga da je K=3,4 ili 6?
[/quote]
U prethodnoj recenici je objasnjenje zasto su jedini moguci prosti faktori od k brojevi 2 i 3.
Ako je k=2^a, onda iz phi(k)=2^(a-1)=2 slijedi a=2, tj. k=4.
Ako je k=3^b, onda iz phi(k)=2*3^(b-1)=2 slijedi b=1, tj. k=3.
Ako je k=2^a*3^n, onda iz phi(k)=2*2^(a-1)*3^(b-1)=2 slijedi a=1,b=1, tj. k=6.
[quote]
odnosno za phi(k)=3 dobivamo da nema rjesenja
[/quote]
Moze se primijeniti isti postupak kao za phi(k)=2, a moze se iskoristiti i opca cinjenica da je za k>2 broj phi(k) paran.
To slijedi iz cinjenice da je (i,k)=1 akko (k-i,k)=1, pa brojevi relativno prosti s k "dolaze u parovima".
[quote]
da li ja jos unutar slucaja kada je (-1/p)=1 promatram p_ove oblika 4k+1 i 4k+3
[/quote]
Moze se valjda i tako reci. No, (-1/p)=1 akko je p=4k+1 (Teorem 2.14, Propozicija 3.3)
[quote]
i isto tako kada je (3/p)=1??pa znaci jos dobivan 2 nova slucaja...
[/quote]
Da.
[quote]
ili kad imam recimo za odrediti p-ove koji zadovoljavaju (2/p)=1
[/quote]
Po Teoremu 3.5, (2/p)=1 akko p=8k+1 ili p=8k+7.
| Citat: |
ako smo stavili da je k=n/7 ili 13 ili 5 zasto je onda k oblika K=2 na nesto x 3 na nesto a ne primjerice ako je k=n/13 k=2 na nesto x 3 na nesto x 5 na nesto x 7 na nesto?
|
Nadam se da sam uspio razumiti pitanje. Recimo za k=n/7 vrijedi phi(k)=2, pa za svaki prosti faktor p_i od k, broj p_i-1 mora dijeli 2; zato je p_i = 2 ili 3.
| Citat: |
otkuda ako je phi(k)=2 dolazimo do toga da je K=3,4 ili 6?
|
U prethodnoj recenici je objasnjenje zasto su jedini moguci prosti faktori od k brojevi 2 i 3.
Ako je k=2^a, onda iz phi(k)=2^(a-1)=2 slijedi a=2, tj. k=4.
Ako je k=3^b, onda iz phi(k)=2*3^(b-1)=2 slijedi b=1, tj. k=3.
Ako je k=2^a*3^n, onda iz phi(k)=2*2^(a-1)*3^(b-1)=2 slijedi a=1,b=1, tj. k=6.
| Citat: |
odnosno za phi(k)=3 dobivamo da nema rjesenja
|
Moze se primijeniti isti postupak kao za phi(k)=2, a moze se iskoristiti i opca cinjenica da je za k>2 broj phi(k) paran.
To slijedi iz cinjenice da je (i,k)=1 akko (k-i,k)=1, pa brojevi relativno prosti s k "dolaze u parovima".
| Citat: |
da li ja jos unutar slucaja kada je (-1/p)=1 promatram p_ove oblika 4k+1 i 4k+3
|
Moze se valjda i tako reci. No, (-1/p)=1 akko je p=4k+1 (Teorem 2.14, Propozicija 3.3)
| Citat: |
i isto tako kada je (3/p)=1??pa znaci jos dobivan 2 nova slucaja...
|
Da.
| Citat: |
ili kad imam recimo za odrediti p-ove koji zadovoljavaju (2/p)=1
|
Po Teoremu 3.5, (2/p)=1 akko p=8k+1 ili p=8k+7.
|
|
| [Vrh] |
|
Gost
|
|
| [Vrh] |
|
mirela11math
Forumaš(ica)
Pridružen/a: 17. 08. 2011. (17:33:53)
Postovi: (3)16
|
| Postano: 8:00 pon, 5. 9. 2011 Naslov: |
|
|
|
Imam pitanje vezano uz slučaj kada je phi(n)=24
Znači, prosti faktori su: {2,3,5,7,13}
Nadalje, n=13k, n=7k, n=5k, n=k
Zanima me korak kada je n = 7k... dobije se da je k=5, k=8, k=10, k=12.
Kako se dobilo da je k toliki?
Pokušala sam to shvatiti preko objašnjenog primjera 2.6 tj kada je phi(n)=12, no nisam bas uspjela...
Imam pitanje vezano uz slučaj kada je phi(n)=24
Znači, prosti faktori su: {2,3,5,7,13}
Nadalje, n=13k, n=7k, n=5k, n=k
Zanima me korak kada je n = 7k... dobije se da je k=5, k=8, k=10, k=12.
Kako se dobilo da je k toliki?
Pokušala sam to shvatiti preko objašnjenog primjera 2.6 tj kada je phi(n)=12, no nisam bas uspjela...
|
|
| [Vrh] |
|
duje
Forumaš(ica)
Pridružen/a: 07. 11. 2002. (12:21:31)
Postovi: (55C)16
Spol:
|
|
| [Vrh] |
|
mirela11math
Forumaš(ica)
Pridružen/a: 17. 08. 2011. (17:33:53)
Postovi: (3)16
|
|
| [Vrh] |
|
|
i p==3(mod 