Faktorisera 2314 till primtal

Hej. Har precis börjat med primtal och delbarhet, och har greppat hur man löser kvot och rest med långdivision, som jag antar också kan och ska användas på primtal, men frågan är bara hur?

Mitt tal som jag primtalsfaktorisera är: 2314. Eftersom det slutar på ett jämnt tal så är det delbart med 2, så jag fick ner det till 1157. Sen ska jag få ner det ytterligare, men jag vet inte hur jag ska komma på vad jag ska dela talet med. Om jag ska testa mig fram kommer det ta väldigt lång tid, så hur vet jag vad jag ska dela med? Facit säger att svaret ska vara 2 * 1157 = 2 * 13 * 89, så jag ska alltså dela med 13, men hur kommer man fram till det?

Du får testa dig fram! 3, 5, 7, 11, 13... Opsss, redan där!

Okej, så det är bara att testa sig fram helt enkelt? Jag kan ju redan nu utesluta vissa tal som inte är delbara. Tänkte mest utifall det fanns någon speciell metod för att lista ut vad talet är delbart med.

Du har listat ut att 2 är en indelning, så vi kan fokusera på 1157. Om det inte är ett primtal så finns det två heltal a och b så att a*b=1157. I så fall måste ett tal vara mindre än roten ur 1157 och det andra större (fast ett större kan ha fler primtalfaktorer, så vi fokuserar inte på det). Roten ur 1157 är lite över 34, så du måste testa alla tal mellan 1 och 34 om du ska visa att det är ett primtal. 2,3,5 och 11 är triviala. Testa 7, funkar inte, testa 13, funkar. Klart.

När du har hittat 89 kan du använda lagen om låga primtal. Det är en skämtregel, men den fungerar. Om du har ett primtal under hundra (förutom 91) och du inte enkelt kan se att det inte är ett primtal, så är det ett primtal.

Det beror på samma regel som innan, ett icke-primtal måste ha en delare mindre än kvadratroten. Kvadratroten ur 100 är 10, så alla tal under hundra är antingen primtal eller har en delare under 10. Nästan alla delare under 10 är enkla, alla kombinationer av 2,3,5 är lätta att se. Det enda knepiga är 7, men 7*7=49 kan alla, 7*11=77 är enkelt, så det enda undantaget är 7*13=91.

Den vanligaste metoden för mindre tal kallas trial division, d.v.s. bara att testa. Däremot kan man göra det med lite finess. Dels jämna tal som du själv sade, men även tal där siffersumman är delbar med 3 är själva delbara med 3. Likaså alla tal delbara med 5 är lätta att se. Därefter blir det lite klurigare. Då är det bara att testa 7, 11, 13 osv. Däremot behöver man aldrig testa tal > kvadratroten av talet du undersöker.

Okej, då förstår jag. En sak bara, de andra som har svarat här har tagit upp att jag ska testa med 11, medan du menar att det är ett trivialt tal. Vad menas med det?

Okej, då förstår jag. Bara att testa på alla 7 uppgifter då haha. Suck...

Det finns ingen riktigt bra metod för det, och faktum är att mycket modern kryptering bygger på just detta. Hade det funnits en enkel metod att ta reda på det så faller större delen av all modern kryptering.

Men annars finns det ju lite genvägar. För både 2 och 5 räcker det med att titta på sista siffran. För 3 så kollar man på om summan av talets siffror är delbar med tre. 1157 är inte delbart med 3 eftersom 1+1+5+7=14 vilket inte är delbart med 3.

För högre primtal blir metoderna mer komplicerade.

Att testa alla primtal under 20 tar inte lång tid. Det är fort gjort med en miniräknare.

Ofta syns det om ett tal är delbart med 11. I just ditt fall skulle jag säga att 1157 är delbart med 11 enbart om 57 är delbart med 11 (eftersom de 1100 naturligtvis är delbara) och det är det ju inte.

Men det stämmer, det beror lite på talet.

115-14=111
11-2=9 ==2 mod 7
Talet är alltså ej delbart med 7.

1*10^3+1*10^2+5^10^1+7*10^0==(-1)+(1)-(5)+(7)==2 mod 11 så ej delbart med 11 heller

Det visar sig med långdivison att det är delbart med 13
1157=13*89
89 är ett primtal så du är klar.
2314=2*13*89

jo men det finns mer generell metod. (se ovan)

Räcker med kolla primtalen mellan 1 och 34.