Euklides algoritm och den största gemensamma delaren

I det här dokumentet introduceras och analyseras en välkänd algoritm för beräkning av den största gemensamma delaren till två heltal, nämligen Euklides algoritm. En användbar 'konsekvens' av Euklides algoritm är att denna största gemensamma delare alltid låter sig uttryckas som en sorts linjärkombination av de två givna heltalen. Denna sats är en viktig ingrediens i ett vanligt bevis för aritmetikens fundamentalsats, eller rättare sagt, för att visa Euklides hjälpsats.

Uppsatsen ingår i del II (Talteori och diskret matematik) av studien Den första matematiken, som också finns att köpa som bok.

Nivå: gymnasium, inledande högskola/universitet