Binomialkoeffizent und Teilbarkeit

28.04.2008, 20:22

dommi88

Auf diesen Beitrag antworten »

Binomialkoeffizent und Teilbarkeit

Sei p eine Primzahl. In dieser Aufgabe werden Binomialkoeffizenten betrachtet.
a) Zeigen sie, dass (p über k) für 0 < k < p durch p teilbar ist.
b) Unter welcher Voraussetzung an p und k ist (2p) über k durch p teilbar?

Das sind meine Aufgaben. Meine bisherigen Überlegungen:
zu a) p über k = p! / ((k! ( p-k)!)
Nun ist es ja egal, was im Nenner steht, solange dieser kleiner p! ist, denn dann ist p! auf jeden fall durch p teilbar. Die Frage ist nur, wie ich dieses richtig aufschreiben soll.

zu b) 2p über k = (2p)! / ((k! ( 2p-k)!)
mit ähnlicher Überlegung komme ich darauf, dass k < 2p sein muss. Aber ist das schon alles?
Wie kann ich das vernünftig aufschreiben?

28.04.2008, 20:25

tmo

Auf diesen Beitrag antworten »

Du nutzt bei der a) gar nicht aus, dass p eine Primzahl ist. Das steht nicht umsonst in der Vorraussetzung.

Bei der b) solltest du mal den fall k = p betrachten.

28.04.2008, 20:56

dommi88

Auf diesen Beitrag antworten »

zu a) ok, wenn p prim ist, dann kann p nicht als das produkt mehrerer zahlen geschrieben werden, also kann (k! (p-k)! nicht gleich p sein. somit haben wir als ergebnis der ausmultiplikation eine (zusammengesetzte) zahl mal eine primzahl und diese ist natürlich durch die primzahl selbst teilbar.

b) für k= p ergibt sich p! / (p!) = 1 und 1 ist nicht durch p teilbar.

28.04.2008, 21:00

tmo

Auf diesen Beitrag antworten »

Bei der a) fehlt immer noch das entscheidende. Wichtig ist nämlich, dass die Zahl $\begin{eqnarray*} k!(p-k)! \end{eqnarray*}$ keinen gemeinsamen Primfaktor mit p haben kann.

zur b) es geht doch um $\begin{eqnarray*} \binom{2p}{k} \end{eqnarray*}$ . Da sollst du k = p betrachten.

29.04.2008, 16:39

dommi88

Auf diesen Beitrag antworten »

a) p über k = p! / ((k! ( p-k)!) = p · (p-1) · · · · · (p- k +2)(p- k +1) / (1 · 2 · · · · · (k -1) · k) ist auch noch ne andere Darstellung, aber irgendwie komm ich da nicht weiter.
Kannst du mir nicht helfen?

b) wenn ich 2p über k = (2p)! / ((k! ( 2p-k)!) für p=k betrachte bekomme ich doch:
2p über p = (2p)! / ((p! (2p-p)!) = (2p)! / (p! p!) = 2^k p! / (p! p!)
Kann ich das weiter vereinfachen?

Steh da echt aufm Schlauch...

29.04.2008, 17:04

dommi88

Auf diesen Beitrag antworten »

noch ne Überarbeitung:

ich kann p über k schreiben als [p(p − 1) · · · (-p − k + 1)(p − k) · · · 1] / [k(k − 1) · · · · 1 · (p − k) · · · 1 ]

= [p(p − 1) · · · (p − k + 1)] / k! diese Beziehung habe ich gerade in einem Skript nach gelesen. Da nach Voraussetzung p Primzahl ist, bleibt oben auf jeden Fall das p stehen, da p nur doch sich selbst teilbar ist und da k < p, dann k! auch kein p enthalten und deswegen muss der ganze Term auch durch p teilbar sein.

Anzeige

29.04.2008, 17:07

dommi88

Auf diesen Beitrag antworten »

noch ne Überarbeitung zu a:

ich kann p über k schreiben als [p(p - 1) · · · (-p - k + 1)(p - k) · · · 1] / [k(k - 1) · · · · 1 · (p - k) · · · 1 ]

= [p(p - 1) · · · (p - k + 1)] / k! diese Beziehung habe ich gerade in einem Skript nach gelesen. Da nach Voraussetzung p Primzahl ist, bleibt oben auf jeden Fall das p stehen, da p nur doch sich selbst teilbar ist und da k < p, dann k! auch kein p enthalten und deswegen muss der ganze Term auch durch p teilbar sein.

29.04.2008, 17:12

tmo

Auf diesen Beitrag antworten »

Zitat:

Original von tmo
Wichtig ist nämlich, dass die Zahl $\begin{eqnarray*} k!(p-k)! \end{eqnarray*}$ keinen gemeinsamen Primfaktor mit p haben kann.

p! enthält den Primfaktor p genau einmal. Also enthält ihn $\begin{eqnarray*} \frac{p!}{k!(p-k)!} \end{eqnarray*}$ auch genau einmal. Das musst du noch etwas ausformulieren.

dann nochmal zur b)

$\begin{eqnarray*} \binom{2p}{p} = \frac{(2p)!}{(p!)^2} \end{eqnarray*}$

Wie oft enhält (2p)! den Primfaktor p? Und wie oft enthält $\begin{eqnarray*} (p!)^2 \end{eqnarray*}$ den Primfaktor p?

PS: Du könntest dir übrigens mal angewöhnen den Formeleditor zu benutzen. Binomialkoeffizienten gehen mit \binom{n}{k}

29.04.2008, 17:32

dommi88

Auf diesen Beitrag antworten »

ok, teil a ist klar!
zu b)
$\begin{eqnarray*} \binom{2p}{p} = \frac{(2p)!}{(p!)^2} \end{eqnarray*}$
da ist mir noch nicht ganz klar, wie das aussieht.
ist

$\begin{eqnarray*} \frac{(2p)!}{(p!)^2} = \frac{(2^p p!)}{(p! p!)} \end{eqnarray*}$
falls dem so ist, kommt der Faktor p im Zähler einmal vor und im Nenner kommt p^2 vor und somit wäre das ganze dann nicht durch p teilbar oder seh ich da schon wieder vor lauter Bäumen den Wald nicht...

Übrigens danke für deine Hilfe und Geduld smile

smile

29.04.2008, 18:48

tmo

Auf diesen Beitrag antworten »

Wie kommst du denn darauf, dass $\begin{eqnarray*} (2p)! = 2^p p! \end{eqnarray*}$ gelten würde?

Es ist $\begin{eqnarray*} (2p)! = 2p \cdot (2p-1) \cdot \dotsb \cdot 2 \cdot 1 \end{eqnarray*}$

Wie oft kommt in diesem Produkt der Primfaktor p vor?

Dass der Primfaktor p im Nenner ( $\begin{eqnarray*} (p!)^2 \end{eqnarray*}$ ) 2 mal vorkommt, ist schonmal richtig.

29.04.2008, 18:57

dommi88

Auf diesen Beitrag antworten »

Zitat:

Original von tmo
Wie kommst du denn darauf, dass $\begin{eqnarray*} (2p)! = 2^p p! \end{eqnarray*}$ gelten würde?

Es ist $\begin{eqnarray*} (2p)! = 2p \cdot (2p-1) \cdot \dotsb \cdot 2 \cdot 1 \end{eqnarray*}$

Wie oft kommt in diesem Produkt der Primfaktor p vor?

Dass der Primfaktor p im Nenner ( $\begin{eqnarray*} (p!)^2 \end{eqnarray*}$ ) 2 mal vorkommt, ist schonmal richtig.

alle Faktoren ab (2p-k) kürzen sich ja raus, also bleibt noch
$\begin{eqnarray*} \frac{2p(2p-1)...(2p-k+1)}{k!} \end{eqnarray*}$
d.h. oben haben wir noch p in der potenz k+1, oder nich?

29.04.2008, 19:01

tmo

Auf diesen Beitrag antworten »

Wollen wir nicht erstmal den Spezialfall k = p zu Ende bringen? Sonst wird das hier zu unübersichtlich.

Du schuldest mir nämlich immer noch eine Antwort:

Zitat:

Original von tmo
Es ist $\begin{eqnarray*} (2p)! = 2p \cdot (2p-1) \cdot \dotsb \cdot 2 \cdot 1 \end{eqnarray*}$
Wie oft kommt in diesem Produkt der Primfaktor p vor?

29.04.2008, 19:20

dommi88

Auf diesen Beitrag antworten »

Zitat:

Original von tmo
Wollen wir nicht erstmal den Spezialfall k = p zu Ende bringen? Sonst wird das hier zu unübersichtlich.

Du schuldest mir nämlich immer noch eine Antwort:

Zitat:

Original von tmo
Es ist $\begin{eqnarray*} (2p)! = 2p \cdot (2p-1) \cdot \dotsb \cdot 2 \cdot 1 \end{eqnarray*}$
Wie oft kommt in diesem Produkt der Primfaktor p vor?

oh klar...irgendwie hab ich da wohl wieder nen schritt übersprungen :-\
also das Produkt hat 2p Faktoren, wobei die letzen beiden 2 und 1 sind...in allen anderen müsste dann noch etwas der form (2p-?) stehen und das 2p mal...also kommt p^(2p) als höchste potenz vor

29.04.2008, 21:01

AD

Auf diesen Beitrag antworten »

Zitat:

Original von dommi88
in allen anderen müsste dann noch etwas der form (2p-?) stehen und das 2p mal...also kommt p^(2p) als höchste potenz vor

Also diese Logik versteht außer dir wohl keiner - sie ist auch falsch. Wenn du es nicht glaubst, dann rechne das Produkt doch mal für ganz konkrete $\begin{eqnarray*} p \end{eqnarray*}$ aus, z.B. p=3, p=5 oder p=7. Dann wirst du sehen, dass $\begin{eqnarray*} p \end{eqnarray*}$ in einer viel, viel kleineren Potenz in $\begin{eqnarray*} (2p)! \end{eqnarray*}$ enthalten ist.

Anscheinend unterliegst du dem Trugschluss, dass jeder der Faktoren $\begin{eqnarray*} (2p-?) \end{eqnarray*}$ durch $\begin{eqnarray*} p \end{eqnarray*}$ teilbar ist. Tatsächlich trifft dies nur auf sehr wenige dieser Faktoren zu!

29.04.2008, 21:12

dommi88

Auf diesen Beitrag antworten »

scheint wohl irgendwie nicht mein Tag zu sein....
für p=3 ist (2p)! = 6 * 5 * 4 * 3 * 2 * 1
p=5 ist das 10 * 9 * 8 * 7 * 6 * 5 * 4 *3 * 2 oder nicht?
dann müsste da für 2p! im Zähler p^p stehen
Falls das auch wieder falsch ist, wäre ich sehr dankbar, wenn du mir sagen könntest, was rauskommt...

29.04.2008, 21:17

AD

Auf diesen Beitrag antworten »

Wie kommst du denn auf $\begin{eqnarray*} p^p \end{eqnarray*}$ ??? Es ist lediglich $\begin{eqnarray*} p^2 \end{eqnarray*}$ .

29.04.2008, 21:22

dommi88

Auf diesen Beitrag antworten »

Zitat:

Original von Arthur Dent
Wie kommst du denn auf $\begin{eqnarray*} p^p \end{eqnarray*}$ ??? Es ist lediglich $\begin{eqnarray*} p^2 \end{eqnarray*}$ .

ich hab doch mehrere Terme die ein p enthalten, p, p-1...etc oder nicht?
auf p^2 wäre ich auf jeden Fall nicht gekommen
das würde dann heißen, ich hätte sowohl im Nenner p^2 als auch auch im Zähler...
da dann ja scheinbar kein p mehr übrig bleibt, ist der Binomialkoeffizent auch nicht durch p teilbar für p=k

29.04.2008, 21:28

AD

Auf diesen Beitrag antworten »

Zitat:

Original von dommi88

Zitat:

Original von Arthur Dent
Wie kommst du denn auf $\begin{eqnarray*} p^p \end{eqnarray*}$ ??? Es ist lediglich $\begin{eqnarray*} p^2 \end{eqnarray*}$ .

ich hab doch mehrere Terme die ein p enthalten, p, p-1...etc oder nicht?

Was hast du denn für ein Verständnis von Teilbarkeit, wenn du so eine Frage stellst? unglücklich

unglücklich

Zitat:

Original von dommi88
das würde dann heißen, ich hätte sowohl im Nenner p^2 als auch auch im Zähler...
da dann ja scheinbar kein p mehr übrig bleibt, ist der Binomialkoeffizent auch nicht durch p teilbar für p=k

Genauso ist es - was denkst du, warum tmo dich gerade auf dieses Beispiel aufmerksam gemacht hat!

29.04.2008, 21:37

dommi88

Auf diesen Beitrag antworten »

Zitat:

Original von Arthur Dent

Zitat:

Original von dommi88

Zitat:

Original von Arthur Dent
Wie kommst du denn auf $\begin{eqnarray*} p^p \end{eqnarray*}$ ??? Es ist lediglich $\begin{eqnarray*} p^2 \end{eqnarray*}$ .

ich hab doch mehrere Terme die ein p enthalten, p, p-1...etc oder nicht?

Was hast du denn für ein Verständnis von Teilbarkeit, wenn du so eine Frage stellst? unglücklich

unglücklich

Zitat:

Original von dommi88
das würde dann heißen, ich hätte sowohl im Nenner p^2 als auch auch im Zähler...
da dann ja scheinbar kein p mehr übrig bleibt, ist der Binomialkoeffizent auch nicht durch p teilbar für p=k

Genauso ist es - was denkst du, warum tmo dich gerade auf dieses Beispiel aufmerksam gemacht hat!

oh man, ich hab die ganze Zeit gar nicht an Teilbarkeit gedacht...
und was bleibt nun noch zu tun? ich kann ja nun nicht jede beziehung austesten. oder funktioniert es sonst immer mit der einschränkung, dass k < p ist?

29.04.2008, 21:42

AD

Auf diesen Beitrag antworten »

Wir sind ja hier im Hochschulforum, da sollte man auch mal selbst was rauskriegen. Und da kann ich nur wieder diese Empfehlung aussprechen: Ruhig mal ein bisschen probieren, konkrete Zahlenwerte austesten ... bis man auf eine Vermutung kommt. Und die dann aber gründlich beweisen!

Nur mit den allgemeinen Fakultäten jonglieren, ohne sich das geringste konkrete Zahlenbeispiel anzusehen - das kann sich nur leisten, wer im Stoff "drinsteht". Das kannst du von dir ehrlicherweise nicht sagen.

Zitat:

Original von dommi88
oh man, ich hab die ganze Zeit gar nicht an Teilbarkeit gedacht...

Das verwundert mich etwas, wenn ich so den Threadtitel betrachte - den hast du doch gewählt! geschockt

geschockt

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »