Inverzní prvek a Eukleidův algoritmus

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

ps wrote: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 = 711 + 32
71 = 322 + 7
32 = 74 + 4
7 = 41 + 3
4 = 3*1 + 1

Teraz si spatne musis vyjadrovat zvysky ako linearne kombinacie pomocou substitucii predchadzujich vyjadreni:

32 = 103 - 711
7 = 71 - 322 = 71 - (103 - 711)2 = 371 - 2103
4 = 32 - 74 = (103 - 711) - (371 - 2103)4 = 9103 - 1371
3 = 7 - 41 = (371 - 2103) - (9103 - 1371)1 = 1671 - 11103
1 = 4 - 31 = (9103 - 1371) - (1671 - 11103)1 = 20103 - 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:)

ja jeste doplnim ze se tomu rikal zpetny chod Eukleidova algoritmu

teoreticky te zajima neco ve smyslu

1 = x72 + y102 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:))

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