Største felles divisor
From Wikipedia, the free encyclopedia
Største felles divisor (forkortet SFD eller sfd, engelsk gcd for greatest common divisor ), er det største tallet som deler to tall.[1] På norsk er dette aritmetiske begrepet også omtalt som største felles faktor (forkortet sff ).[2]
I dag er det mest vanlig å bruke den engelske forkortelsen gcd. Største felles faktor til to tall a og b skrives derfor vanligvis som gcd(a,b) eller noen ganger ganske enkelt som (a,b). Den kan benyttes ved forkorting av brøker. For eksempel, da 5 er det største hele tallet som deler 15 og 50 uten rest, så er gcd(15,50) = 5. Derfor har man også 15/50 = (5⋅3)/(5⋅10) = 3/10.
Noen spesielle verdier er gcd(a,a) = a og gcd(a,1) = 1 som begge følger fra definisjonen. I tillegg må man ha at gcd(a,0) = a fordi tallet 0 er delelig med alle tall da 0⋅a = 0.
Hvis a og b ikke har felles faktorer, det vil si at gcd(a,b) = 1, sier man at a og b er relativt primiske. Det er for eksempel tilfelle med 21 og 64 slik at gcd(64,21) = 1.
For store tall regnes den største felles faktor raskest ut ved bruk av Euklids algoritme. Den viser at svaret d = gcd(a,b) alltid kan skrives som
hvor s og t er heltall som kan bestemmes. To relativt primiske tall a og b kan derfor kombineres slik at 1 = sa + tb. Den samme metoden kan også benyttes i andre tallsystem som er euklidske ringer. I moderne kryptografi benyttes slike ringer hvor elementene består av polynomer.