Kalkylator för största gemensamma faktor
Beräkna den största gemensamma faktorn (SGF) – även kallad den största gemensamma delaren (SGD) – för två heltal med hjälp av Euklides algoritm. Det är det största talet som delar båda talen jämnt, och används för allt från att förenkla bråk till att utforma kakelläggning och kryptografi.
Last updated: May 2026
Jämför med liknande
Om denna räknare
Den största gemensamma faktorn för två heltal a och b är det största positiva heltal som delar båda utan rest. Kalkylatorn använder Euklides algoritm: med absolutbeloppen av a och b ersätts (a, b) upprepade gånger med (b, a mod b) tills b blir 0; kvarvarande a är SGF. Körtiden är O(log min(a, b)) – varje steg halverar minst det större värdet – så även astronomiskt stora tal (miljoner eller miljarder siffror i kryptografiska sammanhang) löses nästan omedelbart. Variabler: num1 och num2 är de två heltalen; negativa tal hanteras genom att ta absolutbelopp, eftersom ett negativt tals delare är desamma som dess absolutbeloppets. Viktiga specialfall: gcd(0, 0) definieras konventionellt som 0 (ingen störst delare finns, varje heltal delar 0); gcd(a, 0) = |a| för alla a; om något av talen är 1 är sgd 1 (1 delar allt). SGF är alltid minst 1 och högst min(|a|, |b|). När gcd(a, b) = 1 kallas de två heltalen samprima eller relativt prima – ett centralt begrepp inom talteori som används i RSA-kryptering, modulär aritmetik och kinesiska restsatsen. SGF uppfyller även identiteten lcm(a, b) · gcd(a, b) = a · b, så en SGF-kalkylator ger implicit också svar på LCM-frågor och vice versa. För tre eller fler tal är sgd associativ: gcd(a, b, c) = gcd(gcd(a, b), c).
Hur du använder den
Exempel 1 – Förenkling av ett bråk. För att reducera 48/180 till lägsta form, beräkna gcd(48, 180). Ange 48 och 180. Euklides spårning: gcd(180, 48) → 180 mod 48 = 36 → gcd(48, 36) → 48 mod 36 = 12 → gcd(36, 12) → 36 mod 12 = 0 → gcd = 12. ✓ Dividera täljare och nämnare med 12: 48/180 = 4/15, som är fullt reducerat eftersom gcd(4, 15) = 1. Exempel 2 – Kakelläggning. Du vill lägga klinker på ett golv på 24 m × 36 m med de största möjliga kvadratiska plattorna utan kapning. Plattans sida måste dela både 24 och 36 jämnt – det vill säga vara en gemensam faktor. Den största är gcd(24, 36) = 12. ✓ Den optimala plattan är alltså 12 m × 12 m, och du behöver 2 × 3 = 6 plattor totalt. Samma princip löser alla problem om "största jämlika delarbarhet", från att skära tyg till att packa burkar.
Vanliga frågor
Vad är skillnaden mellan SGF (eller SGD) och MGM?
SGF/SGD är det största tal som delar båda talen jämnt; MGM (minsta gemensamma multipel) är det minsta tal som båda talen delar jämnt. De hänger samman via identiteten SGD(a, b) · MGM(a, b) = a · b, vilket innebär att du omedelbart kan beräkna det ena om du känner det andra. Som tumregel är SGF alltid högst min(a, b) och MGM alltid minst max(a, b). När talen är samprima (delar inga gemensamma faktorer utom 1) gäller SGF = 1 och MGM = a · b – de drar åt varsitt håll. De används i olika sammanhang: SGF för att förenkla bråk, dela upp i lika grupper eller hitta gemensamma delare; MGM för att synkronisera periodiska händelser eller hitta gemensamma nämnare.
Varför är Euklides algoritm så snabb?
Varje steg i Euklides algoritm reducerar det andra talet till (första mod andra), vilket är strikt mindre än det andra. I värsta fallet (när talen är på varandra följande Fibonacci-tal) krävs ungefär log_φ(N) steg, där φ = (1 + √5)/2 ≈ 1,618 är gyllene snittet – det vill säga O(log N) där N är det större talet. För tal med miljontals siffror löses detta ändå på några hundra steg. Algoritmen är äldre än de flesta kulturers skrivna matematik (Euklides nedtecknade den omkring 300 f.Kr.) och är fortfarande en av de mest effektiva algoritmerna inom talteori. Moderna varianter som den binära SGD-algoritmen (som ersätter division med bitförskjutningar och subtraktion) är ännu snabbare på datorer eftersom de undviker kostsamma divisionsoperationer.
Hur beräknar jag SGF för tre eller fler tal?
Tillämpa SGF parvis: gcd(a, b, c) = gcd(gcd(a, b), c), och så vidare för valfritt antal tal. Resultatet beror inte på grupperingsordningen (SGF är associativ och kommutativ), så gcd(gcd(a, b), c) = gcd(a, gcd(b, c)) – du kan kedja dem i valfri ordning. Exempel: gcd(24, 36, 60) = gcd(gcd(24, 36), 60) = gcd(12, 60) = 12. Ett alternativ är att faktorisera varje tal i primtal och ta den minsta exponenten för varje primtal; det är vad de flesta läroböcker lär ut eftersom det tydliggör strukturen, men den parvisa Euklides-metoden är mycket snabbare i praktiken.
Vilka är de vanligaste misstagen när man beräknar SGF?
Det första är att ange ett av de ursprungliga talen som SGF utan att kontrollera att det delar det andra – till exempel att påstå att gcd(24, 36) är 24 för att 24 verkar "ungefär mindre" (det stämmer inte; 24 delar inte 36). Det andra är att blanda ihop SGF med MGM och ge multipeln i stället för delaren, vilket ger ett alldeles för stort tal. Det tredje är att använda subtraktion i stället för modulo i Euklides algoritm – subtraktionsformen fungerar men är dramatiskt långsammare för tal av olika storlek (gcd(10⁹, 1) kräver 10⁹ steg med subtraktion men bara 1 steg med modulo). Det fjärde är att glömma att SGF för negativa tal använder absolutbelopp, så gcd(-12, 18) = 6, inte -6 eller något negativt resultat. Det femte är att beräkna SGF för icke-heltal – gcd(2,5; 1,5) är inte definierat i standardmening, även om det kan utökas till rationella tal via MGM för nämnarna.
När bör jag inte använda den här kalkylatorn?
Använd den inte för icke-heltal – SGF är bara definierat för heltal i standardmening, och decimaler eller bråk kräver en annan metod (gcd(p/q, r/s) = gcd(p·s, r·q) / (q·s) är en möjlig utökning). Använd den inte när du egentligen behöver minsta gemensamma multipel – använd i stället en MGM-kalkylator. Den är inte rätt verktyg för SGF för tre eller fler tal i ett steg – du måste kedja beräkningarna manuellt; flerinmatnings-SGD-verktyg är mer effektiva. Undvik den för polynom-SGD (att hitta det största polynom som delar två givna polynom) – det kräver polynomisk långdivision, inte heltalsmodulo. Slutligen, använd den inte för kryptografiskt SGD på mycket stora heltal (som vid RSA-nyckelgenerering) – det kräver ett bignum-bibliotek, inte en kalkylatorwidget; även om algoritmen är densamma kan datatyperna i den här kalkylatorn inte representera sådana indata.