Matematické Fórum

Hertas · 03. 08. 2016 21:56

Ahoj mám k dispozici následující dvě věty:

1. Prvočíslo $p \in \mathbb{P}$ se nachází v rozkladu n! právě $\sum_{k \ge1 }^{}[\frac{n}{p^k}]$ krát. ( $[]$ značí celou dolní část)

2. Prvočíslo $p \in \mathbb{P}$ se nachází v rozkladu kombinačního čísla $2n \choose n$ právě $\sum_{k \ge1 }^{}([\frac{2n}{p^k}]-2[\frac{n}{p^k}])$ krát, tj. nanejvýš r-krát, kde $r=max\{k|p^k\le 2n\}$

a z nich mám odvodit následující:
1. pokud pro $p \in \mathbb{P}$ platí $\frac{2}{3}n < p \le n$ , pak se p v rozkladu $2n \choose n$ nevyskytuje

2. pokud pro $p \in \mathbb{P}$ platí $\sqrt{2n}<p$ , pak p se v rozkladu $2n \choose n$ nachází nanejvýš jednou

budu rád za každou radu

check_drummer · 04. 08. 2016 18:21

Ahoj, co třeba druhý bod 1. Zkus si rozepsat čitatele a jmenovatele toho kombinačního čísla.

Hertas · 08. 08. 2016 20:45

číslo $\frac{(2n)!}{(n!)^2}$ odhadnu číslem $(2n)!$ a potom podle první věty a předpokladu, že $\sqrt{2n}<p$ stačí vzít nejmenší takové číslo (prvočíslo je speciální případ přirozeného čsla, takže to musí fungovat), tj. $p=[\sqrt{2n}] + 1$ a po dosazení dostaneme:
$\sum_{k \ge1 }^{}[\frac{2n}{([\sqrt{2n}]+1)^k}]$ , takže se v rozkladu nachází opravdu nanejvýš jednou

a nevěděl bys mě nakopnout s tím prvním bodem?

check_drummer · 08. 08. 2016 22:39

↑ Hertas:
Ahoj, nerozumím tomu prvnímu odhadu - čeho tím odhadem docílíš?

Hertas · 09. 08. 2016 10:28

Potom muzu snadno pouzit tuto vetu:

Prvočíslo $p \in \mathbb{P}$ se nachází v rozkladu n! právě $\sum_{k \ge1 }^{}[\frac{n}{p^k}]$ krát.

check_drummer · 09. 08. 2016 16:26

↑ Hertas:
Jenže to ti nic neřekne o tom čísle $2n \choose n$ .

Hertas · 09. 08. 2016 19:41

Dobře, v tom případě vůbec netuším. Po rozepsání toho kombinačního čísla dostanu $\frac{(n+1)(n+2)...(2n-1)2n}{n!}$ a nic v tom nevidím.

byk7 · 09. 08. 2016 21:16

Pokoušíš se dokázat Bertrandův postulát? :)

Hertas · 09. 08. 2016 21:39

ani ne :)

už to tam vidím, největší prvočíslo, jež se v rozkladu celého čísla $\frac{(n+1)(n+2)...(2n-1)2n}{n!}$ nachází, je $2n$ (což pro n > 1 není prvočíslo), tím pádem prvočíslo $p>\sqrt{2n}$ se v jeho rozkladu může nacházet nanejvýš jednou

check_drummer · 11. 08. 2016 00:48

↑ Hertas:
Já zkoumám ale bod 1, i když asi to bude podobné. Musíš si říct kolikrát je to p v čitateli a kolikrát ve jmenovateli...

Brano · 11. 08. 2016 11:44 — Editoval Brano (30. 08. 2016 10:26)

bod 1)

Pre $n=1$ tvrdenie plati trivialne, lebo nieje ziadne prvocislo v intervale $(2n/3,n]$ .
Pre $n=2$ tvrdenie neplati, lebo $2|\begin{pmatrix}4\\2\end{pmatrix}$ .
Pre $n=3,4$ mame v danom intervale jedine prvocislo $p=3$ a lahko overime, ze prislusne kombinacne cisla nedeli.
Pre $n\ge 5$ plati $\frac{2n}{9}>1$ a teda pre $k\ge 2$ plati $p^k\ge p^2>\frac{4}{9}n^2>2n>n$ a teda
$\left[\frac{2n}{p^k}\right]=\left[\frac{n}{p^k}\right]=0$ . A kedze $\frac{2n}{3}<p\le n$ tak $1\le\frac{n}{p}<\frac{3}{2}$ a $2\le\frac{2n}{p}<3$ , cize $\left[\frac{2n}{p}\right]=2\left[\frac{n}{p}\right]=2$ . Z druhej vety dostaneme, ze $p$ sa v $\begin{pmatrix}2n\\n\end{pmatrix}$ nachadza $2-2+0-0+0-0+... = 0$ krat, teda sa tam nenachadza.

bod 2)
pre $k\ge 2$ plati $p^k\ge p^2>2n>n$ a teda $\left[\frac{2n}{p^k}\right]=\left[\frac{n}{p^k}\right]=0$ . Dalej mozme napisat $n=kp+r$ kde $r\in[0,p)$ a teda $2n=2kp+2r$ a teda plati $\left[\frac{n}{p}\right]=k$ a $\left[\frac{2n}{p}\right]=2k+\left[\frac{2r}{p}\right]$ . Dostaneme teda, ze $p$ sa v $\begin{pmatrix}2n\\n\end{pmatrix}$ nachadza $2k+\left[\frac{2r}{p}\right]-2k = \left[\frac{2r}{p}\right]$ krat, co je bud $0$ alebo $1$ .

vanok · 11. 08. 2016 23:18 — Editoval vanok (12. 08. 2016 10:38)

poznamka.
Kolega ↑ byk7:, polozil velmi dobru otazku.
Pripominam, ze v knihe Proofs from the books, je dokaz Beltranoveho postulatu ktory vyuziva aj otazky z ↑ Hertas: ( ktore su tam aj dokazane).
Tiez moze byt poucne precitat
http://www.cut-the-knot.org/arithmetic/ … late.shtml

check_drummer · 12. 08. 2016 22:53

Ad 1) Takové p se v tom kombinačním čísel vyskytuje v čitateli i jmenovateli právě 2x a tedy se vykrátí...

vanok · 13. 08. 2016 00:17

Ahoj ↑ check_drummer:
Maly doplnok......
Podrobnejsie, pretoze $\frac{2}{3}n < p \le n$
da $\frac{2}{3}n < p \le n <\frac 43n<2p\le2n=\frac 63 n <3p$ .
Co znamena, ze $2n \choose n$ nie je depitelne prvocislom p...... Atd.....

Ale v odkaze co som napisal vcera, je to uz dokazane ( I ked bez podrobnosti)... Dobru noc.

Hertas · 13. 08. 2016 01:45

Děkuji vám všem :)

Matematické Fórum

#1 03. 08. 2016 21:56

Vlastnosti prvočísel

#2 04. 08. 2016 18:21

Re: Vlastnosti prvočísel

#3 08. 08. 2016 20:45

Re: Vlastnosti prvočísel

#4 08. 08. 2016 22:39

Re: Vlastnosti prvočísel

#5 09. 08. 2016 10:28

Re: Vlastnosti prvočísel

#6 09. 08. 2016 16:26

Re: Vlastnosti prvočísel

#7 09. 08. 2016 19:41

Re: Vlastnosti prvočísel

#8 09. 08. 2016 21:16

Re: Vlastnosti prvočísel

#9 09. 08. 2016 21:39

Re: Vlastnosti prvočísel

#10 11. 08. 2016 00:48

Re: Vlastnosti prvočísel

#11 11. 08. 2016 11:44 — Editoval Brano (30. 08. 2016 10:26)

Re: Vlastnosti prvočísel

#12 11. 08. 2016 23:18 — Editoval vanok (12. 08. 2016 10:38)

Re: Vlastnosti prvočísel

#13 12. 08. 2016 22:53

Re: Vlastnosti prvočísel

#14 13. 08. 2016 00:17

Re: Vlastnosti prvočísel

#15 13. 08. 2016 01:45

Re: Vlastnosti prvočísel

Zápatí