Primtal

De positiva delarna till 13 är 1 och 13. Därför är 13 ett primtal. Talet 15 har delarna 1, 3, 5 och 15 och är därför sammansatt. Talet 1 är varken primtal eller sammansatt, eftersom det bara har en positiv delare. Den avgränsningen gör att varje heltal större än 1 får en entydig primtalsfaktorisering bortsett från faktorernas ordning.

Talet 2 är det enda jämna primtalet. Alla andra jämna heltal större än 2 är delbara med 2 och har därför minst tre positiva delare. Ett negativt heltal kallas normalt inte primtal i skolans definition, men dess absolutbelopp kan delas upp i primfaktorer och ett minustecken. Exempelvis är $-30 = -1 \cdot 2 \cdot 3 \cdot 5$.

Ett tal är delbart med 2 om sista siffran är jämn. Det är delbart med 3 om siffersumman är delbar med 3, och med 9 om siffersumman är delbar med 9. Delbarhet med 5 syns på slutsiffran 0 eller 5. Ett tal är delbart med 10 om det slutar på 0. Reglerna ger snabba tester men ersätter inte hela primtalskontrollen.

För att avgöra om $n$ är ett primtal räcker det att pröva primtal som är högst $\sqrt{n}$. Om $n$ hade en faktor större än $\sqrt{n}$ måste den andra faktorn vara mindre än $\sqrt{n}$. För 97 är $\sqrt{97}$ strax under 10. Vi behöver därför bara testa 2, 3, 5 och 7. Talet är inte delbart med något av dem, så 97 är ett primtal.

Ett faktorträd börjar med att ett sammansatt tal skrivs som en produkt. Varje sammansatt faktor delas vidare tills alla löv är primtal. Olika första val ger samma primfaktorer. För 84 kan du börja med $7 \cdot 12$ eller $4 \cdot 21$. Båda vägarna slutar i $2^{2} \cdot 3 \cdot 7$. Att sortera faktorerna och skriva upprepningar som potenser gör resultatet lätt att jämföra.

Kontrollen är alltid multiplikation. Om du har fått $2^{3} \cdot 3 \cdot 5$ som faktorisering ska produkten vara $8 \cdot 3 \cdot 5 = 120$. En faktor får inte lämnas sammansatt. Att skriva $120 = 12 \cdot 10$ är en faktorisering men inte en primtalsfaktorisering, eftersom både 12 och 10 kan delas vidare.

Börja med de billigaste testerna. Jämnhet, slutsiffra och siffersumma kan snabbt utesluta 2, 3 och 5. Beräkna sedan ungefärlig kvadratrot för att veta när kontrollen är klar.

Dividera gärna med små primtal i stigande ordning. Metoden ger en tydlig kedja och minskar risken att en faktor glöms. Fortsätt tills kvoten är 1.

Primfaktorer gör två centrala begrepp mekaniska. Största gemensamma delare använder varje gemensam primfaktor med den lägsta exponenten. Minsta gemensamma multipel använder alla förekommande primfaktorer med den högsta exponenten.

Om $n = p^{a}q^{b}$ med olika primtal $p$ och $q$ kan en delare innehålla $p$ i någon av exponenterna 0 till $a$ och $q$ i någon av exponenterna 0 till $b$. Antalet val multipliceras. Metoden generaliseras direkt till fler primfaktorer.

På högskoleprovet är primtalsfaktorisering ofta ett verktyg inne i en större uppgift. Läs först vad som efterfrågas. För delbarhet med 9 räcker siffersumman. För att förkorta ett bråk behöver du bara hitta gemensamma faktorer. För antal delare behöver du däremot den fullständiga primtalsfaktoriseringen och exponenterna.

Lär dig primtalen åtminstone upp till 31 så att testningen går snabbt, men använd alltid en stoppregel. När alla primtal upp till kvadratroten har prövats är kontrollen klar. Vid stora produkter kan svarsalternativen avslöja vilka primfaktorer som spelar roll. Kontrollera slutligen genom att multiplicera ihop faktorerna och jämföra med ursprungstalet.

Eratosthenes såll hittar alla primtal upp till en vald gräns. Börja med 2 och stryk större multiplar av 2. Gå till nästa ostrukna tal, 3, och stryk dess större multiplar. Fortsätt med 5 och 7. När nästa primtals kvadrat överstiger gränsen är alla sammansatta tal redan strukna, eftersom de har en faktor som inte överstiger sin kvadratrot.

Samma idé förklarar primalitetstestet. Om $n = ab$ och både $a$ och $b$ vore större än $\sqrt{n}$ skulle produkten $ab$ vara större än $n$. Därför måste minst en faktor i varje delarpar vara högst $\sqrt{n}$. Genom att testa möjliga primfaktorer på den sidan av paret fångar du alltså varje möjlig sammansättning.

Delarpar ger också ett konkret sätt att kontrollera antalet delare. För 36 är paren 1 och 36, 2 och 18, 3 och 12, 4 och 9 samt 6 och 6. Kvadrattalet har ett mittpar där faktorerna är lika, så antalet positiva delare blir udda. I exponentformen $36 = 2^{2} \cdot 3^{2}$ fås $(2 + 1)(2 + 1) = 9$ delare, vilket bekräftar listan.

Primfaktoriseringen kan dessutom jämföra bråk utan full division. Om en täljare innehåller fler faktorer 2 eller 3 än nämnaren kan gemensamma faktorer strykas exakt. Metoden bevarar heltalsstrukturen och undviker decimalavrundning. Den är särskilt användbar när stora tal med synliga delbarhetsmönster står i svarsalternativen.

Ett heltal större än 1 kan ha många representationer som produkt, men primfaktorerna är entydiga bortsett från ordningen. Därför kan två till synes olika faktorträd jämföras genom sortering. Om ett träd för 90 slutar i 2, 3, 3 och 5 ska varje korrekt träd ge samma faktorsamling med samma upprepningar och potensen $2 \cdot 3^{2} \cdot 5$.

Två heltal är relativt prima om deras största gemensamma delare är 1. De behöver inte själva vara primtal. Talen 8 och 15 är båda sammansatta men delar ingen primfaktor. Begreppet förklarar när ett bråk redan är fullständigt förkortat och när produkter kan delas upp i oberoende faktordelar.

Exponenterna i primtalsfaktoriseringen visar om ett tal är en perfekt kvadrat eller kub. Ett positivt heltal är en kvadrat exakt när alla primexponenter är jämna. Det är en kub när alla är delbara med 3. Talet $360 = 2^{3} \cdot 3^{2} \cdot 5$ har inte den exponentstruktur som krävs för något av fallen.

För att göra 360 till en kvadrat genom multiplikation behöver exponenterna 3, 2 och 1 bli jämna. Multiplikation med $2 \cdot 5 = 10$ ger $3600 = 2^{4} \cdot 3^{2} \cdot 5^{2} = 60^{2}$. För att göra talet till en kub behövs andra kompletterande exponenter. Metoden arbetar direkt med rester modulo 2 eller 3 i exponenterna.

Om två tal är primtalsfaktoriserade kan deras produkt och kvot analyseras utan stora tal. Produkten adderar exponenterna. En heltalskvot finns bara om varje primexponent i täljaren är minst lika stor som motsvarande exponent i nämnaren. Det ger en exakt delbarhetskontroll.

Ett primtal större än 3 kan bara ha resten 1 eller 5 vid division med 6. Övriga rester ger delbarhet med 2 eller 3. Villkoret är nödvändigt men inte tillräckligt: 25 har resten 1 men är sammansatt. Regeln kan därför utesluta kandidater snabbt men inte ensam bevisa primalitet.

Siffersummeregeln för 3 följer av att 10 har resten 1 vid division med 3. Varje tiopotens har då också resten 1, så talet och dess siffersumma får samma rest. Ett liknande argument fungerar för 9. För 11 används i stället en alternerande siffersumma.

Om ett tal $n$ är primtal och delar en produkt $ab$, måste $n$ dela minst en av faktorerna. Egenskapen gör primfaktoriseringen stabil och hjälper i delbarhetsbevis. För sammansatta delare gäller inte motsvarande påstående, eftersom 6 delar $2 \cdot 3$ utan att dela 2 eller 3 var för sig.