Visa att: Oändligt många primtal

Kunde rätt mycket redan innan kursen börjar, eftersom jag är allmänt intresserad av matematik. Det är mest bara bevis, visa att eller liknande uppgifter hela tiden. Går det fort så vipps kan man bli klar med en veckas planering på ett par timmar ibland.

Värre är det i analysen för vissa partialbråksuppdelningsuppgifter tar fan en timme att lösa.

Låt A_{n} = (p_1 * p_2 * ... * p_n)-1.
Visa att det finns oändligt många primtal (eller påpeka det enkom).

Välj ett godtyckligt k>1, då gäller att A_{k} är kongruent med 5 modulo 6, ty p_1 * p_2 = 2*3 = 6.

För varje sådan produkt A_{k}, k>1, gäller ett av följande:
1. A_{k} är ett primtal, och är kongruent med 5 mod 6.
2. A_{k} är inte ett primtal, men då alla tal kan primtalsfaktoriseras måste A_{k} minst ha en faktor t sådan att t är kongruent med 5 mod 6. Detta då alla primtal över 3 kan skrivas på formen 6k +/- 1, dvs. är kongruenta antingen med 1 eller -1 mod 6.

Vi har A_{k} ≡ -1 (mod 6), och A_{k} = (p_a)..(p_n). Då det för varje p gäller att p ≡ 1 eller -1 (mod 6) måste ju minst 1 av dessa p vara kongruent med 5 mod 6.

Då |N \ {0,1,2}| fortf är aleph 0 gäller att det finns oändligt många produkter A_{k} och därmed måste det finnas oändligt många primtal som är på formen 6k-1, k>0.

Har kanske inte betydelse här, men vad betyder enkom?

Då menar du att k är ett heltal mellan 2 och n? Dvs egentligen här uppe menar du A_{2}? Eftersom du verkar ta de två första primtalen. Men du menar att det räcker att säga såhär, eftersom då faktorn 6 alltid alltid finns med för alla heltal k så är resten av hela följden förutom -1 då, av ändligt antal primtal alltid kongruenta 0 modulo 6. I slutet subtraherar man ju 1, så då är hela skiten alltså alltid kongruent med -1 modulo 6 och då såklart modulo 5.

Helt med på, så långt har jag kommit också.

Varför är detta så säkert då? Jag säger inte att du har fel, vill bara ha extremt mycket motiveringar. Det känns ju svårt att visa eftersom man har två termer. Hur är det så säkert att det finns en sådan faktor t?

Hur vet man detta då? Ganska centralt om beviset skall gälla, jag måste veta om jag själv skall kunna redovisa detta.

Varför är A_{k} ≡ -1 (mod 6)?

När du skriva stora N här så menar du mängden av de naturliga talen? Om dina beloppstecken betyder alltså antalet element i denna mängden?

Gör så här istället, för att göra det mer tydligt och enklare:

1. Konstatera att 2 och 3 är primtal.
2. Låt mängden A_n vara {2, 3, ... p_n}, där p_n är det n:te primtalet.
3. Låt k_n vara produkten av alla element i A_n minus ett.
4. k_n är kongruent med 5 mod 6.
5. Antag att det finns ett ändligt antal primtal som är kongruenta med 5 mod 6. Välj det största sådana talet och låt q vara dess index (dvs. talet är det q:te primtalet).
6. k_q kan antingen vara
a) Ett primtal, men k_n är relativt prim med alla primtal i A_n, alltså är A_n inte fullständigt ty k_n saknas. Saken är klar.
b) Icke ett primtal, men alla tal kan primtalsfaktoriseras. Minst ett av de primtal som ingår i faktoriseringen av k_q är kongruent med 5 mod 6 därför som ALLA primtal är kongruenta med antingen 1 eller -1 mod 6 (förutom 2 och 3). -1 kan ju endast erhållas genom 1*1*1*1*....*-1 (minst ett -1!).

Att alla primtal är på formen 6k+/-1 följer av:
6|(6k+0)
2|(6k+2)
3|(6k+3)
2|(6k+4)

Således är inte A_q komplett, ty det primtal (minst ett) som är kongruent med -1 mod 6 ingår ej - vilket följer av att k_q är relativt prima med alla primtal i A_q.

Saken är klar.

på 6a) här. k_n är relativt prim med alla primtal i A_n fattar jag. Varför skulle inte p_q kunna finnas i A_n? Det q:te primtalet skulle kunna vara p_n-1 eller? (nu är det ju inte så men i min hjärna är det så).

Okey, fan va bra.

Riktigt bra motivering, jag hänger med nu.

Jag har svårt att förstå det här med fullständighet, kompl,ett osv. Antagligen för att jag inte lärt mig det än. Men jag tycker liksom att man liksom är klar utan att säga detta? Eller? Med tanke på att man redan har visat att alla primtal modulo 6 är kongruenta med 5 eller 1.

Låt A_n vara {2,3,...p_n}, dvs mängden av alla primtal upp till det n:te primtalet.
Där n∈ℕ, p₁ = 2

Antag:
Alla primtal utom 2 och 3 kan skrivas på formen 6k±1.

Motivering:

6k+0 ≡ 0 (mod 6,3,2)
6k+1 ≡ 1 (mod 6,3,2)
6k+2 ≡ 0 (mod 2)
6k+3 ≡ 0 (mod 3)
6k+4 ≡ 0 (mod 2)
6k+5 ≡ -1 (mod 6,3,2) ⇔
6k+5 ≡ 5 (mod 6,3,2)
Där k∈ℕ, k≠1

De enda uttrycken som inte är kongruenta med 0 modulo 6 eller primtalsfaktorer av modulo 6 är just 6k±1. Nu skall jag bara visa att primtalen är oändligt många på formen 6k±1.

Definierar B_n:
B_n är produkten av alla primtal fram till det n:te primtalet och sedan minus 1.

Alltså:

B_n = (2·3·p₃·...·p_n)-1

Då är:

B_n ≡ -1 (mod 6) ⇔
B_n ≡ 5 (mod 6)

Eftersom 2·3 är de första två primtalen, och deras produkt är lika med 6. 6 är kongruent med 0 modulo 6. Eftersom -1 = -1, så är B_n kongruent med -1 modulo 6 som är kongruent med 5 modulo 6.

Då gäller att B_n antingen är ett primtal, eller inte ett primtal:

1) Om B_n är ett primtal så är saken klar, då är B_n kongruent med 5 modulo 6.

2) Om B_n inte är ett primtal så kan B_n faktoriseras i ändligt många primtal enligt aritmetikens fundamentalsats. Men eftersom alla primtal, utom 2 och 3, kan skrivas på formen 6k±1 så är de antingen kongruenta med 1 modulo 6 eller 5 modulo 6 (-1 mod 6).

Då det för varje primtal q gäller att:

q ≡ 1 (mod 6)
eller
q ≡ -1 (mod 6)

B_n som inte är ett primtal kan då faktoriseras som:

B_n = q₁q₂...q_n

Alla q är kongruenta med 1 eller -1 modulo 6. Eftersom B_n är kongruent med -1 modulo 6, så är minst ett q i B_n:s faktorisering alltid kongruent med -1 modulo 6. Enligt Euklides bevis så finns det oändligt många primtal, därför kan mängden A_n göras oändligt stor. Det betyder att det finns oändligt många faktorer i B_n.

Det finns två utfall, om B_n är ett primtal så är det klart. Om B_n inte är ett primtal så vet vi att det finns minst en faktor av B_n som är kongruent med -1 modulo 6.

Här fattar jag fan inte. Tänk om det låt oss säga att vid B_12 så är alla B efter detta inte ett primtal. Då har man ju inte visat att det är oändligt många primtal som är kongruenta med 5 modulo 6? Det spelar väl ingen roll om det är minst en faktor i B_n som är kongruent med -1 modulo 6? Om nu 5 ingår i varje B_n efter låt oss säga 12, så gäller det ju alltid, men resten av alla B kommer ju inte vara primtal. Vi vet ju då inte om det finns oändligt många primtal som är kongruenta med 5 modulo 6?

Poängen är att 5 inte kan ingå i alla B_n efter B_12, efter 5 = p_3 redan finns med som en faktor i

p_1 ... p_n

så alltså kan inte 5 dela

p_1 ... p_n - 1.

Jag tror det är lättare att formulera konstruktionen som ett motsägelsebevis: Antag att det bara finns ändligt många primtal på formen 6k+5, och låt det största vara det n:te primtalet. Då kan inte B_n vara delbart med något primtal 6k+5 (eftersom alla sådana är ≤ p_n och förekommer alltså som en faktor i p_1 ... p_n.) Däremot så är B_n ≡ 5 (mod 6), och detta ger en motsägelse.

Hmm men om jag gör såhär då. Samma resonemang som ovan.

Minst en av de måste vara kongruent med -1 mod 6. Om inte så skulle alla vara kongruenta med 1 modulo 6, och ur vår definition av B_n så ser man att så inte är fallet, därför är det sant.

Om B_n är primt så är det klart. Om B_n inte är primt så kan vi faktorisera B_n. Då finns det ett primtal q_l som är kongruent med 5 modulo 6, eftersom det finns minst ett sådant tal. Men q_l finns inte i vår lista A_n. Vi vet att q_l delar B_n men så vi har definierat A_n, som en lista av irreducibla tal så kan inte q_l dela något utav dessa tal, alltså kan vi lägga till q_l till vår lista och nu har vi gjort listan ett större med ett till primtal som är kongruent med 5 modulo 6.

YES där satt den! Det blir ju ett slags induktionsargument. Kan jag formulera mig bättre här? Vill kunna skriva det mer matematiskt om det går.

Det är ett godtagbart resonemang eller? Jag tror verkligen att jag fattar det nu.

Så länge du fattar så är det bra. Jag tycker att det är ett godtagbart resonemang (om man då antar att du också skriver att du väljer n så att p_n är det största primtalet på form 6k+5, vilket jag antar), men något otydligt. Jag skulle skriva det (kanske lite övertydligt) såhär:

Lemma: Låt N vara ett positivt heltal så att N ≡ 5 (mod 6). Då existerar minst ett primtal p, p ≡ 5 (mod 6), så att p | N.

Bevis: Av aritmetikens fundamentalsats vet vi att vi kan skriva N som en produkt av primtal, säg N = q_1 ... q_n. Om något av dessa q_i är kongruent med 5 (mod 6) så kan vi ta p = q_i, och beviset är klart. Så antag att så inte är fallet.

Jag hävdar nu att samtliga q_i måste vara 1 (mod 6): Ty tag ett q_i.

Om det är 0, 2 eller 4 (mod 6), så måste 2 | q_i, och alltså är q_i = 2 (eftersom q_i är ett primtal). Men då gäller att 2 | N, vilket motsäger att N ≡*5 (mod 6).

Om det är 3 (mod 6), så måste 3 | q_i, och alltså är q_i = 3. Men då gäller att 3 | N, vilket också motsäger att N ≡ 5 (mod 6).

Vi har redan antagit att q_i inte är kongruent med 5 (mod 6).

Kvar återstår alltså bara att q_i ≡ 1 (mod 6).

Eftersom detta gäller för alla q_i, så får vi dessutom att N ≡ q_1 ... q_n ≡ 1 (mod 6), vilket är en motsägelse mot att N ≡ 5 (mod 6). Därför måste vårt antagande att inget q_i är 5 vara falskt, och det bevisar lemmat.


Sats: Det finns bara oändligt många primtal på formen 6k + 5.

Bevis: Antag motsatsen. Då finns ett högsta primtal på formen 6k+5; låt säga att detta primtal är det n:te primtalet, och kalla det p_n. Låt också p_i beteckna det i:te primtalet.

Notera att eftersom p_n är det högsta primtalet på formen 6k+5 så återfinns alla primtal på formen 6k+5 som p_i för något i ≤ n.

Låt nu

N = p_1 p_2 ... p_n - 1.

Eftersom p_1 = 2 och p_2 = 3, så får vi att 6 | p_1 p_2 ... p_n, och alltså är N ≡ 5 (mod 6).

Enligt lemmat så finns då ett primtal q på formen 6k+5 så att q | N.

Men notera att q inte kan vara något p_i för i ≤ n, ty för alla sådana i gäller att N ≡ -1 (mod p_i), vilket skulle motsäga att q | N.

Alltså är q > p_n (eftersom p_1, ..., p_n utgör alla primtal ≤ p_n).

Men detta motsäger att p_n skulle vara det största primtalet på formen 6k+5. Alltså är antagandet att det bara finns ändligt många primtal på formen 6k+5 felaktigt, och satsen är bevisad.

Lemma:
Alla primtal utom 2 och 3 kan skrivas på formen 6k±1.

Bevis:

6k+0 ≡ 0 (mod 6,3,2)
6k+1 ≡ 1 (mod 6,3,2)
6k+2 ≡ 0 (mod 2)
6k+3 ≡ 0 (mod 3)
6k+4 ≡ 0 (mod 2)
6k+5 ≡ -1 (mod 6,3,2) ⇔
6k+5 ≡ 5 (mod 6,3,2)
Där k∈ℕ, k≠0

De enda uttrycken som inte är kongruenta med 0 modulo 6 eller primtalsfaktorer av modulo 6 är just 6k±1.
VSB

Sats:
Det finns oändligt många primtal som är kongruenta med 5 modulo 6.

Antar motsatsen, då låter jag:

A_n = 2·3·p₁·...·p_n-1
Där p_n är det n:te och sista primtalet som kan skrivas på formen 6k+5

Om A_n är ett primtal så är saken klar, det finns dock ett till utfall, det är när A_n inte är ett primtal.

Då kan A_n faktorisers enligt:

A_n = q₁·q₂·...·qₐ

Där q är vilka primtal som helst.

Eftersom A_n per definition är kongruent med 5 modulo 6 och därmed även -1 modulo 6 så måste minst ett q_i vara kongruent med -1 modulo 6. Det gäller eftersom alla primtal q_i är kongruenta med antingen 1 eller -1 modulo 6. Om nu hela A_n skall vara kongruent med -1 modulo 6, så är garanterat minst ett q_i det.

Men då finns inte detta primtal q_i som ett av våra primtal p. Eftersom vi vet att q_i delar A_n men ur vår definition så är det garanterat att varken 2, 3 eller något p₁ till p_n delar A_n, för då måste de också dela -1. Eftersom inga primtal är delare till -1 så kan vi lägga till q_i till vår lista, och därmed har den blivit ett större.
VSB

Nu är jag nöjd i alla fall.

Tack som fan för hjälper allesammans.

Mvh

Det som hittills har tagit upp mest plats per uppgift för mig var att undersöka extrempunkter i flervar

Lemma:
Alla primtal utom 2 och 3 kan skrivas på formen 6k±1.

Bevis:

6k+0 ≡ 0 (mod 6,3,2)
6k+1 ≡ 1 (mod 6,3,2)
6k+2 ≡ 0 (mod 2)
6k+3 ≡ 0 (mod 3)
6k+4 ≡ 0 (mod 2)
6k+5 ≡ -1 (mod 6,3,2) ⇔
6k+5 ≡ 5 (mod 6,3,2)
Där k∈ℕ

De enda uttrycken som inte är kongruenta med 0 modulo 6 eller primtalsfaktorer av 6 är just 6k±1.
VSB

Sats:
Det finns oändligt många primtal som är kongruenta med 5 modulo 6.

Antar motsatsen, låt då:

A_n = 2·3·p₁·...·p_n-1
Där p_n är det n:te och största primtalet som kan skrivas på formen 6k+5
Där n∈ℕ

Om A_n är ett primtal så är saken klar, det finns dock ett till utfall, det är när A_n inte är ett primtal.

Då kan A_n faktorisers enligt aritmetikens fundamentalsats:

A_n = q₁·q₂·...·q_m
Där q är vilka primtal som helst utom 2 och 3.
Där m∈ℕ

Eftersom A_n per definition är kongruent med 5 modulo 6 och därmed även -1 modulo 6 så måste minst ett q_a, där a∈[1,m] vara kongruent med -1 modulo 6, eftersom alla q är kongruenta med 1 eller -1 modulo 6 enligt lemmat. Så måste alltså VL ha minst en negativ etta, för att hela faktoriserade A_n skall vara kongruent med -1 modulo 6, och det är A_n per definition.

Men då finns inte detta primtal q_a som ett av våra primtal p_i, där i∈[1,n].

Motivering:

q_a | q₁·q₂·...·q_m ⇔ q_a | A_n

Men q_a kan inte vara något p_i, ty för alla sådana p_i gäller att:

A_n ≡ -1 (mod p_i)

Vilket motsäger att att q_a är vårat p_i. Vilket gör att i > n, därmed finns även A_i, som innehåller ett primtal mer än A_n.
VSB