SBP-Program

f

tw

in

Euklides algoritm. Förklaring

Vad är Euklides algoritm? Euklides algoritm är en metod för att hitta den största gemensamma delaren av två heltal.

Euklides algoritm. Exempel

Uppgift.

Låt A och B vara heltal och A > B.

Använda Euklides algoritm för att bestämma den största gemensamma delaren av talen A och B.

Lösning steg för steg.

1. Vi delar A med B. Vi får kvoten k0 och resten r1

A : B = k0 rest r1

Detta kan skrivas som

A = B * k0 + r1

2. Vi delar B med r1. Vi får kvoten k1 och resten r2

B : r1 = k1 rest r2

Dette kan skrives som

B = r1 * k1 + r2

3. Vi delar r1 på r2. Vi får kvoten k2 och resten r3

r1 : r2 = k2 rest r3

Dette kan skrives som

r1 = r2 * k2 + r3

4. När vi får 0 som en rest

rk - 1 : rk = kk rest 0

dette kan skrives som

rk - 1 = rk * kk + 0

Talet rk är den största gemensamma delaren av A och B

sgd(A, B) = rk

eller

gcd(A, B) = rk

Uppgiften är löst.