Bertrands postulat

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 de  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 , Bertrand-Tjebysjovs sats, 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
För att kunna bevisa satsen måste några hjälpsatser användas.

Lemma: 1 Det gäller att

 för 

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  och 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 raden ovan om vi observerar att eftersom  så består summan av högst en term.

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 ser man att olikheten är uppfylld eftersom produkten är tom. Antag att m ≥ 3 och att olikheten gäller för 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 är udda och skriv m = 2k + 1. 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
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 3.
Med detta kan vi därför skriva om (1) till

och om vi skriver om uttrycket med sats 4 får vi olikheten

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
 Oppermanns förmodan

Satser om primtal