Inverzní prvek a Eukleidův algoritmus

První část základního kursu algebry je věnována základním algebraickým pojmům a strukturám. Míní se tím zejména pojmy uzávěrový systém, operace, algebra, homomorfismus, kongruence, uspořádání, dělitelnost, a struktury jako svazy, monoidy, grupy, okruhy a tělesa. V kursu se též věnuje pozornost modulární aritmetice a konstrukci konečných těles.
ps
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

Příspěvek od ps »

Nevím si rady s tímto příkladem (pochází z testu z jednoho cvičení):
Najděte inverzní prvek k prvku 71 v tělese Z103
Jak se ten prvek nalezne pomocí rozšířeného Eukleidova algoritmu? Díky
qwyxyo
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

Příspěvek od qwyxyo »

ps píše:Nevím si rady s tímto příkladem (pochází z testu z jednoho cvičení):
Najděte inverzní prvek k prvku 71 v tělese Z103
Jak se ten prvek nalezne pomocí rozšířeného Eukleidova algoritmu? Díky
Skusim ti ten postup popisat cely. Je to celkom lahke. Naucil ma to tb a jeho to naucil flaska:)

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:)
Uživatelský avatar
Lada
Donátor
Donátor
Příspěvky: 165
Registrován: 9. 1. 2005 10:17
Typ studia: Informatika Bc.
Bydliště: Slaný / zácpa na Evropské

Příspěvek od Lada »

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:))
Hail to you, champion:o)
ps
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:

Příspěvek od ps »

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
Odpovědět

Zpět na „MAI062 Algebra I“