Primtal

Det stämmer att primtal är involverade. Ett knep är att försöka finna ett samband mellan antalet delare och primtalsfaktoriseringen av ett tal.

Darth Vader skrev:

Det stämmer att primtal är involverade. Ett knep är att försöka finna ett samband mellan antalet delare och primtalsfaktoriseringen av ett tal.

Visa spoiler

Säg $N=p_{1}^{\alpha_{1}}p_{2}^{\alpha_{2}} \cdots p_{n}^{\alpha_{n}}$ är primtalsfaktoriseringen av $N$ där $p_{1},p_{2}, \ldots , p_{n}$ är primtal och $\alpha_{1},\alpha_{2}, \ldots , \alpha_{n}$ är positiva heltal. (Tex. $28=2^{2} \cdot 7^{1}$.) Man kan visa att antalet delare (positva) till $N$ är precis $(\alpha_{1}+1)(\alpha_{2}+1) \cdots (\alpha_{n}+1)$. (Tex. har $28=2^{2} \cdot 7^{1}$ exakt $(2+1)(1+1) = 6$ olika positiva delare, nämligen $1,2,4,7,14,28$.)

N står för naturligt tal?

Cristian0311 skrev:

Darth Vader skrev:

Det stämmer att primtal är involverade. Ett knep är att försöka finna ett samband mellan antalet delare och primtalsfaktoriseringen av ett tal.

Visa spoiler

Säg $N=p_{1}^{\alpha_{1}}p_{2}^{\alpha_{2}} \cdots p_{n}^{\alpha_{n}}$ är primtalsfaktoriseringen av $N$ där $p_{1},p_{2}, \ldots , p_{n}$ är primtal och $\alpha_{1},\alpha_{2}, \ldots , \alpha_{n}$ är positiva heltal. (Tex. $28=2^{2} \cdot 7^{1}$.) Man kan visa att antalet delare (positva) till $N$ är precis $(\alpha_{1}+1)(\alpha_{2}+1) \cdots (\alpha_{n}+1)$. (Tex. har $28=2^{2} \cdot 7^{1}$ exakt $(2+1)(1+1) = 6$ olika positiva delare, nämligen $1,2,4,7,14,28$.)

N står för naturligt tal?

Ja, $N$ är ett naturligt tal.

Alltså man primtalsfaktoriserar ett tal, därefter tittar man vilka exponenter som passar för det sökta naturliga tal? Så som du visade i ditt exempel.

Men man kan väl inte testa sig fram? Hur fortsätter man?

Om du vill använda formeln ovan så vill du alltså hitta en produkt (a₁+1)(a₂+1)... som har värdet 4.

Så exempelvis a₁ =1  a₂ =1

Kom fram till att det är det enda som fungerar eller har jag fel?

Det stämmer. Så då får du hitta alla tal < 100 som går att skriva som p¹q¹ (alltså pq helt enkelt) där p och q är olika primtal.

Finns det ett sätt att göra detta på ett snabbare vis? Tänker mest på en formel?

Kom att tänka på att det högst troligtvis inte finns extremt många kombinationer, då < 100

6,10,14,15,21,22,26,33,34,35,38,39,46,51,55,57,58,62,65,69,74,77,82,85,86,87,91,93,94,95

30 totalt.

(snodde från ChatGpt som listade alla)

Cristian0311 skrev:

Finns det ett sätt att göra detta på ett snabbare vis? Tänker mest på en formel?

Nja, inte vad jag vet.

Vissa problem handlar helt enkelt om att reducera problemet till något enklare att hantera. Du kunde ju tex. pröva varje positivt heltal mindre än 100, vilket är omständligt. Istället reducerade du problemet till att bara undersöka tal på formen $pq$, där p och q är skilda primtal, vilket är betydligt mer enklare.

Darth Vader skrev:

Cristian0311 skrev:

Finns det ett sätt att göra detta på ett snabbare vis? Tänker mest på en formel?

Nja, inte vad jag vet.

Vissa problem handlar helt enkelt om att reducera problemet till något enklare att hantera. Du kunde ju tex. pröva varje positivt heltal mindre än 100, vilket är omständligt. Istället reducerade du problemet till att bara undersöka tal på formen $pq$, där p och q är skilda primtal, vilket är betydligt mer enklare.

Yes uppfattat, har stött på sådant innan. Tar sin tid att testa, men men.

Tack för hjälpen! Fattade först inte din formel i spoilern, men nu i efterhand förstår jag :)

Darth Vader skrev:

Cristian0311 skrev:

Finns det ett sätt att göra detta på ett snabbare vis? Tänker mest på en formel?

Nja, inte vad jag vet.

Vissa problem handlar helt enkelt om att reducera problemet till något enklare att hantera. Du kunde ju tex. pröva varje positivt heltal mindre än 100, vilket är omständligt. Istället reducerade du problemet till att bara undersöka tal på formen $pq$, där p och q är skilda primtal, vilket är betydligt mer enklare.

Snabb fråga kring formeln d(N)=(α ₁​ +1)(α ₂​ +1)⋯(α _n​ +1)

Om jag har ett tresiffrigt tal, är det bara att skriva:

d(N)=(α ₁​ +1)(α ₂​ +1)(α ₃ +1) ?

Förresten, har den ett specifikt namn, alltså om den är välkänd?

Cristian0311 skrev:

Darth Vader skrev:

Visa föregående citat

Cristian0311 skrev:

Finns det ett sätt att göra detta på ett snabbare vis? Tänker mest på en formel?

Nja, inte vad jag vet.

Vissa problem handlar helt enkelt om att reducera problemet till något enklare att hantera. Du kunde ju tex. pröva varje positivt heltal mindre än 100, vilket är omständligt. Istället reducerade du problemet till att bara undersöka tal på formen $pq$, där p och q är skilda primtal, vilket är betydligt mer enklare.

Snabb fråga kring formeln d(N)=(α ₁​ +1)(α ₂​ +1)⋯(α _n​ +1)

Om jag har ett tresiffrigt tal, är det bara att skriva:

d(N)0=(α ₁​ +1)(α ₂​ +1)(α ₃ +1) ?

Yes, där $\alpha_{1}$, $\alpha_{2}$ och $\alpha_{3}$ är exponenterna på primtalen.

Förresten, har den ett specifikt namn, alltså om den är välkänd?

Ja, formeln är ganska känd. Tror dock inte den har något erkänt namn...

Cristian0311 skrev:

Finns det ett sätt att göra detta på ett snabbare vis? Tänker mest på en formel?

 

Kom att tänka på att det högst troligtvis inte finns extremt många kombinationer, då < 100

Du kan börja med att skriva upp alla primtal som kommer ifråga. Det minsta är 2, så det största måste vara mindre än 50.

Sedan är det bara att kombinera så produkten blir mindre än 100.

Hade det gällt t.ex. 1000 så skriver man nog ett datorprogram som räknar ut det.

Hade ni rekommenderat att man memoriserar primtal upp till 100? Ska skriva ett intagningsprov någon gång i februari tror jag, tänker att det kan vara bra. Vad tänker ni?

Cristian0311 skrev:

Hade ni rekommenderat att man memoriserar primtal upp till 100? Ska skriva ett intagningsprov någon gång i februari tror jag, tänker att det kan vara bra. Vad tänker ni?

Det är upp till dig. Men det är knappast nödvändigt eftersom man kan kolla om ett tal är ett primtal eller ej genom att betrakta dess delare.

Jag kan inte påstå att jag har memorerat primtalen upp till 50, men jag kan skriva ner dem med en smula eftertanke. Det enda sammansatta tal upp dit med faktorer större än 5 är 49 = 7*7.

Upp till 100: faktor 11 är enkel, de talen ser ut som 55, 77, båda siffrorna lika. De andra talen med bara faktorer > 5 är 7*13 = 91, och det var nog allt. Primtalen är då alla som inte är något av föregående och inte går att dela med 2, 3 eller 5.

Har jag missat nåt?

Cristian0311 skrev:

Hade ni rekommenderat att man memoriserar primtal upp till 100? Ska skriva ett intagningsprov någon gång i februari tror jag, tänker att det kan vara bra. Vad tänker ni?

För att kolla om ett tal är primtal kan det vara bra att kunna lite knep för att veta delbarhet: 

Delbarhet med 2: Om den sista siffran i talet är delbar med 2 (talet är jämnt)

Delbarhet med 3: Om siffersumman är delbar med 3.
Exempel 87.     $8+7 = 15$.     15 är delbar med 3 och då är 87 det också. Man kan även göra detta trick flera gånger. 
Exempelvis om vi har 8695. Då kan vi göra $8+6+9+5 = 28$,     28 blir då $2+8 = 10$.
10 är inte delbar med 3, och då är 8695 inte det heller.

Delbarhet med 5: Om den sista siffran är 5 eller 0

Delbarhet med 7 (lite mer komplicerad):
Tag bort den sista siffran i talet. Tag talet du har kvar och subtrahera 2 * den sista siffran. Om det talet är delbart med 7 är det ursprungliga talet också det. 

Exempelvis 245. Då tar vi bort den sista siffran, 5. Vi har alltså kvar 24. Då subtraherar $2 \cdot 5$
$24 - 2 \cdot 5 = 24 - 10 = 14$. 14 är delbar med 7, då är 245 också det. 

Precis som 3 kan vi göra denna regel flera gånger.
Om vi har 4326 tar vi $432 - 2\cdot 6=432 - 12 = 420$ 
Då tar vi $42 - 2 \cdot 0 = 42$
Sist tar vi $4 - 2 \cdot 2 = 0$
0 är delbar med 7, alltså är 4326 delbar med 7. 
(Om denna metod ger ett negativt tal som är delbar med 7, ex -7 eller -14 räknas det fortfarande som att talet är delbart med 7)

Delbarhet för 11 är samma sak som 3 men istället för att ta siffersumman så subtraherar man vartannat tal. 
Alltså: Ett tal är delbart med 11 om den alternerande siffersumman är delbar med 11
Exempelvis om vi vill kolla om typ 4213 är delbar med 11 tar vi $4-2+1-3=0$. Alltså delbar med 11. 


Vi kan använda alla dessa regler för att kolla om ett tal är primtal.
Exempel 97:
Då börjar vi med 2. Är talet jämnt? Nej
Är det delbart med 3? Siffersumman blir $9+7 = 16$. Men 16 är inte delbar med 3. Alltså är 97 inte delbar
Är det delbart med 5? Nej, talet slutar inte på 0 eller 5. 
Är det delbart med 7? Regeln ger $9 - 2 \cdot 7 = 9 - 14 = -5$. -5 är inte delbar med 7, Då är 97 inte delbar
Är det delbart med 11? Alternerande siffersumman blir $9-7 = 2$. 2 är inte delbar med 11, 97 är inte delbart med 11. 

Man behöver bara kolla delbarhet med primtal upp till roten ur talet man vill kolla (bra övning att tänka på varför!). Eftersom $\sqrt{97} \approx 9.8$ har vi visat att 97 är ett primtal. 

AlexMu skrev:

Cristian0311 skrev:

Hade ni rekommenderat att man memoriserar primtal upp till 100? Ska skriva ett intagningsprov någon gång i februari tror jag, tänker att det kan vara bra. Vad tänker ni?

För att kolla om ett tal är primtal kan det vara bra att kunna lite knep för att veta delbarhet: 

Delbarhet med 2: Om den sista siffran i talet är delbar med 2 (talet är jämnt)

Delbarhet med 3: Om siffersumman är delbar med 3.
Exempel 87.     $8+7 = 15$.     15 är delbar med 3 och då är 87 det också. Man kan även göra detta trick flera gånger. 
Exempelvis om vi har 8695. Då kan vi göra $8+6+9+5 = 28$,     28 blir då $2+8 = 10$.
10 är inte delbar med 3, och då är 8695 inte det heller.

Delbarhet med 5: Om den sista siffran är 5 eller 0

Delbarhet med 7 (lite mer komplicerad):
Tag bort den sista siffran i talet. Tag talet du har kvar och subtrahera 2 * den sista siffran. Om det talet är delbart med 7 är det ursprungliga talet också det. 

Exempelvis 245. Då tar vi bort den sista siffran, 5. Vi har alltså kvar 24. Då subtraherar $2 \cdot 5$
$24 - 2 \cdot 5 = 24 - 10 = 14$. 14 är delbar med 7, då är 245 också det. 

Precis som 3 kan vi göra denna regel flera gånger.
Om vi har 4326 tar vi $432 - 2\cdot 6=432 - 12 = 420$ 
Då tar vi $42 - 2 \cdot 0 = 42$
Sist tar vi $4 - 2 \cdot 2 = 0$
0 är delbar med 7, alltså är 4326 delbar med 7. 
(Om denna metod ger ett negativt tal som är delbar med 7, ex -7 eller -14 räknas det fortfarande som att talet är delbart med 7)

Delbarhet för 11 är samma sak som 3 men istället för att ta siffersumman så subtraherar man vartannat tal. 
Alltså: Ett tal är delbart med 11 om den alternerande siffersumman är delbar med 11
Exempelvis om vi vill kolla om typ 4213 är delbar med 11 tar vi $4-2+1-3=0$. Alltså delbar med 11. 


Vi kan använda alla dessa regler för att kolla om ett tal är primtal.
Exempel 97:
Då börjar vi med 2. Är talet jämnt? Nej
Är det delbart med 3? Siffersumman blir $9+7 = 16$. Men 16 är inte delbar med 3. Alltså är 97 inte delbar
Är det delbart med 5? Nej, talet slutar inte på 0 eller 5. 
Är det delbart med 7? Regeln ger $9 - 2 \cdot 7 = 9 - 14 = -5$. -5 är inte delbar med 7, Då är 97 inte delbar
Är det delbart med 11? Alternerande siffersumman blir $9-7 = 2$. 2 är inte delbar med 11, 97 är inte delbart med 11. 

Man behöver bara kolla delbarhet med primtal upp till roten ur talet man vill kolla (bra övning att tänka på varför!). Eftersom $\sqrt{97} \approx 9.8$ har vi visat att 97 är ett primtal. 

Tror jag kanske har en aning varför! :D

Har för mig att jag har sett en tabell med delbarhetsregler för alla tal 1-1000 men kan inte finna det. Med det sagt fann jag delbarhetsregler för primtal 1-1000: https://arxiv.org/pdf/math/0001012

(Påstår inte att man ska memorera alla... :D)

Darth Vader skrev:

Har för mig att jag har sett en tabell med delbarhetsregler för alla tal 1-1000 men kan inte finna det. Med det sagt fann jag delbarhetsregler för primtal 1-1000: https://arxiv.org/pdf/math/0001012

(Påstår inte att man ska memorera alla... :D)

Haha intressant! Det följer snabbt från beviset för delbarhetsregeln för 7 att man kan generalisera den till nästan vilket tal som helst. Kul att se att någon gjorde det för alla primtal under 1000