|
Evo nekih odgovora:
[quote]
ako su q=1 mod 4 i p=2q+1 prosti brojevi, dokažite da je 2 primitivni korijen modulo p[/quote]
Treba pokazati da 2^((p-1)/2) nije kongruentno 1 modulo p.
Kad bi bilo 2^((p-1)/2)==2^q == 1 (mod p), onda bi bilo 2^(q+1) == 2 (mod p), pa jer je q+1 paran, dobili bi da je 2 kvadratni ostatak modulo p. No, to bi povlacilo da je p==1 ili 7 (mod 8 ), sto je u kontradikciji s p=2q+1==3 (mod 8 ).
[quote]
neka su a,b prirodni brojevi, a neparan prost i p=a^2+5b^2 prost broj. Ako je a kvadratni ostatak modulo p dokažite da je p=1 (mod 5)[/quote]
Prvo se provjeri da je p==1 (mod 4). Dalje racumo s Legendreovim simbolima. Imamo da je 1=(a/p)=(p/a)=((a^2+5b^2)/a)=(5b^2/a)=(5/a)=(a/5). Stoga je a==1 ili 4 (mod 5), pa je a^2 == 1 (mod 5) i p=a^2+5b^2==1 (mod 5).
[size=9][color=#999999]Added after 17 minutes:[/color][/size]
[quote]pomoću indeksa riješite kongruenciju x^100=16(mod 43)
Tu me dosta buni kako da odredim primitivni korijen od modulo p
[/quote]
Ukratko: primitivni korijen modulo 43 je 3 (treba provjeriti da niti jedan od brojeva 3^21, 3^14, 3^6 ne daje ostatak 1 pri dijeljenju s 43; gledaju se prosti faktori od (43-1)=42, a to su 2,3,7, pa su zato eksponenti (43-1)/2=21, (43-1)/3=14 i (43-1)/7=6).
Za rjesenja kongruencije se dobije x == 4 i 39 (mod 43).
Evo nekih odgovora:
| Citat: |
ako su q=1 mod 4 i p=2q+1 prosti brojevi, dokažite da je 2 primitivni korijen modulo p |
Treba pokazati da 2^((p-1)/2) nije kongruentno 1 modulo p.
Kad bi bilo 2^((p-1)/2)==2^q == 1 (mod p), onda bi bilo 2^(q+1) == 2 (mod p), pa jer je q+1 paran, dobili bi da je 2 kvadratni ostatak modulo p. No, to bi povlacilo da je p==1 ili 7 (mod 8 ), sto je u kontradikciji s p=2q+1==3 (mod 8 ).
| Citat: |
neka su a,b prirodni brojevi, a neparan prost i p=a^2+5b^2 prost broj. Ako je a kvadratni ostatak modulo p dokažite da je p=1 (mod 5) |
Prvo se provjeri da je p==1 (mod 4). Dalje racumo s Legendreovim simbolima. Imamo da je 1=(a/p)=(p/a)=((a^2+5b^2)/a)=(5b^2/a)=(5/a)=(a/5). Stoga je a==1 ili 4 (mod 5), pa je a^2 == 1 (mod 5) i p=a^2+5b^2==1 (mod 5).
Added after 17 minutes:
| Citat: | pomoću indeksa riješite kongruenciju x^100=16(mod 43)
Tu me dosta buni kako da odredim primitivni korijen od modulo p
|
Ukratko: primitivni korijen modulo 43 je 3 (treba provjeriti da niti jedan od brojeva 3^21, 3^14, 3^6 ne daje ostatak 1 pri dijeljenju s 43; gledaju se prosti faktori od (43-1)=42, a to su 2,3,7, pa su zato eksponenti (43-1)/2=21, (43-1)/3=14 i (43-1)/7=6).
Za rjesenja kongruencije se dobije x == 4 i 39 (mod 43).
|
