Legendreův vzorec

Z Wikipedie, otevřené encyklopedie
Skočit na navigaci Skočit na vyhledávání

Legendreův vzorec dovoluje vypočítat nejvyšší exponent u prvočísla , kde umocněné na tento exponent ještě dělí číslo (faktoriál přirozeného čísla ). Jedná se v podstatě o výpočet p-adické valuace čísla [1].

Pomocí Legendreova vzorce lze dokázat například nekonečnost počtu prvočísel.

Základní vzorec[editovat | editovat zdroj]

Buď , prvočíslo, které dělí . Potom

, kde , tj. .

Kde je exponent u prvočísla , sčítance sumy jsou uzavřeny v dolní celé části.

Odvození vzorce[editovat | editovat zdroj]

Odvození vzorce si ukážeme na následujícím příkladu:[2]

Najděte .

Tzn. najděte takové , že dělí , nedělí .

Máme zde tedy dvojek z násobků čísla 2. Musíme ale zahrnout i další dvojky, z násobků čísel 4, 8...

Dále zde je tedy dvojky z násobků čísla 4.

Podobně jsou zde dvojky z násobků čísla 8 a dvojka z násobků čísla 16.

V součtu je zde tedy tento počet dvojek:

Závěr: dělí , ale už nedělí .


Odtud již plyne výše zmíněný Legendreův vzorec.

Co se týče počtu sčítanců:

Protože nerovnosti vyhovuje pouze jediné .

Řešený příklad č. 1[editovat | editovat zdroj]

Kolika nulami končí dekadický zápis čísla  ?

Řešení: Zadání lze vyslovit také takto: Kolik je v čísle obsaženo desítek, tedy pětek a dvojek současně? Dvojek bude samozřejmě více než pětek, proto nám stačí zjistit počet pětek, tedy .

, kde

Závěr: Číslo má 5786 cifer, z nichž 502 posledních jsou nuly.

Odhad pro Legendreův vzorec[editovat | editovat zdroj]

Odhad používáme pro zjednodušení výpočtů, avšak za cenu přesnosti. Pro velká čísla totiž může být výše zmíněný vzorec příliš komplikovaný pro výpočet.

Pro odhad platí vzorec:

přičemž rovnost nastane právě tehdy, když .

Příklad[editovat | editovat zdroj]

Odhad pro z výše zmíněného řešeného příkladu:

Což je velmi dobrý odhad čísla 502.

Důkaz[editovat | editovat zdroj]

Pravá strana nerovnice je zároveň součtem geometrické řady s kvocientem .

Z toho získáme:

pro

Pro jsou všude výše místo nerovností rovnosti. Naopak například pro je poslední nerovnost ostrá.

Lepší Legendreův vzorec[editovat | editovat zdroj]

Buď , prvočíslo, které dělí . Buď

, kde , tj. .

Potom

kde je ciferný součet čísla zapsaného v soustavě o základu .

Příklad[editovat | editovat zdroj]

Odtud

Důkaz[editovat | editovat zdroj]

Přirozené číslo lze v libovolné soustavě o základu zapsat jako:

kde , tj. .

Platí tedy

Sčítance této sumy vypadají následovně:

...

Takže platí:

Nyní můžeme vidět, že první člen v hranaté závorce je roven číslu a druhý člen je roven číslu , jak jsou tato čísla rozepsána výše. Proto platí

Řešený příklad č. 2[editovat | editovat zdroj]

Najděte všechna přirozená čísla , pro která dělí .

Řešení: Tato situace nastane tehdy, když .

Přitom víme, že .

Jde tedy o to, kdy , tj. .

Možnost implikuje , ale potom .

Možnost nastává právě tehdy, když pro libovolné .

Pravidla pro počítání se vzorcem[editovat | editovat zdroj]

Dá se snadno ověřit, že platí následující vztahy:

(protože pro prvočísla v rozkladech čísel a, b platí )

(podobný důkaz)

Řešený příklad č. 3[editovat | editovat zdroj]

Dokažte, že pro libovolná čísla , a prvočíslo platí:

Řešení:

Důkaz nekonečného počtu prvočísel[editovat | editovat zdroj]

Pro důkaz předpokládejme, že je počet prvočísel konečný. Potom pro každé přirozené číslo n musí platit podle De Polignacova vzorce pro součin přes všechna prvočísla p:[3]

Podle definice Legendreova vzorce také platí:

Odtud vyplývá, že:

Z toho by ovšem vyplynul nepravdivý výrok, že:

Reference[editovat | editovat zdroj]

  1. OPRŠAL, Jakub. Celá čísla p-naruby. Matematický korespondenční seminář [online]. [cit. 2016-08-09]. Dostupné online. 
  2. Legendre's Theorem - The Prime Factorization of Factorials. www.cut-the-knot.org [online]. [cit. 2016-08-09]. Dostupné online. 
  3. WHANG, J. P. Another Proof of the Infinitude of the Prime Numbers. The American Mathematical Monthly. Roč. 2010, čís. 117, s. 181.