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 $2,3*10^{6}$ 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

${\frac {2^{x}}{x^{2}-1}}>x^{\sqrt {x}}2^{\frac {2x}{3}}$ för $x\geq 1024.$

Bevis: Det räcker att bevisa olikheten ${\frac {2^{x}}{x^{2}}}>x^{\sqrt {x}}2^{\frac {2x}{3}},x\geq 1024$

och denna olikhet är ekvivalent med

$f(x)=x\ln 2-2\ln x-{\sqrt {x}}\ln x-{\frac {2x\ln 2}{3}},f(x)>0,x\geq 1024$

$f'(x)={\frac {\ln 2}{3}}-{\frac {2}{x}}-{\frac {2+\ln x}{2{\sqrt {x}}}}$

$f''(x)={\frac {2}{x^{2}}}+{\frac {\ln x}{4x{\sqrt {x}}}}.$

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

${2n \choose k}\leq {2n \choose n}.$

Bevis: Påståendet är ekvivalent med

$(n!)^{2}\leq (2n-k)!k!\Leftrightarrow {\frac {n!}{k!}}\leq {\frac {(2n-k)!}{n!}}.$

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 $\operatorname {l_{p}} (n)$ av p i n som det största naturliga tal k, för vilket $p^{k}\mid n.$

Lemma: 3 Om m och n är positiva heltal, gäller det att $\operatorname {l_{p}} (mn)=\operatorname {l_{p}} (m)+\operatorname {l_{p}} (n)$ och om $n\mid m$ , att $\operatorname {l_{p}} (m/n)=\operatorname {l_{p}} (m)-\operatorname {l_{p}} (n)$ .

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

$0\leq \left\lfloor {\frac {2n}{p^{k}}}\right\rfloor -2\left\lfloor {\frac {n}{p^{k}}}\right\rfloor \leq 1.$

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

$n=\left\lfloor {\frac {n}{p^{k}}}\right\rfloor p^{k}+r,0\leq r<p^{k}$

$2n=2\left\lfloor {\frac {n}{p^{k}}}\right\rfloor p^{k}+2r,0\leq 2r<2p^{k}$

Det följer att

$\left\lfloor {\frac {2n}{p^{k}}}\right\rfloor -2\left\lfloor {\frac {n}{p^{k}}}\right\rfloor =\{0,1\},$

0 om $2r<p^{k}$ och 1 om $2r\geq p^{k}.$

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

$\prod _{n+2\leq p\leq 2n+1}p\leq {{2n+1} \choose n}$

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

${{2n+1} \choose n}\leq 4^{n}.$

Bevis Påståendet följer av att

$2{{2n+1} \choose n}={{2n+1} \choose n}+{{2n+1} \choose {n+1}}\leq \sum _{k=0}^{2n+1}{{2n+1} \choose k}=(1+1)^{2n+1}=2^{2n+1}=2*4^{n}$

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

$\operatorname {l_{p}} (n!)=\sum _{k=1}^{\infty }\left\lfloor {\frac {n}{p^{k}}}\right\rfloor .$

Bevis Vi noterar att

$\left\lfloor {\frac {n}{p^{k}}}\right\rfloor =|\{j\in \mathbb {Z} ;1\leq j\leq n,p^{k}\mid j\}|.$

Definiera för $k\in \mathbb {Z} _{+}$ funktionen $f_{k}:\mathbb {Z} _{+}\longrightarrow \{0,1\}$ genom

$f_{k}(j)={\begin{matrix}1&{\mbox{om }}p^{k}\mid j,\\0&{\mbox{annars.}}\end{matrix}}$

Då är

$\operatorname {l_{p}} (j)=\sum _{k=1}^{\infty }f_{k}(j).$

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,

$\operatorname {l_{p}} ((m+1)!)=\operatorname {l_{p}} (m!)+\operatorname {l_{p}} (m+1)=\sum _{k=1}^{\infty }\left\lfloor {\frac {m}{p^{k}}}\right\rfloor +\sum _{k=1}^{\infty }f_{k}(m+1)$

$=\sum _{k=1}^{\infty }(\left\lfloor {\frac {m}{p^{k}}}\right\rfloor +f_{k}(m+1))$

$=\sum _{k=1}^{\infty }(|\{j\in \mathbb {Z} ;1\leq j\leq m,p^{k}\mid j\}|+f_{k}(m+1))$

$=\sum _{k=1}^{\infty }(|\{j\in \mathbb {Z} ;1\leq j\leq m+1,p^{k}\mid j\}|=\sum _{k=1}^{\infty }\left\lfloor {\frac {m+1}{p^{k}}}\right\rfloor$

Summan i satsen innehåller bara ändligt många termer skilda från noll. Om $n\in \mathbb {Z} _{+},$ kan vi låta k löpa från 1 till $\left\lfloor \operatorname {log_{p}} (n)\right\rfloor$ .

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

$\operatorname {l_{p}} {{2n} \choose n}\leq \operatorname {log_{p}} {2n}.$

Om $p>{\sqrt {2n}}$ så är

$\operatorname {l_{p}} {{2n} \choose n}=\left\lfloor {\frac {2n}{p}}\right\rfloor -2\left\lfloor {\frac {n}{p}}\right\rfloor \leq 1.$

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

$\operatorname {l_{p}} {{2n} \choose n}=\operatorname {l_{p}} {(2n)!}-2\operatorname {l_{p}} {(n!)}=\sum _{k=1}^{\left\lfloor \operatorname {log_{p}} (2n)\right\rfloor }\left\lfloor {\frac {2n}{p^{k}}}\right\rfloor -2\sum _{k=1}^{\left\lfloor \operatorname {log_{p}} (n)\right\rfloor }\left\lfloor {\frac {n}{p^{k}}}\right\rfloor =\sum _{k=1}^{\left\lfloor \operatorname {log_{p}} (2n)\right\rfloor }\left(\left\lfloor {\frac {2n}{p^{k}}}\right\rfloor -2\left\lfloor {\frac {n}{p^{k}}}\right\rfloor \right)\leq \left\lfloor \operatorname {log_{p}} (2n)\right\rfloor \leq \operatorname {log_{p}} (2n)$

Det andra påståendet i satsen följer av lemma 4 och raden ovan om vi observerar att eftersom $\left\lfloor \operatorname {log_{p}} (2n)\right\rfloor \leq 1$ så består summan av högst en term.

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

$n\#=\prod _{p\leq n}p\leq 4^{n}$

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

$m\#=(m-1)\#\leq 4^{m-1}\leq 4^{m}$

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

$m\#=(2k+1)\#=\prod _{p\leq 2k+1}p=\left(\prod _{p\leq k+1}p\right)\left(\prod _{k+2\leq p\leq 2k+1}p\right)=(k+1)\#\prod _{k+2\leq p\leq 2k+1}p\leq 4^{k+1}{{2k+1} \choose k}\leq 4^{k+1}4^{k}=4^{m}$

enligt induktionsantagandet och lemma 5 och 6.

Sats 4 Det gäller att ${{2n} \choose n}\geq {\frac {4^{n}}{2n+1}},n\in \mathbb {N} .$

Bevis Detta gäller enligt binomialsatsen och lemma 2

$4^{n}=2^{2n}=(1+1)^{2n}=\sum _{k=0}^{2n}{2n \choose k}\leq \sum _{k=0}^{2n}{2n \choose n}=(2n+1){2n \choose n}$

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:

${\sqrt {2n}}<{\frac {2n}{3}}<2n-1.$

Om p är ett primtal, och

${\frac {2n}{3}}<p\leq n,$

gäller det enligt sats 2

$0\leq \operatorname {l_{p}} {{2n} \choose n}=\left\lfloor {\frac {2n}{p}}\right\rfloor -2\left\lfloor {\frac {n}{p}}\right\rfloor \leq 2-2=0.$

Det följer att p inte delar $2n \choose n$ .

Om primtalet p delar denna centrala binomialkoefficient, så gäller det att $p\mid (2n)!$ , och därför att $p\mid k$ 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

$p\leq {\frac {2n}{3}}$ eller p = 2n - 1, eftersom inte heller 2n - 2 är ett primtal. Om p = 2n - 1 är ett primtal, så är

$\operatorname {l_{p}} {{2n} \choose n}\leq 1.$

Vi får därför att

${{2n} \choose n}=\prod p^{\operatorname {l_{p}} {{2n} \choose n}}\leq \left(\prod _{p\leq {\sqrt {2n}}}p^{\operatorname {l_{p}} {{2n} \choose n}}\right)\left(\prod _{{\sqrt {2n}}<p\leq {\frac {2n}{3}}}p^{\operatorname {l_{p}} {{2n} \choose n}}\right)(2n-1)$ (1)

Enligt sats 2 är

$\prod _{p\leq {\sqrt {2n}}}p^{\operatorname {l_{p}} {{2n} \choose n}}\leq \prod _{p\leq {\sqrt {2n}}}(2n)\leq (2n)^{\sqrt {2n}},$

eftersom antalet primtal p, sådant att $p\leq {\sqrt {2n}}$ , inte överstiger ${\sqrt {2n}}$ . Enligt samma sats gäller det att

$\operatorname {l_{p}} {{2n} \choose n}\leq 1,$ om $p>{\sqrt {2n}}$ .

Därför är

$\prod _{{\sqrt {2n}}<p\leq {\frac {2n}{3}}}p^{\operatorname {l_{p}} {{2n} \choose n}}\leq \prod _{{\sqrt {2n}}<p\leq {\frac {2n}{3}}}p\leq \prod _{p\leq {\frac {2n}{3}}}p=\left({\frac {2n}{3}}\right)\#\leq 4^{\frac {2n}{3}}$