Binomialkoeffizienten modulo p

Neue Frage »

Takir Auf diesen Beitrag antworten »
Binomialkoeffizienten modulo p
Meine Frage:
Für meine Facharbeit würde ich gerne die (meiner Meinung nach richtigen) Formeln bzw. zeigen, komme aber leider nicht mehr weiter.

Danke für jede Hilfe

Meine Ideen:
Die einfachere Identität hab ich schon gezeigt: (es gab kein Produktzeichen, deshalb habe ich hier ein Summenzeichen verwendet). Vermutlich gehen die beiden anderen Beweise ähnlich, aber irgendwie klappt es nicht so richtig.
PS.: Dass es nur mit Primzahlen möglich ist, kommt meiner Meinung nach daher, dass man dann nicht so einfach zu den Restklassen übergehen kann, solange (p-1)! noch im Nenner steht.
juffo-wup Auf diesen Beitrag antworten »

Also erstmal kann man in Latex ein Produktzeichen mit \prod (statt \sum) einfügen.

Dann liegst du mit deiner Vermutung
Zitat:
PS.: Dass es nur mit Primzahlen möglich ist, kommt meiner Meinung nach daher, dass man dann nicht so einfach zu den Restklassen übergehen kann, solange (p-1)! noch im Nenner steht.

richtig. Genauer gesagt sind modulo einer Zahl n diejenigen Elemente invertierbar (und man kann bei solchen Rechnungen in Zähler und Nenner getrennt reduzieren), die teilerfremd zu n sind. Bei also alle Zahlen außer den Vielfachen von p.
Das kann man denn auch nutzen, um aus zu bestimmen. Bei dem ersten Bruch kürzen sich nämlich mod alle Faktoren oben und unten, in denen anfangs kein p als Faktor vorkommt, gegenseitig weg, nachdem man bei den übrigen einmal ( noch nicht mod ) p gekürzt hat und was noch übrig bleibt...

Ein Ansatz um modulo zu berechnen, den ich gefunden habe, ist anknüpfend an deine Rechnung, mit der Umformung
Wenn man dieses Produkt ausmultipliziert, sind die meisten Summanden Null modulo
Takirion Auf diesen Beitrag antworten »

Danke für die Antwort, allerdings hat sie an einigen Stellen noch ein paar Fragen aufgeworfen:

Zitat:
Bei dem ersten Bruch kürzen sich nämlich mod alle Faktoren oben und unten, in denen anfangs kein p als Faktor vorkommt, gegenseitig weg, nachdem man bei den übrigen einmal ( noch nicht mod ) p gekürzt hat und was noch übrig bleibt...

Hm ok dieser Satz hat mich jetzt zugegeben noch etwas mehr verwirrt. Aus der Darstellung (warum bin ich eigentlich nich da drauf gekommen? es war doch nur noch ein Schritt Hammer ) hätte ich jetzt einfach modulo die beiden Terme mit "gekürzt" (also Modulo eben), wonach einfach übrig bleibt... oder ist diese Umformung nicht zulässig?



Zitat:
Wenn man dieses Produkt ausmultipliziert, sind die meisten Summanden Null modulo

Ok hier glaube ich verstanden zu haben, was du meinst und es klingt auch irgendwie recht logisch, aber irgendwie hält es dem Praxistest nicht stand...
p=7 k=4

alle restlichen Summanden werden mindestens als Faktor enthalten und damit modulo 49 gleich 0 sein (das war doch deine Argumentation (?)) es ist aber

wo sind meine Denkfehler?
HAL 9000 Auf diesen Beitrag antworten »

Also bitte... Rechne hier bitte mit echten Brüchen, wir sind hier in und nicht etwa in !!! So ist

juffo-wup Auf diesen Beitrag antworten »

Zitat:
Original von Takirion
Hm ok dieser Satz hat mich jetzt zugegeben noch etwas mehr verwirrt. Aus der Darstellung (warum bin ich eigentlich nich da drauf gekommen? es war doch nur noch ein Schritt Hammer ) hätte ich jetzt einfach modulo die beiden Terme mit "gekürzt" (also Modulo eben), wonach einfach übrig bleibt... oder ist diese Umformung nicht zulässig?

Das Produkt hat nicht Faktoren, sondern :

Bei den Nennern mit muss man aufpassen. Hier kann man nicht einfach sagen z.B.
Sondern
Für p=2,k=2 ergibt das z.B. was nicht kongruent 1 modulo 4 ist.

Das liegt wie gesagt daran, dass das Inversenbilden mod nur möglich ist bei Zahlen die teilerfremd zu n sind.
Wenn du den euklidischen Algorithmus kennst, weißt du vielleicht auch, dass genau im Falle der Teilerfremdheit von 2 ganzen Zahlen n,m eine Gleichung der Form
besteht mit a,b ganze Zahlen.
Modulo also
was impliziert, dass b mod n invertierbar ist.

Bezeichne immer die Restklasse von mod n. Gegeben 2 ganze Zahlen sodass eine ganze Zahl ist, d.h. mit k eine ganze Zahl.
Dann ist und
Also sind die beiden gleich. Das gilt aber nur, wenn man überhaupt bilden kann!
Für kann man z.B. nicht bilden. Denn wenn wäre, dann und Widerspruch.
Genauso für alle anderen Zahlen die nicht teilerfremd zu n sind.

Zitat:
Ok hier glaube ich verstanden zu haben, was du meinst und es klingt auch irgendwie recht logisch, aber irgendwie hält es dem Praxistest nicht stand...
p=7 k=4

alle restlichen Summanden werden mindestens als Faktor enthalten und damit modulo 49 gleich 0 sein (das war doch deine Argumentation (?))

Richtig. Beachte auch, dass die Nenner alle invertierbar mod sind (sodass man hier einfach so rechnen kann). Und Vorzeichenfehler, wenn ich das richtig sehe. 1-4=-3.

Zitat:
es ist aber
wo sind meine Denkfehler?

Dezimalbrüche ergeben nicht viel Sinn wie HAL schon gesagt hat. Man darf aber, solange die Nenner mod invertierbar sind (was hier ja der Fall ist), wie in rechnen und am Ende (Zähler und Nenner) modulo nehmen. Es reicht zu zeigen, dass 49 den Zähler des Bruches teilt, der neben dem 1+ steht. Dazu verweise ich auf HALs Antwort. Die Art zu Rechnen dort lässt sich auch verallgemeinern.
Takirion Auf diesen Beitrag antworten »

OK das mit den Brüchen war in der Tat blöd und auch sonst habe ich jetzt denke ich alles verstanden. Vielen Dank für eure Hilfe, waren echt sehr hilfreich und ausführlich. smile Freude
Lg
Takirion
 
 
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »