Største felles divisor for heltall er det største positive heltallet som deler dem alle uten rest. Forkortelsen er SFD. Den forkorter brøker og forhold, deler mengder i like grupper og finner den største lengden som passer nøyaktig i flere mål.
Felles divisorer gjør definisjonen konkret
De positive divisorene til 18 er 1, 2, 3, 6, 9 og 18. For 24 er de 1, 2, 3, 4, 6, 8, 12 og 24. Felles er 1, 2, 3 og 6, så SFD er 6. Full opplisting blir upraktisk ved store tall.
Velg to positive heltall. Panelet viser hver divisjon og rest i Euklids algoritme, slik at veien kan kontrolleres.
Følg Euklids algoritme
Hvert trinn erstatter paret med divisor og rest; siste rest forskjellig fra null er SFD.
Primfaktorer beholder de minste felles eksponentene
Løs hvert tall opp i primfaktorer. For hver primfaktor som finnes i alle tall, velger du den minste eksponenten og multipliserer potensene. Metoden fungerer også for tre eller flere tall.
For 84 og 126 er én faktor 2, 3 og 7 felles. Produktet er 42. Kontrollen er 84 delt på 42 lik 2 og 126 delt på 42 lik 3. Ingen ekstra primtallspotens deles.
Euklids algoritme unngår vanskelig faktorisering
Hvis (a>b>0), del (a) på (b), erstatt paret med (b) og resten, og gjenta. Felles divisorer bevares fordi enhver divisor i (a) og (b) også deler (a-qb). Siste rest forskjellig fra null er SFD.
For 252 og 105 blir restene 42, 21 og null. SFD er 21 uten full faktorisering. Vanligvis gjelder (gcd(a,0)=|a|), mens (0,0) ofte er udefinert.
Identiteter gir en uavhengig kontroll
Å bytte rekkefølge endrer ikke den positive SFD. Etter divisjon med SFD er kvotientene innbyrdes primiske. Dessuten er SFD ganger minste felles multiplum lik absoluttverdien av tallenes produkt.
Kvadratiske fliser uten skjæring
Et gulv på 252 cm ganger 105 cm skal dekkes med størst mulige kvadratiske fliser uten kutt. Siden må dele begge mål og er 21 cm. Det passer 12 ganger 5, altså 60 fliser.
SFD passer bare ved nøyaktig delbarhet. Hvis svinn, toleranser eller avrundede mål tillates, kreves et annet praktisk kriterium. Regn først alle lengder om til samme eksakte enhet.
For tre tall arbeider du trinnvis: bestem først SFD for de to første og deretter SFD for dette resultatet og det tredje. SFD for 48 og 72 er 24; sammen med 60 blir den 12. Negative fortegn endrer ikke delbarheten, så bruk absoluttverdier og oppgi en positiv SFD. Del hvert opprinnelige tall på kandidaten. Alle kvotientene skal være heltall, og kandidaten kan ikke være større enn absoluttverdien av en input forskjellig fra null. I en tekstoppgave skal også antallet grupper eller biter bli helt.
Hvis oppgaven spør etter antall grupper, er SFD bare et mellomresultat. Med gruppestørrelse 12 gir 48 gjenstander 4 grupper og 60 gjenstander 5. Kontroller at alt brukes uten rest, og at ordet «største» viser til gruppestørrelsen, ikke til antallet grupper. For tre eller flere tall brukes metoden trinnvis til alle tallene er tatt med. Del til slutt hvert opprinnelig tall på kandidaten som en enkel kontroll.
