Anonymný autor

Euklidov algoritmus

Dobrý deň prosím potrebovala by som poradiť s týmto príkladom:
Pomocou Euklidovho algoritmu nájdite D(132, 56) a túto hodnotu vyjadrite v tvare 132.x+56.y
Ďakujem

2 odpovede

Anna S. Kontaktovať

Prílohy:

Komentáre:

Anna S.

Ja som využila Euklidov algoritmus na rozklad na prvočinitele a až potom som určila spoločný deliteľ ako to robia žiaci aj na ZŠ. Existuje aj priamo algorimus na výpočet spoločného deliteľa (tam sa čísla aj odčítavajú a nakoniec sa dospeje k D). Až večer sa dostanem k počítaču. k to potrebujete takto pošlem vám to, len mňa to už do úlohy druhýkrát nepustí.... musíte mi napísať odkaz. Výsledok bude ten istý - len trochu iný postup

Anonymný autor

Ja by som to potrebovala takto: 132=56*2+20 56=20*2+16 20=16*1+4 16=4*4+0 4=4*1+0 NSD =4 (posledný nenulovy zvyšok) A teraz ešte potrebujem spätne vyjadrenie (a to neviem ako pokračovať) 4=20-16*1=20-(56 -20*2) ?

Peter K. Kontaktovať

Pozri sa na túto tabuľku. Aby to bolo jednoduché, použil som "vanilla" - teda odčítací a nie moduliaci Euklidov algoritmus. V prvých dvoch stĺpcoch je obyčajný Eukleidov algoritmus, v druhých dvoch je všetko vyjadrené ako kombinácie 132 a 56. Skončili sme, keď sa nám v prvých dvoch stĺpcoch objavili dve čísla, z ktorých jedno je deliteľ druhého. Výsledná kombinácie je 4 = 3 x 132 - 7 x 56.

Prílohy: