Jak se ten prvek nalezne pomocí rozšířeného Eukleidova algoritmu? DíkyNajděte inverzní prvek k prvku 71 v tělese Z103
Inverzní prvek a Eukleidův algoritmus
-
- Matfyz(ák|ačka) level III
- Příspěvky: 137
- Registrován: 1. 6. 2006 08:47
- Typ studia: Informatika Mgr.
- Bydliště: Praha 4
- Kontaktovat uživatele:
Inverzní prvek a Eukleidův algoritmus
Nevím si rady s tímto příkladem (pochází z testu z jednoho cvičení):
-
- Matfyz(ák|ačka) level II
- Příspěvky: 51
- Registrován: 30. 5. 2005 19:26
- Typ studia: Informatika Mgr.
- Kontaktovat uživatele:
Re: Inverzní prvek a Eukleidův algoritmus
Skusim ti ten postup popisat cely. Je to celkom lahke. Naucil ma to tb a jeho to naucil flaska:)ps píše:Nevím si rady s tímto příkladem (pochází z testu z jednoho cvičení):
Jak se ten prvek nalezne pomocí rozšířeného Eukleidova algoritmu? DíkyNajděte inverzní prvek k prvku 71 v tělese Z103
Najprv si rozlozis cisla nasledovne, az kym nebude zvysok po deleni jedna (ten algoritmus tam snad uvidis):
103 = 71*1 + 32
71 = 32*2 + 7
32 = 7*4 + 4
7 = 4*1 + 3
4 = 3*1 + 1
Teraz si spatne musis vyjadrovat zvysky ako linearne kombinacie pomocou substitucii predchadzujich vyjadreni:
32 = 103 - 71*1
7 = 71 - 32*2 = 71 - (103 - 71*1)*2 = 3*71 - 2*103
4 = 32 - 7*4 = (103 - 71*1) - (3*71 - 2*103)*4 = 9*103 - 13*71
3 = 7 - 4*1 = (3*71 - 2*103) - (9*103 - 13*71)*1 = 16*71 - 11*103
1 = 4 - 3*1 = (9*103 - 13*71) - (16*71 - 11*103)*1 = 20*103 - 29*71
Z toho vyplyva, inverzom v Z103 je -29, teda 74...
Myslim si, ze je to celkom jednoduche. Je to len trosu iny pohlad na ten algoritmus, ale hlavne mi pride lahsie zapamatatelny. Ale to bude zrejme subjektivne:)
- Lada
- Donátor
- Příspěvky: 165
- Registrován: 9. 1. 2005 10:17
- Typ studia: Informatika Bc.
- Bydliště: Slaný / zácpa na Evropské
ja jeste doplnim ze se tomu rikal zpetny chod Eukleidova algoritmu
teoreticky te zajima neco ve smyslu
1 = x*72 + y*102 kde to x je cislo ktere hledas...
Jo a posledni hint od Flasky je, ze je lepsi si ty prubezne vysledky psat hned, pac jinak v tom nasekas spoustu chyb (osobne vyzkouseno:))
teoreticky te zajima neco ve smyslu
1 = x*72 + y*102 kde to x je cislo ktere hledas...
Jo a posledni hint od Flasky je, ze je lepsi si ty prubezne vysledky psat hned, pac jinak v tom nasekas spoustu chyb (osobne vyzkouseno:))
Hail to you, champion:o)
-
- Matfyz(ák|ačka) level III
- Příspěvky: 137
- Registrován: 1. 6. 2006 08:47
- Typ studia: Informatika Mgr.
- Bydliště: Praha 4
- Kontaktovat uživatele:
Díky oběma za pomoc, už jsem si to dal v hlavě všechno do pořádku.
Nakonec jsem našel podobný příklad i u Žemličky:
http://www.karlin.mff.cuni.cz/~zemlicka ... algi_1.htm
Nakonec jsem našel podobný příklad i u Žemličky:
http://www.karlin.mff.cuni.cz/~zemlicka ... algi_1.htm