Største fælles divisor for heltal er det største positive heltal, der deler dem alle uden rest. Forkortelsen er SFD. Den forkorter brøker og forhold, opdeler mængder i lige store grupper og finder den største længde, der passer præcist i flere mål.
Fælles divisorer gør definitionen konkret
De positive divisorer i 18 er 1, 2, 3, 6, 9 og 18. For 24 er de 1, 2, 3, 4, 6, 8, 12 og 24. Fælles er 1, 2, 3 og 6, så SFD er 6. Fuld oplistning bliver upraktisk ved store tal.
Vælg to positive heltal. Panelet viser hver division og rest i Euklids algoritme, så vejen kan kontrolleres.
Følg Euklids algoritme
Hvert trin erstatter parret med divisor og rest; den sidste rest forskellig fra nul er SFD.
Primfaktorer beholder de mindste fælles eksponenter
Opløs hvert tal i primfaktorer. For hver primfaktor, der findes i alle tal, vælges den mindste eksponent, og potenserne ganges. Metoden fungerer også for tre eller flere tal.
For 84 og 126 er én faktor 2, 3 og 7 fælles. Produktet er 42. Kontrollen er 84 divideret med 42 lig 2 og 126 divideret med 42 lig 3. Ingen yderligere primtalspotens deles.
Euklids algoritme undgår svær faktorisering
Hvis (a>b>0), divider (a) med (b), erstat parret med (b) og resten, og gentag. Fælles divisorer bevares, fordi enhver divisor i (a) og (b) også deler (a-qb). Den sidste rest forskellig fra nul er SFD.
For 252 og 105 bliver resterne 42, 21 og nul. SFD er 21 uden fuld faktorisering. Normalt gælder (gcd(a,0)=|a|), mens (0,0) ofte er udefineret.
Identiteter giver en uafhængig kontrol
At bytte input ændrer ikke den positive SFD. Efter division med SFD er kvotienterne indbyrdes primiske. Desuden er SFD gange mindste fælles multiplum lig absolutværdien af tallenes produkt.
Kvadratiske fliser uden tilskæring
Et gulv på 252 cm gange 105 cm skal dækkes med størst mulige kvadratiske fliser uden snit. Siden skal dele begge mål og er 21 cm. Der er plads til 12 gange 5, altså 60 fliser.
SFD passer kun ved præcis delelighed. Hvis spild, tolerancer eller afrundede mål tillades, kræves et andet praktisk kriterium. Omregn først alle længder til samme nøjagtige enhed.
For tre tal arbejdes trinvist: bestem først SFD for de to første og derefter SFD for dette resultat og det tredje. SFD for 48 og 72 er 24; sammen med 60 bliver den 12. Negative fortegn ændrer ikke deleligheden, så brug absolutværdier og angiv en positiv SFD. Divider hvert oprindeligt tal med kandidaten. Alle kvotienter skal være heltal, og kandidaten kan ikke være større end absolutværdien af et input forskelligt fra nul. I en tekstopgave skal antallet af grupper eller stykker også blive helt.
Hvis spørgsmålet handler om antal grupper, er SFD alene ikke slutsvaret. Med gruppestørrelse 12 giver 48 genstande 4 grupper og 60 genstande 5. Kontrollér, at alt bruges uden rest, og at ordet “største” gælder gruppens størrelse, ikke antallet af grupper. De fortolkninger giver forskellige svar. For flere tal fortsætter den trinvise metode, indtil alle input er medtaget.
