Algorytm Euklidesa - dowód poprawności

pr110d · Post autor: **pr110d** » 30 paź 2009, o 22:32

Witam forumowiczow. Potrzebuję jakiegoś formalnego zapisu dowodu poprawności algorytmu Euklidesa wyznaczania NWD liczb. Ma on być zrozumiały dla przeciętnego dziecka w LO. Szukałem po sieci, ale niestety nic konkretnego nie znalazłem. Na Wikipedii jest jeden, ale autor używa kongruencji i innych pojęć, które są dla pierwszoklasisty jeszcze za skomplikowane.

Drugie pytanie... ktory z alg. wyznaczania NWD ma nazwe algorytmu Gaussa?

Pozdrawiam.

Kvasir · Post autor: **Kvasir** » 30 paź 2009, o 23:35

Dowód na wikipedii da się zapisać nie używając kongruencji.
Kongruencje to tylko język, prostszy sposób zapisu, nic innego.
Jeśli wiesz co to kongruencje to rozpisz ten dowód bez nich. Reszta dowodu powinna być zoruzmiała dla zwykłego ucznia

edit: tam nawet nie ma kongruencji chyba. To, że jest 'słowo' mod nie oznacza, że są to kongruencje.

pr110d · Post autor: **pr110d** » 31 paź 2009, o 10:35

Z tego co mi sie wydaje to: NWD (a, b) = NWD (b, a mod b) bedzie oznaczac NWD(a, b) = NWD(b, a - kb)? Tak?

No i jeszcze pozostaje mi ten alg. Gaussa w szukaniu NWD. To jest ten najwzyklejszy co dzieci w gimnazjum poznaja, polegajacy na rozkladzie liczb na czynniki i przemnozeniu pewnych skladnikow iloczynu?