Største fælles divisor

Antag at vi har to hele tal a og b. Vi vil finde det største hele tal, som både går op i tallet a og i tallet b. Dette tal kaldes for den største fælles divisor.

Den største fælles divisor for to hele tal a og b skrives som sfd(a, b). På engelsk skriver man gcd(a, b).

Eksempler:

Lad os se på de to tal a = 2 og b = 4.
De eneste tal der går op i 2 er tallene 1 og 2. 
De eneste tal der går op i 4 er tallene 1, 2 og 4. 
Dermed er sfd(2, 4) = 2.

Lad os se på de to tal a = 2 og b = 6.
De eneste tal der går op i 2 er tallene 1 og 2. 
De eneste tal der går op i 6 er tallene 1, 2 og 3. 
Dermed er sfd(2, 6) = 2.

Lad os se på de to tal a = 4 og b = 6.
De eneste tal der går op i 4 er tallene 1, 2 og 4. 
De eneste tal der går op i 6 er tallene 1, 2 og 3. 
Dermed er sfd(4, 6) = 2.

Lad os se på de to tal a = 12 og b = 9.
De eneste tal der går op i 12 er tallene 1, 2, 3, 4, 6, 12. 
De eneste tal der går op i 9 er tallene 1, 3 og 9. 
Dermed er sfd(12, 9) = 3.

Lad os se på de to tal a = 12345 og b = 2345.

De eneste tal der går op i 12345 er tallene 
1, 3, 5, 15, 823, 2469, 4115, 12345.

De eneste tal der går op i 2345 er tallene 
1, 5, 7, 35, 67, 335, 469, 2345.

Dermed er sfd(12345, 2345) = 5.

Når tallene a og b er store tal, så kan man ikke sådan lige finde de tal der går op i hver af dem.

Det er her Euklids algoritme kommer ind i billedet. Euklids algoritme er en effektiv metode til at bestemme den største fælles divisor for to tal.