Primzahlen und Binomialkoeffizienten

18.05.2009, 17:09

plizzz

Primzahlen und Binomialkoeffizienten

Hi Leute,
ich muss morgen einen Seminarvortrag halten und mir ist da heute eine kleine Lücke in einem Beweis aufgefallen. Und zwar will ich beweißen, dass

$\begin{eqnarray*} \begin{pmatrix} p \\ k \end{pmatrix} \end{eqnarray*}$ durch p teilbar ist für $\begin{eqnarray*} 1\leq k\leq p-1 \end{eqnarray*}$ .

Nun weiß ich:

$\begin{eqnarray*} \begin{pmatrix} p \\ k \end{pmatrix} = \frac{p*(p-1)*...*(p-k+1)}{k!} \end{eqnarray*}$

Dass das p sich nicht rauskürzt und der Binomialkoeffizient eine ganze Zahl ist, ist klar. Aber damit $\begin{eqnarray*} \begin{pmatrix} p \\ k \end{pmatrix} \end{eqnarray*}$ durch p teilbar ist, muss ja gelten:

$\begin{eqnarray*} \begin{pmatrix} p \\ k \end{pmatrix}=p*z , z\in Z \end{eqnarray*}$ .
Also woher weiß ich, dass $\begin{eqnarray*} \frac{(p-1)*...*(p-k+1)}{k!} \end{eqnarray*}$ eine ganze Zahl ist?

Oder verfolge ich komplett den falschen Ansatz?

Wäre super, wenn mir jemand bis morgen helfen könnte, da es echt wichtig für mich ist.

Also vielen Dank, plizzz

18.05.2009, 17:20

WebFritzi

Auf diesen Beitrag antworten »

Wie wäre es mit Induktion über p? Es gibt da doch diese Rekursionsformeln für Binomialkoeffizienten.

18.05.2009, 17:28

Auf diesen Beitrag antworten »

Zitat:

Original von plizzz
Dass das p sich nicht rauskürzt und der Binomialkoeffizient eine ganze Zahl ist, ist klar.

Wenn das so "klar" ist, dann bist du bereits fertig - musst es nur noch ordentlich aufschreiben. Augenzwinkern

18.05.2009, 20:53

plizzz

Auf diesen Beitrag antworten »

Das denke ich eben nicht. Ich habe ja
$\begin{eqnarray*} \begin{pmatrix} p \\ k \end{pmatrix} = p*\frac{(p-1)*...*(p-k+1)}{k!} \end{eqnarray*}$

Und damit $\begin{eqnarray*} \begin{pmatrix} p \\ k \end{pmatrix} \end{eqnarray*}$ durch p teilbar ist, muss ja $\begin{eqnarray*} \frac{\begin{pmatrix} p \\ k \end{pmatrix}}{p} \end{eqnarray*}$ eine ganze Zahl ergeben, also muss, damit wir auf Teilbarkeit schließen können, auch
$\begin{eqnarray*} \frac{(p-1)*...*(p-k+1)}{k!} \end{eqnarray*}$ eine ganze Zahl sein. Aber dass es eine ist, weiß ich ja nicht. Oder übersehe ich etwas?

Oder anders: Woher weiß ich, dass der Binomialkoeffizient erst dadurch zu einer Ganzzahl wird, dass ich ihn mit p multipliziere?

18.05.2009, 21:34

willy

Auf diesen Beitrag antworten »

Ist das nicht ganz einfach?
Wenn k wie du vorausgesetzt hast, größer-gleich 1 und kleiner-gleich (p-1) ist, dann ist doch der Binomialkoeffizient "(p-1) über k" mindestens 1 (genau dann wenn k=(p-1) oder größer und eine ganze Zahl. Dann ist aber "p über k" geteilt durch p immer eine ganze Zahl und im Fall k=(p-1) genau 1, da "p über k" geteilt durch p gleich "(p-1) über k" ist.

18.05.2009, 22:22

plizzz

Auf diesen Beitrag antworten »

Den Ansatz hatte ich auch schon, aber $\begin{eqnarray*} \frac{\begin{pmatrix} p \\ k \end{pmatrix}}{p} \end{eqnarray*}$ ist nicht $\begin{eqnarray*} \begin{pmatrix} p-1 \\ k \end{pmatrix} \end{eqnarray*}$ , sondern $\begin{eqnarray*} \frac{\begin{pmatrix} p-1 \\ k \end{pmatrix}}{p-k} \end{eqnarray*}$ .

19.05.2009, 02:24

WebFritzi

Auf diesen Beitrag antworten »

Zitat:

Original von Arthur Dent

Zitat:

Original von plizzz
Dass das p sich nicht rauskürzt und der Binomialkoeffizient eine ganze Zahl ist, ist klar.

Wenn das so "klar" ist, dann bist du bereits fertig - musst es nur noch ordentlich aufschreiben. Augenzwinkern

Arthur hat recht. Du bist fertig - siehst es allerdings scheinbar noch nicht. Beachte, dass p eine Primzahl ist (was du leider nur in der Überschrift dieses Threads erwähnt hast) und dass diese in der Primzahlzerlegung von k! nicht vorkommt.

EDIT: Es schreibt sich übrigens "beweisen" und nicht "beweißen". Augenzwinkern

19.05.2009, 07:19

plizzz

Auf diesen Beitrag antworten »

Ja gut, dass k! kein p in seiner Primfaktorzerlegung haben kann, ist klar und führt ja eben dazu, dass p sich nicht rauskürzt. Mein Problem konstruiere ich jetzt mal an einem Beispiel, das natürlich nicht stimmen kann, da es ja Fakt ist, dass $\begin{eqnarray*} \begin{pmatrix} p \\ k \end{pmatrix} \end{eqnarray*}$ durch p teilbar ist.

Angenommen, wir haben unseren Binomialkoeffizienten $\begin{eqnarray*} \begin{pmatrix} p \\ k \end{pmatrix} \end{eqnarray*}$ und p ist ne Primzahl, z.B. p=5. Dann ist $\begin{eqnarray*} \begin{pmatrix} p \\ k \end{pmatrix} \end{eqnarray*}$ eine ganze Zahl. Aber $\begin{eqnarray*} \begin{pmatrix} p \\ k \end{pmatrix} \end{eqnarray*}$ kann ja auch eine ganze Zahl sein, indem z.B.

$\begin{eqnarray*} \begin{pmatrix} p \\ k \end{pmatrix}=p*\frac{(p-1)*...*(p-k+1)}{k!}=5*5.2=21 \end{eqnarray*}$ (was natürlich nicht stimmen kann). In diesem Fall wären aber meine beiden Voraussetzungen erfüllt, nämlich, dass p eine Primzahl ist und $\begin{eqnarray*} \begin{pmatrix} p \\ k \end{pmatrix} \end{eqnarray*}$ eine ganze Zahl ist. Warum kann das nicht sein?

Sorry Jungs, aber bin gerade etwas vor den Kopf gestoßen. Finds aber super, dass hier so schnell so viele Antworten kommen!

19.05.2009, 07:32

WebFritzi

Auf diesen Beitrag antworten »

Die Primfaktoren von k! kürzen sich raus. p ist nicht dabei.

19.05.2009, 08:54

Auf diesen Beitrag antworten »

Das ganze ist eine elementare Folgerung aus der Eindeutigkeit der Primfaktorzerlegung:

Zitat:

Gilt $\begin{eqnarray*} a\cdot b = p\cdot c \end{eqnarray*}$ mit einer Primzahl $\begin{eqnarray*} p \end{eqnarray*}$ , und ist $\begin{eqnarray*} p \end{eqnarray*}$ KEIN Teiler von $\begin{eqnarray*} a \end{eqnarray*}$ , so MUSS $\begin{eqnarray*} p \end{eqnarray*}$ in der Primfaktorzerlegung von $\begin{eqnarray*} b \end{eqnarray*}$ auftauchen - anders gesprochen: $\begin{eqnarray*} p \end{eqnarray*}$ ist ein Teiler von $\begin{eqnarray*} b \end{eqnarray*}$ .

Genau das wendet man im vorliegenden Fall an, und zwar auf

$\begin{eqnarray*} a &=& k! \\ b &=& \binom{p}{k} \\ c &=& (p-1)\cdot\ldots\cdot (p-k+1) \end{eqnarray*}$ .

Der eigentlich schwierigere Teil ist der Nachweis, dass $\begin{eqnarray*} \binom{p}{k} \end{eqnarray*}$ (oder allgemein $\begin{eqnarray*} \binom{n}{k} \end{eqnarray*}$ ) überhaupt eine ganze Zahl ist - aber das ist dir ja anscheinend schon anderweitig klar. Beweisen lässt es sich übrigens leicht über das Konstruktionsprinzip des Pascalschen Dreiecks.

19.05.2009, 12:42

plizzz

Auf diesen Beitrag antworten »

Ah!
Das ist genau das, was ich gesucht habe. Ist auch irgendwie total klar, da war ich wohl nur etwas zu doof.

Warum
$\begin{eqnarray*} \begin{pmatrix} p \\ k \end{pmatrix} \end{eqnarray*}$ eine ganze Zahl ist, habe ich mich auch schon gefragt - allerdings muss ich das zum Glück (noch nicht) beweisen, sondern kann es als gegeben voraussetzen.

Danke!

19.05.2009, 13:30

WebFritzi

Auf diesen Beitrag antworten »

Zitat:

Original von plizzz
Warum $\begin{eqnarray*} \begin{pmatrix} p \\ k \end{pmatrix} \end{eqnarray*}$ eine ganze Zahl ist, habe ich mich auch schon gefragt - allerdings muss ich das zum Glück (noch nicht) beweisen, sondern kann es als gegeben voraussetzen.

Das geht z.B. per Induktion über p und die Rekursionsformel für Binomialkoeffizienten.

Neue Frage »

Antworten »

Primzahlen und Binomialkoeffizienten

Verwandte Themen