Fórum studentů MFF UK

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/cvic4-5/algi_1.htm

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:))

[quote="ps"]Nevím si rady s tímto příkladem (pochází z testu z jednoho cvičení):

[quote]Najděte inverzní prvek k prvku 71 v tělese Z103[/quote]

Jak se ten prvek nalezne pomocí rozšířeného Eukleidova algoritmu? Díky[/quote]

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:)

Nevím si rady s tímto příkladem (pochází z testu z jednoho cvičení):

[quote]Najděte inverzní prvek k prvku 71 v tělese Z103[/quote]

Jak se ten prvek nalezne pomocí rozšířeného Eukleidova algoritmu? Díky