Tschebyscheffscher Schrankens. < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Tschebyscheffscher Schrankensatz:
Es gibt ein $a$ und ein $A$ mit
[mm] \boxed{
a\cdot \frac{x}{log(x)}\le \pi(x)\le A\cdot \frac{x}{log(x)}\hspace{1cm}\texttt{f"ur x gro\ss{} genug}
}
[/mm]
Tschebyscheff hat [mm] gefunden:\\
[/mm]
[mm] a&=0,89\\
[/mm]
[mm] A&=1,11\\\\
[/mm]
[mm] a&=\frac{7}{8}=0,875\\
[/mm]
[mm] A&=\frac{9}{8}=1,125
[/mm]
Hilfssatz zu dem Beweis: Tschebyscheffscher Schrankensatz
Sei $p$ prim, dann teilt $p$ die Zahl $m!$ genau [mm] $m_p$ [/mm] mal mit
[mm] m_p=\left[\frac{m}{p}\right]+\left[\frac{m}{p^2}\right]+\left[\frac{m}{p^3}\right]+...
[/mm]
Die Reihe konvergiert, da sie endlich abbrechend ist.
Sobald [mm] $p^n>m [/mm] $ ist, wird der ganze Teil immer 0.
Beweis des Hilfssatzes:
Unter den Zahlen $1,2,...,m$ gibt es genau [mm] $\left[\frac{m}{p}\right]$ [/mm] Vielfache von:
[mm] p:p,2p,3p,...,\left[\frac{m}{p}\right]p
[/mm]
und [mm] $\left[\frac{m}{p}\right] [/mm] $ Vielfache von
[mm] p^2:p^2,2p^2,3p^2,...,\left[\frac{m}{p^2}\right] p^2 [/mm] |
Hallo zusammen!
Habe gleich mehrere Fragen:
1. Hilfssatz: Habe hier wohl einen Denkfehler, denn mit einem Zahlenbeispiel wie z.B.
mit $p=3$ und $m!=5!=120$ gilt:
[mm] 5_3&=\left[\frac{m}{p}\right]+\left[\frac{m}{p^2}\right]+\left[\frac{m}{p^3}\right]+\left[\frac{m}{p^4}\right]+...\\\\
[/mm]
[mm] &=\left[\frac{5}{3}\right]+\left[\frac{5}{3^2}\right]+\left[\frac{5}{3^3}\right]+\left[\frac{5}{3^4}\right]+...\\\\
[/mm]
&=1+0+0+0+...
meines Erachtens m"usste hier doch [mm] $m_p=40$ [/mm] rauskommen, oder ?
Wo ist da mein Denkfehler?
-----------------------------------------------------------------------------------------
2. Der Beweis zum Schrankensatz:
Für die obere Schranke habe ich das soweit nachvollzogen, aber bei der unteren Schranke hänge ich:
Obere Schranke $A$
Im Beweis zu Satz 1 wurde gezeigt:
[mm] \pi(x)= \frac{\theta(x)}{log(x)}+O\left(\cdot \frac{x}{log(x)^2}\right)
[/mm]
d.h.
[mm] \pi(x)\cdot [/mm] log(x)&= [mm] \theta(x)+O\left(\cdot \frac{x}{log(x)}\right)\\\\
[/mm]
[mm] \frac{\pi(x)\cdot log(x)}{x}&=\frac{ \theta(x)}{x}+O\underbrace{\left(\cdot \frac{1}{log(x)}\right)}_{=0 \text { f"ur } x\rightarrow \infty}\\
[/mm]
Aus einem gegebenen Corrollar [mm] $\theta(x)\le x\cdot [/mm] log(4)$ folgt, dass [mm] $\frac{\theta(x)}{x}\le [/mm] log(4)$, somit
[mm] \frac{\pi(x)\cdot log(x)}{x}&=\underbrace{\frac{ \theta(x)}{x}}_{\le log(4)}+O\underbrace{\left(\cdot \frac{1}{log(x)}\right)}_{=0 \text { f"ur } x\rightarrow \infty}\\
[/mm]
[mm] \frac{\pi(x)\cdot log(x)}{x}&=log(4)+\epsilon=A \hspace{2cm} \text{f"ur x gro\ss{} genug}
[/mm]
z.B. [mm] $\frac{\pi(x)\cdot log(x)}{x}=log(4)+\epsilon=\underbrace{2\cdot log(2)}_{1,39}+\underbrace{\epsilon}_{0,01}=1,4=A$
[/mm]
Untere Schranke $a$:
Betrachte
[mm] N:={2n\choose n}&=\frac{ 2n!}{n!\cdot(2n-n)!}=\frac{ 2n!}{(n!)^2}\\
[/mm]
Es ist
[mm] (2n+1)\cdot [/mm] N> [mm] 2^{2n}=(1+1)^{2n}\\
[/mm]
N> [mm] \frac{2^{2n}}{(2n+1)}\\
[/mm]
[mm] log(N)>2n\cdot [/mm] log(2)-log(2n+1)
Nun ist $ [mm] N=\frac{ (2n)!}{(n!)^2}$, [/mm] d.h. eine Primzahl $p$ teilt $N$ genau [mm] $v_p$ [/mm] -mal mit
[mm] v_p=\sum_{k\ge 1} \left[\frac{2n}{p^k}\right]-2\cdot \sum_{k\ge 1} \left[\frac{n}{p^k}\right]
[/mm]
Diese Rechnung verstehe ich nicht.
Ich habe jetzt den Logarithmus auf N angewendet: $log(N)=log((2n)!)-2log(n!)$, aber jetzt weiß ich leider nicht weiter.
Kann mir das jemand vielleicht vorrechnen?
Vielen vielen Dank schon im Voraus!
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 12:43 Mi 05.01.2011 | | Autor: | leduart |
Hallo
zu a)
du schreibst selbst ;Sobald $ [mm] p^n>m [/mm] $ ist, wird der ganze Teil immer 0.
bei dir [mm] 3^2>5 [/mm] also [mm] m_p=1 [/mm] wieso sollte es 40sein ? [mm] m_p [/mm] ist nicht m!/p
Gruss leduart
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 13:16 Mi 05.01.2011 | | Autor: | felixf |
Moin!
> Tschebyscheffscher Schrankensatz:
> Es gibt ein [mm]a[/mm] und ein [mm]A[/mm] mit
> [mm]\boxed{
a\cdot \frac{x}{log(x)}\le \pi(x)\le A\cdot \frac{x}{log(x)}\hspace{1cm}\texttt{f"ur x gro\ss{} genug}
}[/mm]
>
> Tschebyscheff hat [mm]gefunden:\\[/mm]
>
> [mm]a&=0,89\\[/mm]
> [mm]A&=1,11\\\\[/mm]
> [mm]a&=\frac{7}{8}=0,875\\[/mm]
> [mm]A&=\frac{9}{8}=1,125[/mm]
>
>
> Hilfssatz zu dem Beweis: Tschebyscheffscher Schrankensatz
> Sei [mm]p[/mm] prim, dann teilt [mm]p[/mm] die Zahl [mm]m![/mm] genau [mm]m_p[/mm] mal mit
>
> [mm]m_p=\left[\frac{m}{p}\right]+\left[\frac{m}{p^2}\right]+\left[\frac{m}{p^3}\right]+...[/mm]
>
> Die Reihe konvergiert, da sie endlich abbrechend ist.
> Sobald [mm]p^n>m[/mm] ist, wird der ganze Teil immer 0.
>
>
> Beweis des Hilfssatzes:
> Unter den Zahlen [mm]1,2,...,m[/mm] gibt es genau
> [mm]\left[\frac{m}{p}\right][/mm] Vielfache von:
>
> [mm]p:p,2p,3p,...,\left[\frac{m}{p}\right]p[/mm]
>
> und [mm]\left[\frac{m}{p}\right][/mm] Vielfache von
>
> [mm]p^2:p^2,2p^2,3p^2,...,\left[\frac{m}{p^2}\right] p^2[/mm]
> Hallo
> zusammen!
> Habe gleich mehrere Fragen:
>
> 1. Hilfssatz: Habe hier wohl einen Denkfehler, denn mit
> einem Zahlenbeispiel wie z.B.
> mit [mm]p=3[/mm] und [mm]m!=5!=120[/mm] gilt:
>
> [mm]5_3&=\left[\frac{m}{p}\right]+\left[\frac{m}{p^2}\right]+\left[\frac{m}{p^3}\right]+\left[\frac{m}{p^4}\right]+...\\\\[/mm]
>
> [mm]&=\left[\frac{5}{3}\right]+\left[\frac{5}{3^2}\right]+\left[\frac{5}{3^3}\right]+\left[\frac{5}{3^4}\right]+...\\\\[/mm]
> &=1+0+0+0+...
>
> meines Erachtens m"usste hier doch [mm]m_p=40[/mm] rauskommen, oder
> ?
Wie leduart schon sagte: du verstehst das falsche unter [mm] $m_p$. [/mm] Es gilt $m! = [mm] p^{m_p} \cdot [/mm] r$, wobei $r$ nicht durch $p$ teilbar ist.
Und $5!$ ist genau einmal durch 3 teilbar, da es nicht durch [mm] $3^2$ [/mm] teilbar ist (dann muesste $40 = [mm] \frac{5!}{3}$ [/mm] durch 3 teilbar sein).
> -----------------------------------------------------------------------------------------
> 2. Der Beweis zum Schrankensatz:
>
> Für die obere Schranke habe ich das soweit nachvollzogen,
> aber bei der unteren Schranke hänge ich:
>
>
> Obere Schranke [mm]A[/mm]
> Im Beweis zu Satz 1 wurde gezeigt:
>
> [mm]\pi(x)= \frac{\theta(x)}{log(x)}+O\left(\cdot \frac{x}{log(x)^2}\right)[/mm]
>
> d.h.
>
> [mm]\pi(x)\cdot[/mm] log(x)&= [mm]\theta(x)+O\left(\cdot \frac{x}{log(x)}\right)\\\\[/mm]
>
> [mm]\frac{\pi(x)\cdot log(x)}{x}&=\frac{ \theta(x)}{x}+O\underbrace{\left(\cdot \frac{1}{log(x)}\right)}_{=0 \text { f"ur } x\rightarrow \infty}\\[/mm]
>
> Aus einem gegebenen Corrollar [mm]\theta(x)\le x\cdot log(4)[/mm]
> folgt, dass [mm]\frac{\theta(x)}{x}\le log(4)[/mm], somit
>
> [mm]\frac{\pi(x)\cdot log(x)}{x}&=\underbrace{\frac{ \theta(x)}{x}}_{\le log(4)}+O\underbrace{\left(\cdot \frac{1}{log(x)}\right)}_{=0 \text { f"ur } x\rightarrow \infty}\\[/mm]
>
> [mm]\frac{\pi(x)\cdot log(x)}{x}&=log(4)+\epsilon=A \hspace{2cm} \text{f"ur x gro\ss{} genug}[/mm]
>
> z.B. [mm]\frac{\pi(x)\cdot log(x)}{x}=log(4)+\epsilon=\underbrace{2\cdot log(2)}_{1,39}+\underbrace{\epsilon}_{0,01}=1,4=A[/mm]
>
> Untere Schranke [mm]a[/mm]:
> Betrachte
> [mm]N:={2n\choose n}&=\frac{ 2n!}{n!\cdot(2n-n)!}=\frac{ 2n!}{(n!)^2}\\[/mm]
>
> Es ist
> [mm](2n+1)\cdot[/mm] N> [mm]2^{2n}=(1+1)^{2n}\\[/mm]
> N> [mm]\frac{2^{2n}}{(2n+1)}\\[/mm]
> [mm]log(N)>2n\cdot[/mm] log(2)-log(2n+1)
>
> Nun ist [mm]N=\frac{ (2n)!}{(n!)^2}[/mm], d.h. eine Primzahl [mm]p[/mm] teilt
> [mm]N[/mm] genau [mm]v_p[/mm] -mal mit
>
> [mm]v_p=\sum_{k\ge 1} \left[\frac{2n}{p^k}\right]-2\cdot \sum_{k\ge 1} \left[\frac{n}{p^k}\right][/mm]Eingabefehler: "\left" und "\right" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
>
> Diese Rechnung verstehe ich nicht.
Du meinst $v_p = \sum_{k\ge 1} \left[\frac{2n}{p^k}\right]-2\cdot \sum_{k\ge 1} \left[\frac{n}{p^k}$?
Wenn du $\frac{(2n)!}{(n!)^2}$ schreibst als $p^{v_p} \cdot r$ mit $r \in \IZ$ nicht durch $p$ teilbar, dann ist $v_p = (2n)_p - 2 \cdot n_p$: es ist doch $(2n!) = p^{(2n)_p} r_1$ und $n! = p^{n_p} r_2$ mit $r_1, r_2 \in \IZ$ nicht durch $p$ teilbar, und somit $\frac{(2n)!}{(n!)^2} = p^{(2n)_p - 2 n_p} \frac{r_1}{r_2^2}$, und weder Zaehler noch Nenner von $\frac{r_1}{r_2^2}$ sind durch $p$ teilbar (es ist sogar eine ganze Zahl, aber das ist hier nicht so wichtig).
> Ich habe jetzt den Logarithmus auf N angewendet:
> [mm]log(N)=log((2n)!)-2log(n!)[/mm], aber jetzt weiß ich leider
> nicht weiter.
Das [mm] $v_p$ [/mm] ist die ![[]](/images/popup.gif) $p$-adische Bewertung von [mm] $\frac{(2n)!}{(n!)^2}$. [/mm] Bewertungen verhalten sich aehnlich wie der Logarithmus: sie sind Homomorphismen von der multiplikativen Gruppe von [mm] $\IQ$ [/mm] in die additive Gruppe von [mm] $\IZ$ [/mm] (bei Logarithmen hast du die additive Gruppe von [mm] $\IR$).
[/mm]
LG Felix
|
|
|
| |
|
| Aufgabe | Da [mm] $N=\frac{ (2n)!}{(n!)^2}$ [/mm] kann man mit dem Hilfssatz [mm] ($m!=p^{m_p}\cdot [/mm] r$, wobei r nicht durch $p$ teilbar ist), nun [mm] $\frac{(2n)!}{(n!)^2} [/mm] $ als $ [mm] p^{v_p} \cdot [/mm] r $ mit $ r [mm] \in [/mm] Z$ nicht durch p teilbar, schreiben. F"ur (2n)! gilt
[mm] m!=p^{m_p}\cdot [/mm] r
[mm] (2n)!=p^{(2n)_p}\cdot r_1
[/mm]
f"ur $n!$ gilt:
[mm] n!=p^{n_p}\cdot r_2 [/mm]
mit [mm] $r_1,r_2 \in [/mm] Z$ nicht durch $p$ teilbar. Es gilt dann
[mm] \frac{(2n)!}{(n!)^2}&=\frac{p^{(2n)_p}\cdot r_1}{(p^{n_p}\cdot r_2 )^2}\\
[/mm]
[mm] &=\frac{p^{(2n)_p}\cdot r_1}{(p^{2n_p}\cdot r^2_2 )}\\
[/mm]
[mm] &=p^{(2n)_p-2n_p}\cdot \frac{r_1}{r_2^2}
[/mm]
und weder Z"ahler noch Nenner von $ [mm] \frac{r_1}{r_2^2}$ [/mm] ist durch $p$ teilbar.
Das [mm] $(2n)_p-2n_p$ [/mm] ist mein [mm] $m_p$ [/mm] und l"asst mit Summe [mm] folgenderma\ss{}en [/mm] darstellen
[mm] m_p&=\sum_{k\ge 1}\left[\frac{2n}{p^k}\right]-2\cdot \sum_{k\ge 1}\left[\frac{n}{p^k}\right]\\
[/mm]
[mm] &=\sum_{k\ge 1}\left(\underbrace{\left[\frac{2n}{p^k}\right]-2\cdot\left[\frac{n}{p^k}\right]}_{\text{von der Form: } [2x]-2[x]}\right)\\
[/mm]
Es gilt:
[mm] [x]\le x\le [/mm] [x]+1
Daraus ergibt sich
[mm] [x]\le x\le [/mm] [x]+1 [mm] |\cdot [/mm] 2
= [mm] 2[x]\le 2x\le [/mm] 2[x]+2
= [mm] 2[x]\le [2x]\le [/mm] 2[x]+1
[mm] =0\le[2x]-2[x]\le [/mm] 1
Da [mm] $\left[\frac{2n}{p^k}\right]$ [/mm] und [mm] $2\cdot\left[\frac{n}{p^k}\right]$ [/mm] f"ur [mm] $p^k>2n$ [/mm] auf jeden Fall 0 ist, gilt
[mm] p^k&>2n\\
[/mm]
[mm] log(p^k)&> log(2n)\\
[/mm]
[mm] k&>\frac{log(2n)}{log(p)}\\
[/mm]
Da [mm] $k\in [/mm] Z$ wird der ganze Teil [mm] ben"otigt:\\ [/mm]
[mm] k&>\left[\frac{log(2n)}{log(p)}\right]=M_p\\
[/mm]
Also ist [mm] $M_p$ [/mm] die kleinstm"ogliche Primzahl-Potenz, f"ur die der ganze Teil 0 wird. Es ergibt sich daher
[mm] m_p\le \sum_{k=1}^{M_p} 1&=\left[\frac{log(2n)}{log(p)}\right]\\
[/mm]
[mm] \textcolor{red}{Somit}
[/mm]
[mm] N=\prod_{p\le 2n} p^{m_p}\le \prod_{p\le 2n} p^{M_p} [/mm] |
Eure Erklärungen waren super und ich glaube, ich habe auch alles kapiert. Jetzt hänge ich aber wieder bei einem Schritt:
Wie komme ich von
[mm] m_p\le \sum_{k=1}^{M_p} 1&=\left[\frac{log(2n)}{log(p)}\right]\\
[/mm]
auf
[mm] N=\prod_{p\le 2n} p^{m_p}\le \prod_{p\le 2n} p^{M_p}?
[/mm]
Vielen Dank
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 16:52 Mi 05.01.2011 | | Autor: | felixf |
Moin!
> Eure
> Erklärungen waren super und ich glaube, ich habe auch
> alles kapiert. Jetzt hänge ich aber wieder bei einem
> Schritt:
> Wie komme ich von
>
> [mm]m_p\le \sum_{k=1}^{M_p} 1&=\left[\frac{log(2n)}{log(p)}\right]\\[/mm]
>
> auf
>
> [mm]N=\prod_{p\le 2n} p^{m_p}\le \prod_{p\le 2n} p^{M_p}?[/mm]
Das hat mit der Primfaktorzerlegung zu tun 
Jeder Primfaktor von $N = [mm] \frac{(2 n)!}{(n!)^2}$ [/mm] ist ja [mm] $\le [/mm] 2 n$, womit das Produkt u.a. alle Primfaktoren von $N$ durchlaeuft. Seien diese Primzahlen [mm] $p_1, \dots, p_t$. [/mm] Dann ist $N = [mm] \prod_{i=1}^t p_i^{e_i}$ [/mm] mit passenden [mm] $e_i \in \IN$ [/mm] -- das ist einfach die Primfaktorzerlegung.
Fuer ein festes $i$ ist $N = [mm] p_i^{e_i} \cdot \prod_{j \neq i} p_j^{e_j}$, [/mm] wobei [mm] $\prod_{j \neq i} p_j^{e_j}$ [/mm] nicht durch [mm] $p_i$ [/mm] teilbar ist. Deswegen ist [mm] $e_i$ [/mm] gerade gleich [mm] $m_{p_i}$, [/mm] wenn du die Definitionen vergleichst!
Also ist $N = [mm] \prod_{i=1}^t p_i^{m_{p_i}} [/mm] = [mm] \prod_{p \le 2 n} p^{m_p}$.
[/mm]
Und da [mm] $m_p \le M_p$ [/mm] gilt folgt [mm] $p^{m_p} \le p^{M_p}$ [/mm] und somit auch die Ungleichung fuer das Produkt ueber alle $p [mm] \le [/mm] 2 n$.
LG Felix
|
|
|
| |
|
| Aufgabe | Sei $n=3$, dann gilt:
[mm] N&={2n\choose n}={2\cdot 3\choose 3}=\frac{(2\cdot 3)!}{(3!)^2}\\
[/mm]
Mit [mm] $m!=p^{m_p}\cdot [/mm] r$ gilt:
[mm] (2\cdot 3)!&=p^{(2\cdot 3)_p}\cdot r_1\\
[/mm]
[mm] 3!&=p^{3_p}\cdot r_2\\\\
[/mm]
[mm] \frac{(2\cdot 3)!}{(3!)^2}&=\frac{p^{(2\cdot 3)_p}\cdot r_1}{(p^{3_p}\cdot r_2)^2}\\
[/mm]
[mm] &=\frac{p^{(2\cdot 3)_p}\cdot r_1}{(p^{3_p\cdot 2}\cdot r^2_2)}\\
[/mm]
[mm] &=p^{(2\cdot 3)_p-3_p\cdot 2}\cdot \frac{r_1}{r^2_2}\\
[/mm]
Daraus ergibt sich [mm] $m_p=(2\cdot 3)_p-3_p\cdot [/mm] 2$ und als Summe dargestellt:
[mm] m_p&=\sum_{k\le 1}\left[\frac{2\cdot 3}{p^k}\right]-2\cdot\sum_{k\le1}\left[\frac{3}{p^k}\right]\\
[/mm]
[mm] &=\sum_{k\le 1}\left(\left[\frac{2\cdot 3}{p^k}\right]-2\left[\frac{3}{p^k}\right]\right)\\
[/mm]
Ab [mm] $p^k>2\cdot [/mm] 3$ nehmen beide Terme nur noch 0 an, das [mm] heit\ss{}t, [/mm] sobald [mm] $p^k$ gr"o\ss{}er [/mm] als $6$ wird, wird der ganze Teil beider Terme 0 (beim hinteren Term wid der ganze Teil schon ab [mm] $p^k>3$ [/mm] gleich 0). L"ost man [mm] $p^k>2\cdot [/mm] 3$ nach k auf, so ergibt sich
[mm] k>\frac{log(2\cdot 3)}{log(p)}.
[/mm]
F"ur die Primzahl $p=2$ ergibt sich zum Beispiel:
k>2,585
Da $k$ nur ganze Zahlen annehmen kann, gilt
[mm] k>\left[\frac{log(2\cdot 3)}{log(p)}\right]=2=M_p
[/mm]
Also ist [mm] $M_p$ [/mm] die kleinstm"ogliche Primzahl-Potenz, f"ur die der ganze Teil 0 wird. Insgesamt gilt:
[mm] \sum_{k=1}^{M_p}1=\sum_{k=1}^{2}1=2=\left[\frac{log(2\cdot 3)}{log(p)}\right]
[/mm]
und
[mm] m_p&\le \sum_{k=1}^{M_p}1\\
[/mm]
[mm] \sum_{k\ge 1}\left(\left[\frac{2\cdot 3}{p^k}\right]-2\cdot \left[\frac{3}{p^k}\right]\right)&\le \sum_{k=1}^{M_p}1\\
[/mm]
[mm] \left[\frac{2\cdot 3}{p}\right]+\left[\frac{2\cdot 3}{p^2}\right]+...-2\cdot \left(\left[\frac{3}{p^1}\right]+2\cdot \left[\frac{3}{p^2}\right]+...\right)&\le \sum_{k=1}^{M_p}1\\
[/mm]
f"ur $p=2$ gilt:
[mm] \left[\frac{2\cdot 3}{2}\right]+\left[\frac{2\cdot 3}{2^2}\right]+...-2\cdot \left(\left[\frac{3}{2^1}\right]+2\cdot \left[\frac{3}{2^2}\right]+...\right)&\le \sum_{k=1}^{M_p}1\\
[/mm]
[mm] 3+1-2\cdot(1+0)&\le \sum_{k=1}^{M_p}1\\
[/mm]
[mm] 2&\le \sum_{k=1}^{M_p}1=2
[/mm]
[mm] \underline{Primfaktorzerlegung:}\\
[/mm]
Jeder Primfaktor von $ N = [mm] \frac{(2 n)!}{(n!)^2}= \frac{(2 \cdot 3)!}{(3!)^2}=20 [/mm] $ ist ja $ [mm] \le [/mm] 2 n [mm] =2\cdot [/mm] 3=6$,
da ein [mm] gr"o\ss{}erer [/mm] Primfaktor $N$ nicht darstellen kann. Das [mm] hei\ss{}t, [/mm] es k"onnen nur Primfaktoren, [mm] $\le [/mm] 6$ sind, die Zahl $20$ darstellen,z.B:
[mm] n&=p_1^{\alpha_1}\cdot p_2^{\alpha_2}\cdot p_3^{\alpha_3}\cdot ...\\
[/mm]
[mm] 20&=2^2\cdot [/mm] 5
Ein Produkt, das alle Primzahlen bis $2n=6$ durchl"auft, durchl"auft somit u.a. alle Primfaktoren von $N$. Seien [mm] $p_1,...,p_t=2,3,5$ [/mm] diese Primzahlen, dann ist
[mm] N=\prod_{i=1}^t p^{\alpha_i} _i=\prod_{i=1}^3 p^{\alpha_i} _i=2^2\cdot 3^0\cdot 5^1
[/mm]
mit passenden [mm] $\alpha_i \in [/mm] N$. Das ist die einfache [mm] Primfaktorzerlegung.\\
[/mm]
Fuer ein festes $i$ ist
N &= [mm] p_i^{\alpha_i} \cdot \prod_{j \neq i} p_j^{\alpha_j} \\
[/mm]
, wobei $ [mm] \prod_{j \neq i} p_j^{\alpha_j} [/mm] $ nicht durch $ [mm] p_i [/mm] $ teilbar ist. |
Hallo !
Ich mache immer ein Zahlenbeispiel, um den Beweis richtig zu verstehen. Du schreibt :
Fuer ein festes $i$ ist
N = [mm] p_i^{\alpha_i} \cdot \prod_{j \neq i} p_j^{\alpha_j} [/mm]
, wobei $ [mm] \prod_{j \neq i} p_j^{\alpha_j} [/mm] $ nicht durch $ [mm] p_i [/mm] $ teilbar ist.
Wie komme ich auf dieses feste $i$ in meinem Beispiel?
DANKE
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 03:17 Sa 08.01.2011 | | Autor: | felixf |
Moin!
> Sei [mm]n=3[/mm], dann gilt:
>
> [mm]N&={2n\choose n}={2\cdot 3\choose 3}=\frac{(2\cdot 3)!}{(3!)^2}\\[/mm]
>
> Mit [mm]m!=p^{m_p}\cdot r[/mm] gilt:
>
> [mm](2\cdot 3)!&=p^{(2\cdot 3)_p}\cdot r_1\\[/mm]
> [mm]3!&=p^{3_p}\cdot r_2\\\\[/mm]
>
> [mm]\frac{(2\cdot 3)!}{(3!)^2}&=\frac{p^{(2\cdot 3)_p}\cdot r_1}{(p^{3_p}\cdot r_2)^2}\\[/mm]
>
> [mm]&=\frac{p^{(2\cdot 3)_p}\cdot r_1}{(p^{3_p\cdot 2}\cdot r^2_2)}\\[/mm]
>
> [mm]&=p^{(2\cdot 3)_p-3_p\cdot 2}\cdot \frac{r_1}{r^2_2}\\[/mm]
>
> Daraus ergibt sich [mm]m_p=(2\cdot 3)_p-3_p\cdot 2[/mm] und als
> Summe dargestellt:
>
> [mm]m_p&=\sum_{k\le 1}\left[\frac{2\cdot 3}{p^k}\right]-2\cdot\sum_{k\le1}\left[\frac{3}{p^k}\right]\\[/mm]
>
> [mm]&=\sum_{k\le 1}\left(\left[\frac{2\cdot 3}{p^k}\right]-2\left[\frac{3}{p^k}\right]\right)\\[/mm]
>
> Ab [mm]p^k>2\cdot 3[/mm] nehmen beide Terme nur noch 0 an, das
> [mm]heit\ss{}t,[/mm] sobald [mm]p^k[/mm] [mm]gr"o\ss{}er[/mm] als [mm]6[/mm] wird, wird der
> ganze Teil beider Terme 0 (beim hinteren Term wid der ganze
> Teil schon ab [mm]p^k>3[/mm] gleich 0). L"ost man [mm]p^k>2\cdot 3[/mm] nach
> k auf, so ergibt sich
>
> [mm]k>\frac{log(2\cdot 3)}{log(p)}.[/mm]
>
> F"ur die Primzahl [mm]p=2[/mm] ergibt sich zum Beispiel:
>
> k>2,585
>
> Da [mm]k[/mm] nur ganze Zahlen annehmen kann, gilt
>
> [mm]k>\left[\frac{log(2\cdot 3)}{log(p)}\right]=2=M_p[/mm]
>
> Also ist [mm]M_p[/mm] die kleinstm"ogliche Primzahl-Potenz, f"ur die
> der ganze Teil 0 wird. Insgesamt gilt:
>
> [mm]\sum_{k=1}^{M_p}1=\sum_{k=1}^{2}1=2=\left[\frac{log(2\cdot 3)}{log(p)}\right][/mm]
>
> und
>
> [mm]m_p&\le \sum_{k=1}^{M_p}1\\[/mm]
> [mm]\sum_{k\ge 1}\left(\left[\frac{2\cdot 3}{p^k}\right]-2\cdot \left[\frac{3}{p^k}\right]\right)&\le \sum_{k=1}^{M_p}1\\[/mm]
>
> [mm]\left[\frac{2\cdot 3}{p}\right]+\left[\frac{2\cdot 3}{p^2}\right]+...-2\cdot \left(\left[\frac{3}{p^1}\right]+2\cdot \left[\frac{3}{p^2}\right]+...\right)&\le \sum_{k=1}^{M_p}1\\[/mm]
>
> f"ur [mm]p=2[/mm] gilt:
> [mm]\left[\frac{2\cdot 3}{2}\right]+\left[\frac{2\cdot 3}{2^2}\right]+...-2\cdot \left(\left[\frac{3}{2^1}\right]+2\cdot \left[\frac{3}{2^2}\right]+...\right)&\le \sum_{k=1}^{M_p}1\\[/mm]
>
> [mm]3+1-2\cdot(1+0)&\le \sum_{k=1}^{M_p}1\\[/mm]
> [mm]2&\le \sum_{k=1}^{M_p}1=2[/mm]
>
> [mm]\underline{Primfaktorzerlegung:}\\[/mm]
> Jeder Primfaktor von [mm]N = \frac{(2 n)!}{(n!)^2}= \frac{(2 \cdot 3)!}{(3!)^2}=20[/mm]
> ist ja [mm]\le 2 n =2\cdot 3=6[/mm],
> da ein [mm]gr"o\ss{}erer[/mm] Primfaktor [mm]N[/mm] nicht darstellen kann.
> Das [mm]hei\ss{}t,[/mm] es k"onnen nur Primfaktoren, [mm]\le 6[/mm] sind, die
> Zahl [mm]20[/mm] darstellen,z.B:
>
> [mm]n&=p_1^{\alpha_1}\cdot p_2^{\alpha_2}\cdot p_3^{\alpha_3}\cdot ...\\[/mm]
>
> [mm]20&=2^2\cdot[/mm] 5
>
> Ein Produkt, das alle Primzahlen bis [mm]2n=6[/mm] durchl"auft,
> durchl"auft somit u.a. alle Primfaktoren von [mm]N[/mm]. Seien
> [mm]p_1,...,p_t=2,3,5[/mm] diese Primzahlen, dann ist
>
> [mm]N=\prod_{i=1}^t p^{\alpha_i} _i=\prod_{i=1}^3 p^{\alpha_i} _i=2^2\cdot 3^0\cdot 5^1[/mm]
>
> mit passenden [mm]\alpha_i \in N[/mm]. Das ist die einfache
> [mm]Primfaktorzerlegung.\\[/mm]
> Fuer ein festes [mm]i[/mm] ist
>
> N &= [mm]p_i^{\alpha_i} \cdot \prod_{j \neq i} p_j^{\alpha_j} \\[/mm]
>
> , wobei [mm]\prod_{j \neq i} p_j^{\alpha_j}[/mm] nicht durch [mm]p_i[/mm]
> teilbar ist.
> Hallo !
>
> Ich mache immer ein Zahlenbeispiel, um den Beweis richtig
> zu verstehen. Du schreibt :
> Fuer ein festes [mm]i[/mm] ist
>
> N = [mm]p_i^{\alpha_i} \cdot \prod_{j \neq i} p_j^{\alpha_j}[/mm]
>
> , wobei [mm]\prod_{j \neq i} p_j^{\alpha_j}[/mm] nicht durch [mm]p_i[/mm]
> teilbar ist.
>
> Wie komme ich auf dieses feste [mm]i[/mm] in meinem Beispiel?
Also $i$ ist fest, aber beliebig. Hier kannst du etwa $i = 1, 2, 3$ einsetzen.
Bei $i = 1$ hast du: $N = [mm] 2^2 \cdot \prod_{i=2}^3 p_i^{\alpha_i} [/mm] = 4 [mm] \cdot [/mm] 5$, und $5$ ist offensichtlich nicht durch [mm] $p_1 [/mm] = 2$ teilbar.
Bei $i = 2$ erhaelst du $N = 1 [mm] \cdot [/mm] 20$, und $20$ ist offensichtlich nicht durch [mm] $p_2 [/mm] = 3$ teilbar.
Und bei $i = 3$ schliesslich erhaelst du $N = 5 [mm] \cdot [/mm] 4$, und $4$ ist offensichtlich nicht durch [mm] $p_3 [/mm] = 5$ teilbar.
LG Felix
|
|
|
|
