Prethodna tema :: Sljedeća tema |
Autor/ica |
Poruka |
dada Forumaš(ica)
Pridružen/a: 13. 12. 2008. (22:33:42) Postovi: (10)16
Lokacija: Sarajevo
|
|
[Vrh] |
|
dada Forumaš(ica)
Pridružen/a: 13. 12. 2008. (22:33:42) Postovi: (10)16
Lokacija: Sarajevo
|
|
[Vrh] |
|
duje Forumaš(ica)
Pridružen/a: 07. 11. 2002. (12:21:31) Postovi: (55C)16
Spol:
|
Postano: 22:11 čet, 26. 3. 2009 Naslov: Re: zadačić |
|
|
[quote="dada"]
Neka je p neparan prost broj.
Dokazati da kongurencija:
x na 4 kongurentno -1 po modulu p
ima riješenje akko je p=8k+1
[/quote]
Jedan smjer: Neka je x^4==-1 (mod p). Dignemo ovu kongruenciju na potenciju (p-1)/2, pa iz Malog Fermatovog teorema dobijemo 1==(x^(p-1))^2 == (-1)^((p-1)/2) (mod p). Odavde je (p-1)/2 paran, pa je (p-1)/4 prirodan broj. Sada dignemo polaznu kongruenciju na potenciju (p-1)/4, pa dobijemo 1==x^(p-1)==(-1)^((p-1)/4) (mod p). Zato je (p-1)/4 paran broj, tj. (p-1)/4=2k, odnosnp p=8k+1.
Drugi smjer: Neka je p=8k+1 prost broj, te neka je g primitivni korijen modulo p. Vrijedi g^((p-1)/2)==-1 (mod p). Zaista, neka je g^((p-1)/2)==a (mod p). Tada a nije kongruentno 1 modulo p i vrijedi a^2==1 (mod p), pa mora biti a==-1 (mod p). Sada je g^((p-1)/2)=g^(4k)=(g^k)^4, pa za x=g^k vrijedi x^4==-1 (mod p).
dada (napisa): |
Neka je p neparan prost broj.
Dokazati da kongurencija:
x na 4 kongurentno -1 po modulu p
ima riješenje akko je p=8k+1
|
Jedan smjer: Neka je x^4==-1 (mod p). Dignemo ovu kongruenciju na potenciju (p-1)/2, pa iz Malog Fermatovog teorema dobijemo 1==(x^(p-1))^2 == (-1)^((p-1)/2) (mod p). Odavde je (p-1)/2 paran, pa je (p-1)/4 prirodan broj. Sada dignemo polaznu kongruenciju na potenciju (p-1)/4, pa dobijemo 1==x^(p-1)==(-1)^((p-1)/4) (mod p). Zato je (p-1)/4 paran broj, tj. (p-1)/4=2k, odnosnp p=8k+1.
Drugi smjer: Neka je p=8k+1 prost broj, te neka je g primitivni korijen modulo p. Vrijedi g^((p-1)/2)==-1 (mod p). Zaista, neka je g^((p-1)/2)==a (mod p). Tada a nije kongruentno 1 modulo p i vrijedi a^2==1 (mod p), pa mora biti a==-1 (mod p). Sada je g^((p-1)/2)=g^(4k)=(g^k)^4, pa za x=g^k vrijedi x^4==-1 (mod p).
|
|
[Vrh] |
|
Gost
|
|
[Vrh] |
|
dada Forumaš(ica)
Pridružen/a: 13. 12. 2008. (22:33:42) Postovi: (10)16
Lokacija: Sarajevo
|
|
[Vrh] |
|
dada Forumaš(ica)
Pridružen/a: 13. 12. 2008. (22:33:42) Postovi: (10)16
Lokacija: Sarajevo
|
|
[Vrh] |
|
|