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 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 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

\frac{2^x}{x^2-1}> x^\sqrt x 2^\frac{2x}{3}, x\ge 1024


Bevis: Det räcker att bevisa olikheten \frac{2^x}{x^2}> x^\sqrt x 2^\frac{2x}{3}, x\ge 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\ge 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}\le {2n\choose n}


Bevis: Påståendet är ekvivalent med

 (n!)^2 \le (2n-k)!k! \Leftrightarrow\frac{n!}{k!} \le \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  m\mid n, 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\le\left\lfloor\frac{2n}{p^k}\right\rfloor - 2\left\lfloor\frac{n}{p^k}\right\rfloor\le 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\le r\le p^k

 2n = 2\left\lfloor\frac{n}{p^k}\right\rfloor p^k + r, 0\le 2r\le 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 , 1 om 2r\ge p^k


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

\prod_{n+2\le p\le 2n+1} p\le {{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}\le 4^n

Bevis Påståendet följer av att

 2{{2n+1}\choose n}= {{2n+1}\choose n}+ {{2n+1}\choose {n+1}}\le\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{2n}{p^k}\right\rfloor

Bevis Vi noterar att

 \left\lfloor\frac{2n}{p^k}\right\rfloor = |\{ j \in \mathbb{Z}; 1\le j \le 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\le j \le m , p^k\mid j\} | +  f_k (m + 1))

 = \sum_{k=1}^{\infty} (|\{ j \in \mathbb{Z}; 1\le j \le 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}}\le\operatorname{log_p}{2n}

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

 \operatorname{l_p}{{{2n}\choose n}} =\left\lfloor\frac{2n}{p^k}\right\rfloor - 2\left\lfloor\frac{n}{p^k}\right\rfloor\le 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)\le\left\lfloor\operatorname{log_p}(2n)\right\rfloor\le\operatorname{log_p}(2n)

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

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

Om k > 1 och  p > \sqrt{2n}


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

 n\# = \prod_{p\le n} p\le 4^n


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

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

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

 m\# = (2k + 1)\# = \prod_{p\le 2k+1} p =    \left(\prod_{p\le k+1} p\right)\left(\prod_{k+2\le p\le k+1} p\right) =  (k + 1)\#\prod_{k+2\le p\le k+1} p \le 4^{k+1}{{2k+1}\choose k}\le 4^{k+1}4^{k}= 4^m

enligt induktionsantagandet och lemma 5 och 6.


Sats 4 Det gäller att  {{2n}\choose n}\le\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}\le \sum_{k=0}^{2n} {2n \choose n} = (2n + 1){2n \choose n}

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:

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

Om p är ett primtal, och

 \frac{2n}{3}< p\le n,

gäller det enligt sats 2

 0\le\operatorname{l_p}{{{2n}\choose n}} =\left\lfloor\frac{2n}{p^k}\right\rfloor - 2\left\lfloor\frac{n}{p^k}\right\rfloor\le 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\le\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}}\le 1.

Vi får därför att

 {{2n}\choose n} =  \prod p^{\operatorname{l_p}{{{2n}\choose n}}}\le\left( \prod_{p\le\sqrt{2n}} p^{\operatorname{l_p}{{{2n}\choose n}}}\right)\left(\prod_{\sqrt{2n} < p \le\frac{2n}{3}} p^{\operatorname{l_p}{{{2n}\choose n}}}\right) (2n-1) (1)

Enligt sats 2 är

  \prod_{p\le\sqrt{2n}} p^{\operatorname{l_p}{{{2n}\choose n}}}\le \prod_{p\le\sqrt{2n}}(2n)\le (2n)^\sqrt{2n},

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

 \operatorname{l_p}{{2n}\choose n}\le 1, om  p > \sqrt{2n}.

Därför är

\prod_{\sqrt{2n} < p \le\frac{2n}{3}} p^{\operatorname{l_p}{{{2n}\choose n}}}\le  \prod_{\sqrt{2n} < p \le\frac{2n}{3}} p\le\prod_{p\le\frac{2n}{3}} p = 
\left\lfloor\frac{n}{p^k}\right\rfloor\#\le 4^{\left\lfloor\frac{n}{p^k}\right\rfloor}\le 4^{\frac{2n}{3}}

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

 {{2n}\choose n}\le {2n}^\sqrt{2n} 4^\frac{2n}{3}(2n-1)

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

 \frac{4^n}{4n^2 - 1}\le{2n}^\sqrt{2n} 4^\frac{2n}{3}.

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

 (p_k)_{k=0}^10 = ( 4, 5,7,11,19,31,59,113,223,443,883)

i vilket alla element utom  p_0 är primtal.

Det gäller att  p_{k+1} < 2p_k -2, då k = 0,1,...,9. Om 4 ≤ n ≤ 511,

väljer vi k, så att  p_k \le n < p_{k+1}  . Då är 2n-2 \ge 2p_k -2 > p_{k+1} då får vi fram att för primtalet  p_{k+1} gäller  n< p_{k+1} \le 2n-2.

Därmed har vi bevisat Bertrands postulat.

Se även[redigera | redigera wikitext]