SBP-Program

matematikk

f

tw

in

Euklids algoritme. Forklaring

Hva er Euklids algoritme? Euklidalgoritmen er en metode for å finne den største felles divisor mellom to hele tall.

Euklids algoritme. Eksempel

Vi har gitt to hele tallene A og B og A > B.

Finn største felles divisor for tallene A og B ved hjelp av euklidalgoritmen.

Løsning skritt for skritt.

1. Vi deler A på B. Vi får kvotienten k0 og resten r1

A : B = k0 rest r1

Dette kan skrives som

A = B * k0 + r1

2. Vi deler B på r1. Vi får kvotienten k1 og resten r2

B : r1 = k1 rest r2

Dette kan skrives som

B = r1 * k1 + r2

3. Vi deler r1 på r2. Vi får kvotienten k2 og resten r3

r1 : r2 = k2 rest r3

Dette kan skrives som

r1 = r2 * k2 + r3

4. Når vi får null som en rest

rk - 1 : rk = kk rest 0

dette kan skrives som

rk - 1 = rk * kk + 0

Tallet rk er den største felles divisoren til A og B

sfd(A, B) = rk

eller

gcd(A, B) = rk