| 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:20 sri, 18. 1. 2006 Naslov: Re: kongruencije |
    |
|
|
[quote]kako se rješavaju kongruencije tipa 5*x^4==3(mod 11)
[/quote]
Lijeva i desna strana kongruencije se "logaritmiraju" (to u ovoj situaciji zovemo "indeksiraju"). Za razliku od obicnog logaritmiranja gdje je skoro svaka baza logaritma dobra, ovdje za bazu moramo uzeti neki primitivni korijen. Za naci primitivni korijen preporuca se provjeravati redom 2,3,5,6,7,10, ... (sve prirodne brojeve koji nisu potencije). Ovdje se dobije (vidi primjer 2.12) je vec broj 2 primitivni korijen (to nije slucajno - po Artinovoj slutnji, dogodit ce se u oko 37% slucajeva).
Sada se lijeva i desna strana indeksiraju po bazi 2. Kod indeksiranja vrijede ista pravila za logaritam produkta i logaritam potencije.
Dakle, dobije se ind_2(5)+4*ind_2(x) == ind_2(3) (mod 10). Uocite da se modul promijenio. Opcenito, umjesto (mod n), imamo (mod phi(n)).
Nadalje, ind_2(5)=4, jer je 2^4==5 (mod 11), a ind_2(5) je potencija s kojom treba potencirati bazu 2 da se dobije 5 (mod 11). Slicno je ind_2(3) = 8, jer je 2^8==3 (mod 11).
Uvrstavanjem dobijemo kongruenciju
4*ind_2(x) == 4 (mod 10). To je kongruencija s jednom nepoznanicom ind_2(x). Uvedimo oznaku y=ind_2(x), pa je kongruencija 4*y == 4 (mod 10). Modul 10 je tako mali da ovu kongruenciju mozemo rijesiti tako da uvrstimo redom y=0,1,2,...,9. Opcenito, postupamo po pravilu za rijesavanje linearnih kongruencija. Imamo da je najveci zajednicki djelitelj (4,10)=2, a 2 dijeli 4, pa imamo dva rjesenja. Podijelimo sa 2,
pa dobijemo 2*y==2 (mod 5). Sada bi u opcem slucaju primjenili Euklidov algoritam. U ovom konkretnom slucaju je ocito da je rjesenje y==1 (mod 5). Nama trebaju rjesenja (mod 10), a to su 1 i 1+5, tj. ind_2(x) =1 , 6 (mod 10). Konacno (kao i u slucaju obicnih logaritama), x dobijemo po formuli x=2^y (mod 11) (uocite da je modul ponovo 11, tj. n). Dobijemo rezultat da je x == 2^1 == 2 (mod 11) ili x == 2^6 == 9 (mod 11).
Nadam se da sam uspio malo pojasniti.
| Citat: | kako se rješavaju kongruencije tipa 5*x^4==3(mod 11)
|
Lijeva i desna strana kongruencije se "logaritmiraju" (to u ovoj situaciji zovemo "indeksiraju"). Za razliku od obicnog logaritmiranja gdje je skoro svaka baza logaritma dobra, ovdje za bazu moramo uzeti neki primitivni korijen. Za naci primitivni korijen preporuca se provjeravati redom 2,3,5,6,7,10, ... (sve prirodne brojeve koji nisu potencije). Ovdje se dobije (vidi primjer 2.12) je vec broj 2 primitivni korijen (to nije slucajno - po Artinovoj slutnji, dogodit ce se u oko 37% slucajeva).
Sada se lijeva i desna strana indeksiraju po bazi 2. Kod indeksiranja vrijede ista pravila za logaritam produkta i logaritam potencije.
Dakle, dobije se ind_2(5)+4*ind_2(x) == ind_2(3) (mod 10). Uocite da se modul promijenio. Opcenito, umjesto (mod n), imamo (mod phi(n)).
Nadalje, ind_2(5)=4, jer je 2^4==5 (mod 11), a ind_2(5) je potencija s kojom treba potencirati bazu 2 da se dobije 5 (mod 11). Slicno je ind_2(3) = 8, jer je 2^8==3 (mod 11).
Uvrstavanjem dobijemo kongruenciju
4*ind_2(x) == 4 (mod 10). To je kongruencija s jednom nepoznanicom ind_2(x). Uvedimo oznaku y=ind_2(x), pa je kongruencija 4*y == 4 (mod 10). Modul 10 je tako mali da ovu kongruenciju mozemo rijesiti tako da uvrstimo redom y=0,1,2,...,9. Opcenito, postupamo po pravilu za rijesavanje linearnih kongruencija. Imamo da je najveci zajednicki djelitelj (4,10)=2, a 2 dijeli 4, pa imamo dva rjesenja. Podijelimo sa 2,
pa dobijemo 2*y==2 (mod 5). Sada bi u opcem slucaju primjenili Euklidov algoritam. U ovom konkretnom slucaju je ocito da je rjesenje y==1 (mod 5). Nama trebaju rjesenja (mod 10), a to su 1 i 1+5, tj. ind_2(x) =1 , 6 (mod 10). Konacno (kao i u slucaju obicnih logaritama), x dobijemo po formuli x=2^y (mod 11) (uocite da je modul ponovo 11, tj. n). Dobijemo rezultat da je x == 2^1 == 2 (mod 11) ili x == 2^6 == 9 (mod 11).
Nadam se da sam uspio malo pojasniti.
|
|
| [Vrh] |
|
Gost
|
|
| [Vrh] |
|
ta2a
Forumaš(ica)
Pridružen/a: 01. 09. 2004. (12:59:54)
Postovi: (B4)16
Spol: 
Lokacija: zg
|
|
| [Vrh] |
|
vinko
Forumaš(ica)
Pridružen/a: 26. 08. 2006. (23:08:00)
Postovi: (1A8)16
Spol:
Lokacija: PMF-MO 214
|
|
| [Vrh] |
|
ta2a
Forumaš(ica)
Pridružen/a: 01. 09. 2004. (12:59:54)
Postovi: (B4)16
Spol:
Lokacija: zg
|
|
| [Vrh] |
|
hermione
Forumaš(ica)
Pridružen/a: 23. 09. 2003. (10:50:57)
Postovi: (152)16
Spol: 
Sarma: -
|
|
| [Vrh] |
|
ta2a
Forumaš(ica)
Pridružen/a: 01. 09. 2004. (12:59:54)
Postovi: (B4)16
Spol:
Lokacija: zg
|
|
| [Vrh] |
|
hermione
Forumaš(ica)
Pridružen/a: 23. 09. 2003. (10:50:57)
Postovi: (152)16
Spol:
Sarma: -
|
|
| [Vrh] |
|
vinko
Forumaš(ica)
Pridružen/a: 26. 08. 2006. (23:08:00)
Postovi: (1A8)16
Spol:
Lokacija: PMF-MO 214
|
| Postano: 11:59 uto, 16. 1. 2007 Naslov: |
|
|
|
[quote="ta2a"]a kako bi se onda rješilo ovo:
x^2 + x + 47 == 0 (mod 7)
to je primjer iz skripte i rješenja su x==1(mod 7) i x==5(mod 7), al ja nikak nemrem skužit kak se to izračuna :([/quote]
U ovome zadatku to možemo izračunati 'na prste', uvrštavajući za x redom 0, 1, 2, ..., 6 i vidimo koji x-evi zadovoljavaju jednadžbu.
| ta2a (napisa): | a kako bi se onda rješilo ovo:
x^2 + x + 47 == 0 (mod 7)
to je primjer iz skripte i rješenja su x==1(mod 7) i x==5(mod 7), al ja nikak nemrem skužit kak se to izračuna  |
U ovome zadatku to možemo izračunati 'na prste', uvrštavajući za x redom 0, 1, 2, ..., 6 i vidimo koji x-evi zadovoljavaju jednadžbu.
|
|
| [Vrh] |
|
vinko
Forumaš(ica)
Pridružen/a: 26. 08. 2006. (23:08:00)
Postovi: (1A8)16
Spol:
Lokacija: PMF-MO 214
|
| Postano: 12:24 uto, 16. 1. 2007 Naslov: |
|
|
|
[quote="ta2a"]a kako bi se onda rješilo ovo:
x^2 + x + 47 == 0 (mod 7)
to je primjer iz skripte i rješenja su x==1(mod 7) i x==5(mod 7), al ja nikak nemrem skužit kak se to izračuna :([/quote]
Inače, zadaci u kojima se koristi Henselova lema su uglavnom takvi da se početna kongruencija riješi na prste. Inače, jednadžbu
x^2 + x + 47 == 0 (mod 7), odnosno x^2 + x + 5 == 0 (mod 7)
bi mogli rješavati i da ju probamo svesti na kvadrat (da je veći prost broj od 7 bio, možda bi to bilo i korisno).
Imamo (x+1/2)^2-1/4 + 5 == 0 (mod 7).
1/2 = 4 (mod 7) ... ovo dobijemo tražeći 1/2 odnosno 2^-1(mod 7) odnosno riješimo 2y == 1 (mod 7) i dobijemo y=4
, to kvadriramo i dobijemo da je 1/4=2(mod 7)
pa nam jednadžba izgleda:
(x + 4)^2 == -3 (mod 7).
Vidimo da je (+/- 2)^2 == -3 (mod 7),
pa je jednadžba ekvivalentna sa x+4== +/- 2 (mod 7).
Jedno rješenje je -2 odnosno 5 (sa +), a drugo -6 odnosno 1 (sa -).
Nadam se da ovo neće samo zbuniti studente. A moguće da se ovo može i jednostavnije izračunati.
| ta2a (napisa): | a kako bi se onda rješilo ovo:
x^2 + x + 47 == 0 (mod 7)
to je primjer iz skripte i rješenja su x==1(mod 7) i x==5(mod 7), al ja nikak nemrem skužit kak se to izračuna |
Inače, zadaci u kojima se koristi Henselova lema su uglavnom takvi da se početna kongruencija riješi na prste. Inače, jednadžbu
x^2 + x + 47 == 0 (mod 7), odnosno x^2 + x + 5 == 0 (mod 7)
bi mogli rješavati i da ju probamo svesti na kvadrat (da je veći prost broj od 7 bio, možda bi to bilo i korisno).
Imamo (x+1/2)^2-1/4 + 5 == 0 (mod 7).
1/2 = 4 (mod 7) ... ovo dobijemo tražeći 1/2 odnosno 2^-1(mod 7) odnosno riješimo 2y == 1 (mod 7) i dobijemo y=4
, to kvadriramo i dobijemo da je 1/4=2(mod 7)
pa nam jednadžba izgleda:
(x + 4)^2 == -3 (mod 7).
Vidimo da je (+/- 2)^2 == -3 (mod 7),
pa je jednadžba ekvivalentna sa x+4== +/- 2 (mod 7).
Jedno rješenje je -2 odnosno 5 (sa +), a drugo -6 odnosno 1 (sa -).
Nadam se da ovo neće samo zbuniti studente. A moguće da se ovo može i jednostavnije izračunati.
|
|
| [Vrh] |
|
vinko
Forumaš(ica)
Pridružen/a: 26. 08. 2006. (23:08:00)
Postovi: (1A8)16
Spol:
Lokacija: PMF-MO 214
|
| Postano: 14:16 uto, 16. 1. 2007 Naslov: Rješavanje (x+4)^2 == -3 (mod 7) |
|
|
|
[quote="vinko"]
(x + 4)^2 == -3 (mod 7).
Vidimo da je (+/- 2)^2 == -3 (mod 7),
[/quote]
(supstitucija z=x+4)
z^2 == -3 (mod 7)
Da je rješenje z= +/- 2 jednostavno vidimo ako primjetimo da je -3 = 4 (mod 7), pa imamo z^2 == 4 (mod 7).
Inače bi to indeksirali (npr. po bazi 3) pa rješavali
2 ind_3(z) == 4 (mod 6), odnosno ind_3(z) == 2 (mod 3), te dobili
ind_3(z) = 2, 5 (mod 6)
odnosno z=3^2, 3^5, odnosno z = 2, 5 (mod 7).
Pa dobijemo x = -2, 1 (mod 7) odnosno 5 i 1 (mod 7).
| vinko (napisa): |
(x + 4)^2 == -3 (mod 7).
Vidimo da je (+/- 2)^2 == -3 (mod 7),
|
(supstitucija z=x+4)
z^2 == -3 (mod 7)
Da je rješenje z= +/- 2 jednostavno vidimo ako primjetimo da je -3 = 4 (mod 7), pa imamo z^2 == 4 (mod 7).
Inače bi to indeksirali (npr. po bazi 3) pa rješavali
2 ind_3(z) == 4 (mod 6), odnosno ind_3(z) == 2 (mod 3), te dobili
ind_3(z) = 2, 5 (mod 6)
odnosno z=3^2, 3^5, odnosno z = 2, 5 (mod 7).
Pa dobijemo x = -2, 1 (mod 7) odnosno 5 i 1 (mod 7).
|
|
| [Vrh] |
|
LSSD
Forumaš(ica)
Pridružen/a: 19. 01. 2005. (19:11:16)
Postovi: (CB)16
Lokacija: SD CN
|
|
| [Vrh] |
|
vinko
Forumaš(ica)
Pridružen/a: 26. 08. 2006. (23:08:00)
Postovi: (1A8)16
Spol:
Lokacija: PMF-MO 214
|
| Postano: 20:11 čet, 18. 1. 2007 Naslov: |
|
|
|
[quote="LSSD"]Moze li mi netko reci koji su koraci prilikom rijesavanja kongruencije:
x^2 + x + 47 == 0 (mod 7^4)?
U knjizi je rijesen zadatak za mod 7^3, i tamo rijesavamo kongruencije za j=1 i 2, a kako je ovdje?Da li za j=1 i 3 ili j=1,2,3?[/quote]
Trebamo rjesavati sve redom, prvo za 1, pa 2 (isto kao u knjizi), te na kraju jos za 3.
| LSSD (napisa): | Moze li mi netko reci koji su koraci prilikom rijesavanja kongruencije:
x^2 + x + 47 == 0 (mod 7^4)?
U knjizi je rijesen zadatak za mod 7^3, i tamo rijesavamo kongruencije za j=1 i 2, a kako je ovdje?Da li za j=1 i 3 ili j=1,2,3? |
Trebamo rjesavati sve redom, prvo za 1, pa 2 (isto kao u knjizi), te na kraju jos za 3.
|
|
| [Vrh] |
|
|
pa 4 se prebaci s druge strane! 
strašno...
