Euklides algoritm - hur motivera att den "alltid kommer fungera"?

Jag har fått i uppgift att "försöka hitta en motivering till att detta förkortningsförfarande alltid kommer fungera". Problemet är bara att jag inte her någon aning om hur jag ska göra det... Jag förstår algoritmen, men jag vet verkligen inte hur man går tillväga föra att motivera eller bevisa att den alltid kommer fungera. Om någon kunde tipsa om hur man gör så vore det uppskattat, har suttit hela helgen med det här nu...

Att du kan använda den är inte det samma som att du förstår den.
Sätt dig ner med ett exempel och gå igenom algoritmen. Försök sen gå baklänges och se om du kan skriva om de två talen på ett sätt med en gemensam faktor.

Om du har a och b så kolla om du kan få
a = c*d
b = c*e

Klarade det tror jag, förstår vad du menade nu