Zahlentheorie: Teilbarkeit Binomialkoeffizient

22.04.2013, 15:24

Thorus

Zahlentheorie: Teilbarkeit Binomialkoeffizient

Sei $\begin{eqnarray*} n \in \mathbb{N} \end{eqnarray*}$ und $\begin{eqnarray*} n<p\leq 2n \end{eqnarray*}$ eine Primzahl.
Zeige: $\begin{eqnarray*} p \end{eqnarray*}$ teilt $\begin{eqnarray*} \frac{(2n)!}{n!n!} \end{eqnarray*}$ .

Ich habe bereits relativ langwierig versucht, den Ausdruck passend umzuformen, und habe es dann auch mit Induktion versucht, nach folgendem Muster:

Es gelte $\begin{eqnarray*} \frac{(2n!)}{n!n!} = cp, c \in \mathbb{N} \end{eqnarray*}$ . Dann ist $\begin{eqnarray*} \frac{(2n+2)!}{(n+1)!(n+1)!} = \frac{(2n+2)(2n+1)}{(n+1)^2}cp = \frac{2(2n+1)}{n+1}cp \end{eqnarray*}$ , wo ich nicht weiterkomme, da ja nicht klar ist, ob/dass $\begin{eqnarray*} \frac{2(2n+1)}{n+1}c \in \mathbb{N} \end{eqnarray*}$ .

Ich hab auch bereits versucht, an das $\begin{eqnarray*} c \end{eqnarray*}$ irgendwie konkreter ranzukommen, und ich habe $\begin{eqnarray*} \frac{(2n)!}{n!n!} = \binom{2n}{n} = \binom{2n-1}{n-1} + \binom{2n-1}{n} \end{eqnarray*}$ versucht auszunutzen.

Das war alles relativ erfolglos. Wahrscheinlich ist die Lösung ganz einfach, aber ich seh sie nicht. Mag mir bitte jemand einen Hinweis geben? smile

22.04.2013, 17:05

Thorus

Auf diesen Beitrag antworten »

Hat sich erledigt.

22.04.2013, 17:22

PeterSchmitt

Auf diesen Beitrag antworten »

Hallo,
ich bin bei der Induktion genauso weit gekommen wie Thorus, allerdings bin ich noch nicht dahinter gekommen, wieso

$\begin{eqnarray*} \frac{4n+2}{n+1} \in \mathbb{N} \end{eqnarray*}$

gelten sollte. Kann mir jemand einen Tipp geben?

Danke!

Viele Grüße,
Peter

22.04.2013, 21:09

RavenOnJ

Auf diesen Beitrag antworten »

Auf alle Fälle teilt p prim die Zahl $\begin{eqnarray*} (2n)! \end{eqnarray*}$ , da $\begin{eqnarray*} p\le 2n \end{eqnarray*}$ . Da außerdem $\begin{eqnarray*} p>n \end{eqnarray*}$ , kann p in $\begin{eqnarray*} n! \end{eqnarray*}$ nicht als Faktor enthalten sein. Also muss p auch $\begin{eqnarray*} \binom {2n}{n} = \frac {(2n)!}{n!n!} \end{eqnarray*}$ teilen.

22.04.2013, 22:06

PeterSchmitt

Auf diesen Beitrag antworten »

Die Überlegungen bzgl. der Teilbarkeit von 2n! und n! hatte ich auch bereits. Allerdings verstehe ich deine letzte Schlussfolgerung nicht.

Warum soll p

$\begin{eqnarray*} \frac{(2n)!}{n!n!} \end{eqnarray*}$

teilen, wenn p die Zahl 2n! aber nicht n! teilt?

Danke!

22.04.2013, 22:24

RavenOnJ

Auf diesen Beitrag antworten »

Weil $\begin{eqnarray*} S=\binom{2n}{n} \end{eqnarray*}$ eine natürliche Zahl ist, gibt es eine eindeutige Zerlegung in Primfaktoren. p ist in $\begin{eqnarray*} (2n)! \end{eqnarray*}$ als Primfaktor vorhanden, wie jede Primzahl kleiner oder gleich 2n. Die Primfaktoren in $\begin{eqnarray*} (2n)! \end{eqnarray*}$ können durch Primfaktoren in $\begin{eqnarray*} n!n! \end{eqnarray*}$ neutralisiert werden, sodass sie in S nicht mehr vorkommen. p ist aber größer als n, kann also in $\begin{eqnarray*} n! \end{eqnarray*}$ nicht als Faktor vorhanden sein. Er muss also auch in S als Primfaktor vorkommen.

23.04.2013, 08:38

RavenOnJ

Auf diesen Beitrag antworten »

Man könnte noch hinterherschicken: Jede Primzahl $\begin{eqnarray*} n<p_i \le 2n \end{eqnarray*}$ kommt in der Zerlegung von $\begin{eqnarray*} \binom{2n}{n} \end{eqnarray*}$ mit Multiplizität Eins vor. Sei also $\begin{eqnarray*} P_n \end{eqnarray*}$ die Menge aller Primzahlen mit $\begin{eqnarray*} P_n:=\{p\;|\;n <p\le 2n, p\text{ prim}\} \end{eqnarray*}$ , dann kommen in der Primfaktorzerlegung von $\begin{eqnarray*} \binom{2n}{n}\prod_{p_i\in P_n}\frac 1 {p_i} \end{eqnarray*}$ nur Primfaktoren $\begin{eqnarray*} \le n \end{eqnarray*}$ vor.

23.04.2013, 18:50

PeterSchmitt

Auf diesen Beitrag antworten »

Zu deinem ersten Beitrag:
Hier verstehe ich wieder die letzte Schlussfolgerung nicht. Alle $\begin{eqnarray*} p \end{eqnarray*}$ mit $\begin{eqnarray*} p \leq n \end{eqnarray*}$ sind nun eliminiert. Aber warum muss dann $\begin{eqnarray*} p \end{eqnarray*}$ als Primfaktor von $\begin{eqnarray*} S \end{eqnarray*}$ vorkommen? Immerhin kann es ja auch andere Primzahlen $\begin{eqnarray*} q \end{eqnarray*}$ geben mit $\begin{eqnarray*} n < q \leq 2n \end{eqnarray*}$ , sodass $\begin{eqnarray*} S \end{eqnarray*}$ eine Primfaktorzerlegung dieser Primzahlen ist und $\begin{eqnarray*} p \end{eqnarray*}$ nicht enthalten ist.

Auch wenn ich die Primzahlen $\begin{eqnarray*} \leq n \end{eqnarray*}$ elminiere und $\begin{eqnarray*} p \end{eqnarray*}$ herausschreibe: Aus $\begin{eqnarray*} S = pc \end{eqnarray*}$ , wobei $\begin{eqnarray*} c \end{eqnarray*}$ der verbleiende Bruch ist, folgt nicht $\begin{eqnarray*} c \in \mathbb{N} \end{eqnarray*}$

Zu deinem zweiten Beitrag:
Auch ist mir unklar, wieso nur Primfaktoren $\begin{eqnarray*} \leq n \end{eqnarray*}$ vorkommen sollten bei $\begin{eqnarray*} \binom{2n}{n}\prod_{p_i\in P_n}\frac 1 {p_i} \end{eqnarray*}$ . Hier sind ja alle Primzahlen im Zähler elimniniert, die restlichen stehen nur im Nenner.

23.04.2013, 18:56

PeterSchmitt

Auf diesen Beitrag antworten »

Auf jeden Fall herzlichen Dank! smile

23.04.2013, 19:12

RavenOnJ

Auf diesen Beitrag antworten »

Sei $\begin{eqnarray*} n< p\le 2n, p\text{ prim} \end{eqnarray*}$ . Es ist doch hoffentlich klar, dass p ein Primfaktor in $\begin{eqnarray*} (2n)! \end{eqnarray*}$ ist, da die Zahl auf alle Fälle in der Menge $\begin{eqnarray*} \{1,2,3,\cdots,2n\} \end{eqnarray*}$ enthalten ist. In den Zahlen $\begin{eqnarray*} 1,2,3,\cdots,n \end{eqnarray*}$ können aber nur Primfaktoren $\begin{eqnarray*} \le n \end{eqnarray*}$ vorkommen. Das gilt dann ebenso in $\begin{eqnarray*} n! \end{eqnarray*}$ und in $\begin{eqnarray*} (n!)^2 \end{eqnarray*}$ . Der Primfaktor p in $\begin{eqnarray*} (2n)! \end{eqnarray*}$ wird also in $\begin{eqnarray*} \binom{2n}{n} \end{eqnarray*}$ nicht neutralisiert, muss also auch dort als Primfaktor enthalten sein.

23.04.2013, 19:20

RavenOnJ

Auf diesen Beitrag antworten »

Zitat:

Original von RavenOnJ
Man könnte noch hinterherschicken: Jede Primzahl $\begin{eqnarray*} n<p_i \le 2n \end{eqnarray*}$ kommt in der Zerlegung von $\begin{eqnarray*} \binom{2n}{n} \end{eqnarray*}$ mit Multiplizität Eins vor. Sei also $\begin{eqnarray*} P_n \end{eqnarray*}$ die Menge aller Primzahlen mit $\begin{eqnarray*} P_n:=\{p\;|\;n <p\le 2n, p\text{ prim}\} \end{eqnarray*}$ , dann kommen in der Primfaktorzerlegung von $\begin{eqnarray*} \binom{2n}{n}\prod_{p_i\in P_n}\frac 1 {p_i} \end{eqnarray*}$ nur Primfaktoren $\begin{eqnarray*} \le n \end{eqnarray*}$ vor.

Ich möchte dich auf die Definition von $\begin{eqnarray*} P_n \end{eqnarray*}$ aufmerksam machen. In dieser Menge sind alle Primzahlen $\begin{eqnarray*} > n \end{eqnarray*}$ und $\begin{eqnarray*} \le 2 n \end{eqnarray*}$ enthalten. Man kann zeigen, dass diese in der Primfaktorzerlegung von $\begin{eqnarray*} (2n)! \end{eqnarray*}$ genau mit Multiplizität 1 vorkommen. Teilt man also $\begin{eqnarray*} (2n)! \end{eqnarray*}$ durch alle diese Primzahlen, dann können in $\begin{eqnarray*} (2n)! \end{eqnarray*}$ nur noch Primfaktoren $\begin{eqnarray*} \le n \end{eqnarray*}$ vorkommen und in $\begin{eqnarray*} \binom{2n}{n} \end{eqnarray*}$ natürlich auch.

23.04.2013, 22:20

RavenOnJ

Auf diesen Beitrag antworten »

Ein Beispiel:

$\begin{eqnarray*} \binom{200}{100} = 90548514656103281165404177077484163874504589675413336841320 \end{eqnarray*}$

$\begin{eqnarray*} P_{100} =\{ 101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193<br /> ,197,199\} \end{eqnarray*}$

$\begin{eqnarray*} \binom{200}{100}\prod_{p_i\in P_{100}}\frac 1 {p_i} = 26765107838040=2^3\cdot 3\cdot 5\cdot 11\cdot 13^2\cdot 17\cdot 37\cdot 53\cdot 59\cdot 61 \end{eqnarray*}$

Alle Primfaktoen sind $\begin{eqnarray*} \le 100 \end{eqnarray*}$ . Man kann sogar zeigen, dass sie alle $\begin{eqnarray*} \le\frac 2 3 100\approx 66 \end{eqnarray*}$ sein müssen.

24.04.2013, 11:46

PeterSchmitt

Auf diesen Beitrag antworten »

Herzlichen Dank RavenOnJ für deine Mühen! smile

Nun habe auch ich es verstanden! smile

Neue Frage »

Antworten »

Zahlentheorie: Teilbarkeit Binomialkoeffizient

Verwandte Themen