Bertrands postulat

Från Wikipedia
Hoppa till: navigering, sök

Bertrands postulat säger att för varje heltal n > 3 så finns det minst ett primtal p som uppfyller n < p < 2n - 2. Ett mer elegant sätt att skriva formeln (men svagare formulerat) kan sägas vara;

Om n är ett positivt heltal finns det minst ett primtal p så att n < p ≤ 2n.

Satsen formulerades av matematikern Joseph Bertrand år 1845 och han visade den även för det första heltalen. Men satsen bevisades först 1850 av den ryska matematikern Pafnutij Lvovitj Tjebysjov (mer känd under den engelska versionen av hans efternamn Chebyshev) och satsen går även under namnet Bertrand-Chebyshevs sats eller Chebyshevs sats.

Beviset nedanför är baserat på det elementära beviset för den svagare formuleringen som publicerades av matematikern Paul Erdős från 1932, omgjort så att den bevisar den starkare satsen.


Hjälpsatser[redigera | redigera wikitext]

För att kunna bevisa satsen måste några hjälpsatser användas.


Lemma: 1 Det gäller att


Bevis: Det räcker att bevisa olikheten

och denna olikhet är ekvivalent med

Eftersom f``(x) ≥ 0 då x ≥ 1 är f` växande på intervallet [1,∞[, samt med det att f`(1024) > 0 och f(1024)>0 följer det att f(x)>0 då x ≥ 1024.


Lemma: 2 Om k och n är naturliga tal och 0 ≤ k ≤ 2n gäller det att


Bevis: Påståendet är ekvivalent med

Denna olikhet kan skrivas n(n-1)...(n-(n-k-1)) ≤ (2n-k)(2n-k-1)...(2n-k -(n-k-1)) och visar att olikheten är giltig, ty (n-i) ≤ (2n-k-i), då i = 0,...,n-k-1.

Man kan också se olikheten i Pascals triangel. Det n:te talet på rad 2n, som alltid är i mitten, kommer att vara större än alla andra (k) på samma rad.


Definition 1

Om p är ett primtal och n ett positivt heltal, definierar vi exponenten av p i n som det största naturliga tal k, för vilket

Lemma: 3 Om m och n är positiva heltal, gäller det att och om , att .

Bevis: Påståendet är en följd av aritmetikens fundamentalsats.


Lemma: 4 Om n är ett naturligt tal och p ett primtal gäller det att

Bevis Det gäller enligt divisionsalgoritmen, att det finns ett heltal r, sådant att:

Det följer att

0 om , 1 om


Lemma: 5 om n är ett naturligt tal, gäller det att

där produkten är över primtal p.

Bevis: Om produkten är tom, är olikheten uppfylld. I annat fall delar vart och ett av de ingående primtalen högerledet, vilket därför också delas av deras produkt.

(se. Primultet)


Lemma: 6 Om n är ett naturligt tal, gäller det att

Bevis Påståendet följer av att


Sats: 1 Om n är ett naturligt tal och p ett primtal är

Bevis Vi noterar att

Definiera för funktionen genom

Då är

Nu kan vi genomföra beviset av satsen med induktion över n. Då n = 0, är påståendet trivialt sant. Antag att likheten gäller, då n = m. Då är, enligt lemma 3,

Summan i satsen innehåller bara ändligt många termer skilda från noll. Om kan vi låta k löpa från 1 till .


Sats: 2 Om n är ett positivt heltal och p ett primtal, så är

Om , så är

Bevis Enligt lemma 3, sats 1 och lemma 4 är

Det andra påståendet i satsen följer av lemma 4 och det faktum att

Om k > 1 och


Sats: 3 Om n är ett naturligt tal, så gäller det att


Bevis Påståendet kan bevisas med induktion över n. Då 0 ≤ n ≤ 2, finns man att olikheten är uppfylld genom uträkning. Antag att m ≥ 3, och att olikheten gäller, då n < m.

Om m är ett jämnt tal, så är m inte ett primtal, och man får att

enligt induktionsantagandet. Antag att m = 2k + 1 och är udda. Då är

enligt induktionsantagandet och lemma 5 och 6.


Sats 4 Det gäller att

Bevis Detta gäller enligt binomialsatsen och lemma 2

Bevis för Bertrands postulat[redigera | redigera wikitext]

Sats: Bertrands postulat

Om n > 3 är ett heltal, så finns det något primtal p, sådant att n < p < 2n -2.

Bevis Vi bevisar först påståendet, då n ≥ 512. Då gäller påståendet:

Om p är ett primtal, och

gäller det enligt sats 2

Det följer att p inte delar .

Om primtalet p delar denna centrala binomialkoefficient, så gäller det att , och därför att för något heltal k, sådant att 1 ≤ k ≤ 2n. Eftersom 2n inte är ett primtal, så gäller det att p > 2n.

Antag nu att det inte finns något primtal p, sådant att n < p < 2n - 2. Om primtalet p delar binomialkoefficienten, så gäller det då att

eller p = 2n - 1, eftersom inte heller 2n - 2 är ett primtal. Om p = 2n - 1 är ett primtal, så är

Vi får därför att

(1)

Enligt sats 2 är

eftersom antalet primtal p, sådant att , inte överstiger . Enligt samma sats gäller det att

om .

Därför är

enligt sats 4. Med detta kan därför skriva om (1) till

och om vi skriver om uttrycket med sats 5 kan vi skriva olikheten som

Detta strider mot lemma 1 (där x = 2n) och därför visar vi Bertrands postulat, då n ≥ 512.

För återstående element (då 4 ≤ n ≤ 511). Betrakta följande

i vilket alla element utom är primtal.

Det gäller att då k = 0,1,...,9. Om 4 ≤ n ≤ 511,

väljer vi k, så att . Då är då får vi fram att för primtalet gäller

Därmed har vi bevisat Bertrands postulat.

Se även[redigera | redigera wikitext]