Zahlentheoretischer Beweis mit Binomialkoeffizient

21.05.2007, 12:00

mylittlehelper

Zahlentheoretischer Beweis mit Binomialkoeffizient

Hallo liebe Community,

ich bin im Rahmen meiner Zahlentheorievorbereitung auf folgendes Problem gestoßen. Ich habe dazu leider weder hier noch in den Weiten des sonstigen Internets eine Lösung dazu gefunden. Dies liegt evtl. daran, dass ich nicht so recht weiß, welche Suchbegriffe ich verwenden kann.

Die Aufgabe lautet wie folgt:

Sei $\begin{eqnarray*} p>2 \end{eqnarray*}$ Primzahl und $\begin{eqnarray*} 0<a<p-1,\; a\in\mathbb{Z} \end{eqnarray*}$ . Beweisen Sie, dass dann gilt:

$\begin{eqnarray*} \binom{p-1}{a} \equiv (-1)^a \mod p \end{eqnarray*}$

Als Hinweis wurde noch gegeben: $\begin{eqnarray*} \binom{p-1}{a} \end{eqnarray*}$ ist das Zeichen für den betreffenden Binomialkoeffizienten.

Ich habe auch einen Ansatz für die Aufgabe, der aber nicht zum Erfolg geführt hat. Aus diesem Grunde poste ich ihn auch nicht, damit ihr unbefangen an die Aufgabe rangehen könnt.

Schon mal vorab danke für eure Mühe,

Chris

21.05.2007, 12:09

Lazarus

Auf diesen Beitrag antworten »

Ich bin mir nicht sicher, aber evtl. hilft ja $\begin{eqnarray*} {n\choose k}=\left(-1\right)^k \cdot {k-n+1 \choose k} \end{eqnarray*}$ weiter ?

21.05.2007, 13:03

Auf diesen Beitrag antworten »

Eigentlich muss man sich den Binomialkoeffizienten nur mal richtig aufschreiben:

$\begin{eqnarray*} \binom{p-1}{a} = \frac{(p-1)\cdot (p-2)\cdot \ldots \cdot (p-a)}{1\cdot 2\cdot \ldots \cdot a} = \frac{p-1}{1}\cdot \frac{p-2}{2}\cdot \ldots \cdot \frac{p-a}{a} \end{eqnarray*}$

Und jetzt betrachte man mal jeden der Faktoren rechts einzeln modulo $\begin{eqnarray*} p \end{eqnarray*}$ . Augenzwinkern

Zitat:

Original von Lazarus
aber evtl. hilft ja $\begin{eqnarray*} {n\choose k}=\left(-1\right)^k \cdot {k-n+1 \choose k} \end{eqnarray*}$ weiter ?

Da hat sich entweder ein Denk- oder ein Schreibfehler eingeschlichen - richtig ist

$\begin{eqnarray*} \binom{n}{k} = \left(-1\right)^k \cdot \binom{k-n-1}{k} \end{eqnarray*}$ .

21.05.2007, 14:36

mylittlehelper

Auf diesen Beitrag antworten »

Ok, erstmal vielen Dank! Allerdings muss ich nochmal nachhaken, da ich nicht so der Vollprofi im Rechnen mit Restklassen bin.

Wir haben $\begin{eqnarray*} a \end{eqnarray*}$ Faktoren, d.h. jeder einzelne müsste $\begin{eqnarray*} -1 \mod p \end{eqnarray*}$ sein. Für den ersten $\begin{eqnarray*} p-1=-1+p\equiv -1 \mod p \end{eqnarray*}$ ist das auch sofort einsichtig.

Aber bereits bei $\begin{eqnarray*} \frac{p-2}{2}=-1+\frac{p}{2} \end{eqnarray*}$ scheiterts bei mir am Erklärungsmuster.

Evtl. könntest du dir ja nochmal 5min Zeit nehmen und mir allg. erklären, warum $\begin{eqnarray*} -1+\frac{p}{k} \equiv -1 \mod p \end{eqnarray*}$ für ein $\begin{eqnarray*} k\in\mathbb{Z} \end{eqnarray*}$ ist.

21.05.2007, 14:45

Auf diesen Beitrag antworten »

Zitat:

Original von mylittlehelper
Aber bereits bei $\begin{eqnarray*} \frac{p-2}{2}=-1+\frac{p}{2} \end{eqnarray*}$ scheiterts bei mir am Erklärungsmuster.

Nein, es scheitert nicht. Du bist es nur nicht gewohnt, im Restklassenkörper modulo $\begin{eqnarray*} p \end{eqnarray*}$ richtig zu rechnen...

Na egal, es geht auch ohne Körper nur im Ring: Rechne

$\begin{eqnarray*} (p-1)\cdot (p-2)\cdot \ldots \cdot (p-a) \equiv (-1)\cdot (-2)\cdot \ldots \cdot (-a) \mod p \end{eqnarray*}$ ,

dann kommt dir vielleicht so die Erleuchtung.

21.05.2007, 15:28

mylittlehelper

Auf diesen Beitrag antworten »

Manchmal sieht man den Wald vor lauter Bäumen nicht! Alles klar und vielen Dank. Mein Problem war, dass ich die Terme vereinfacht habe, statt die Addition von $\begin{eqnarray*} p \end{eqnarray*}$ direkt wegzulassen, da dies ja immer in der gleichen Restklasse landet.

Klasse finde ich im Übrigen, dass Du nicht direkt die Lösung vorgegeben hast - so war der AHA-Effekt um Längen größer.

Neue Frage »

Antworten »

Zahlentheoretischer Beweis mit Binomialkoeffizient

Verwandte Themen