Binomialkoeffizient modulo Primzahl

29.05.2021, 13:19

MaPalui

Binomialkoeffizient modulo Primzahl

Hallo ihr lieben smile

ich hänge mal wieder an einer Umformng. Es soll gezeigt werden:
Sei p prim und sei $\begin{eqnarray*} 2\leq k \leq p-1 \end{eqnarray*}$ . Dann gilt $\begin{eqnarray*} \begin{pmatrix}p+1 \\ k \end{pmatrix}\pmod p = 0 \end{eqnarray*}$

Mein Ansatz:
$\begin{eqnarray*} \begin{pmatrix}p+1 \\ k \end{pmatrix} = \frac{(p+1)!}{k!(p+1-k)!} = p\cdot\frac{(p-1)!(p+1)}{k!(p+1-k)!} \end{eqnarray*}$
Nun genügt es ja zu zeigen, dass der Bruch eine Ganze Zahl ist. Kürzen ergibt $\begin{eqnarray*} \frac{(k+1)(k+2)\cdot\dots (p-1)(p+1)}{(p+1-k)!} \end{eqnarray*}$ .

Leider sehe ich jetzt nicht was ich noch tun kann.
Außerdem: Geht es vielleicht eleganter?

Danke und Gruß
Maren

29.05.2021, 13:45

Leopold

Auf diesen Beitrag antworten »

Von vorneherein ist klar, daß Binomialkoeffizienten ganze Zahlen sind. Am besten verwendest du die Darstellung

$\begin{align*} {{p+1} \choose k} = \frac{(p+1) \cdot p \cdot (p-1) \cdots (p-k+2)}{k \cdot (k-1) \cdot (k-2) \cdots 1} \end{align*}$

Nun schau dir Zähler und Nenner getrennt an. Und beachte die an $\begin{align*} k \end{align*}$ gestellten Bedingungen.

29.05.2021, 19:54

MaPalui

Auf diesen Beitrag antworten »

Hi Leopold,

danke für deine Bereitschaft, aber ich sehe das leider immernoch nicht.
Also diese darstellung sehe ich ja ein, mit Beispielen klappt es auch, aber weiter leider nicht. Hm verwirrt

also im Zähler sind k viele Faktoren, im Nenner auch.

29.05.2021, 20:04

Leopold

Auf diesen Beitrag antworten »

Und im Zähler ist der Faktor $\begin{align*} p \end{align*}$ zu sehen. Immer? Wie hängt das von $\begin{align*} k \end{align*}$ ab? Und im Nenner?
Beachte, daß Binomialkoeffizienten auf jeden Fall ganze Zahlen sind. Das ergibt sich allein schon daraus, daß sie ein kombinatorisches Problem lösen. Der Nenner muß sich daher vollständig wegkürzen lassen.

29.05.2021, 20:09

MaPalui

Auf diesen Beitrag antworten »

Also $\begin{eqnarray*} p \end{eqnarray*}$ ist im Nenner immer zu sehen, da es eine Primzahl ist. Ich kann $\begin{eqnarray*} p \end{eqnarray*}$ also mit keinem Element oder Produkten von Elementen des Nenners kürzen.
Im Nenner habe ich ja höchstens p-1 viele Faktoren, also tritt der Faktor p da gar nicht auf.

30.05.2021, 20:56

MaPalui

Auf diesen Beitrag antworten »

Also ich hänge da jetzt seit zwei Tagen dran aber sehe es nicht. Wer Lust hat kann mir ja nochmal helfen, sehe es leider nicht. Habe mehrere Skripte geschrieben und mir jede Menge Ansätze aufgeschrieben, ohne Erfolg. Ist ziemlich einfach nehme ich an.

Ah, ich glaube jetzt hab ich erst den anderen hinweis gerafft.

Zitat:

Original von Leopold
Der Nenner muß sich daher vollständig wegkürzen lassen.

Klar, Binomialkoeffizienten sind ganze Zahlen (check).
Die Darstellung verstehe ich auch und ist daher auch eine ganze Zahl (check).
Also lässt sich der Nenner komplett kürzen, aber da p prim ist, kann p nicht gekürzt werden. (das hätte ich wiederum gerne irgendwie analytisch. Ich würde also gerne den Restterm angeben, der übrig bleibt.=

30.05.2021, 21:35

Leopold

Auf diesen Beitrag antworten »

Zitat:

Original von MaPalui
Ich würde also gerne den Restterm angeben, der übrig bleibt.

$\begin{align*} \frac{1}{p} \cdot {{p+1} \choose k} \end{align*}$

Big Laugh

30.05.2021, 22:13

MaPalui

Auf diesen Beitrag antworten »

ok danke

Neue Frage »

Antworten »

Binomialkoeffizient modulo Primzahl

Verwandte Themen