Primzahl als Divisor < Algebra < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:47 So 19.08.2012 | | Autor: | Blake512 |
| Aufgabe | | Let p denote an arbitrary prime number. Explain why the binomial coefficient [mm] \vektor{p \\ i} [/mm] = [mm] \bruch{p!}{i!*(p-i)!} [/mm] is an integer which is divisible by p where 1 < i < p. |
Kann mir jemand weiterhelfen was die Vorgehensweise bei einer solchen Aufgabe betrifft? Welche Theorie benötige ich, um die Aufgabe lösen zu können? Für jegliche Inputs bin ich sehr dankbar!
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 16:56 So 19.08.2012 | | Autor: | Teufel |
Hi!
Formen wir das ganze mal zu [mm] i!\vektor{p \\ i}=\bruch{p!}{(p-i)!} [/mm] um. Nun teilt p die rechte Seite (wieso?), d.h. p teilt auch die linke Seite.
Für eine Primzahl p gilt nun: p|ab [mm] \Rightarrow [/mm] p|a oder p|b. Kommst du damit weiter?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 17:36 So 19.08.2012 | | Autor: | Blake512 |
Nun teilt p die rechte Seite (wieso?): weil p in p! enthalten ist. Der Nenner i!(p-i)! bzw. (p-i)! ist aber nicht durch p teilbar, weil es ein Produkt von Zahlen ist, welche kleiner als p sind.
Wie würdest du den Beweis formulieren?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 17:45 So 19.08.2012 | | Autor: | Teufel |
Wenn ich den Beweis so weitermache, wie ich ihn angefangen habe:
Also es gilt p teilt [mm] i!\vektor{p \\ i}. [/mm] p teilt aber nicht i!, denn p kommt nicht in i! vor (wenn i<p). Also muss p [mm] \vektor{p \\ i} [/mm] teilen.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 16:59 So 19.08.2012 | | Autor: | Blake512 |
| Aufgabe | | Let p denote a prime number. Give a convincing argument why the congruence [mm] (a+b)^p [/mm] = [mm] a^p [/mm] + [mm] b^p [/mm] mod p does hold for any integer a,b |
Mit Einsetzen von verschiedenen Primzahlen kann ich zwar nachvollziehen, dass die Behauptung stimmt aber einen allgemeinen Beweis konnte ich nicht herausfinden.
[mm] (a+b)^2 [/mm] = [mm] a^2 [/mm] + 2ab + [mm] b^2 [/mm] mod 2
[mm] (a+b)^3 [/mm] = [mm] a^3 [/mm] + [mm] 3a^2*b [/mm] + [mm] 3a*b^2 [/mm] + [mm] b^3 [/mm] = [mm] a^3 [/mm] + [mm] b^3 [/mm] mod 3
[mm] (a+b)^5 [/mm] = [mm] a^5 [/mm] + [mm] 5a^4*b [/mm] + [mm] 10a^3*b^2 [/mm] + [mm] 10a^2*b^3 [/mm] + [mm] 5a*b^4 [/mm] + [mm] b^5 [/mm] = [mm] a^5 [/mm] + [mm] b^5 [/mm] mod 5
etc.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 17:08 So 19.08.2012 | | Autor: | Teufel |
Das folgt, indem du [mm] (a+b)^p [/mm] mit dem Binomischen Lehrsatz ausschreibst und dann deine 1. Frage (und deren Antwort) beachtest.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:08 So 19.08.2012 | | Autor: | Blake512 |
Also wenn die Gleichung [mm] (a+b)^p [/mm] = [mm] \summe_{i=0}^{p} \vektor{p \\ i} a^{p-i}*b^p [/mm] gilt und [mm] \vektor{p \\ i} [/mm] = [mm] \bruch{p!}{i!*(p-i)!} [/mm] wie kann man daraus [mm] (a+b)^p \equiv a^p [/mm] + [mm] b^p [/mm] mod p herleiten?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:14 So 19.08.2012 | | Autor: | Teufel |
Es gilt ja: wenn $p|a$, dann ist $a [mm] \equiv [/mm] 0 [mm] \mod [/mm] p$. Nun weißt du, dass [mm] p|\vektor{p \\ i} [/mm] für 0<i<p.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:29 So 19.08.2012 | | Autor: | Blake512 |
Ah jetzt, was mir noch gefehlt hat ist die umgeschriebene Form der Formel: [mm] (a+b)^p [/mm] = [mm] a^b [/mm] + [mm] [\summe_{i=1}^{p-1} \vektor{p \\ i} a^{p-i}*b^p] [/mm] + [mm] b^p [/mm] wobei alles innerhalb der beiden Klammern [] 0 ist.
Danke für deine Hilfe!
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:30 So 19.08.2012 | | Autor: | reverend |
Hallo nochmal,
> Es gilt ja: wenn [mm]p|a[/mm], dann ist [mm]a \equiv 0 \mod p[/mm]. Nun
> weißt du, dass [mm]p|\vektor{p \\
i}[/mm] für 0<i<p.
Damit bleiben unabhängig von p nur noch zwei Glieder übrig, die möglicherweise nicht [mm] 0\mod{p} [/mm] sind.
Für 0<i<p ist ja [mm] \vektor{p\\i}a^ib^{p-i}\equiv 0\mod{p}.
[/mm]
Die Aussage [mm] (a+b)^p\equiv a^p+b^p\mod{p} [/mm] kannst Du anders aber auch über den "kleinen Fermat" beweisen.
Grüße
reverend
<i<p. <br=""></i
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 21:04 Mi 22.08.2012 | | Autor: | Blake512 |
| Aufgabe | | Wie beweist man die Aussage [mm] (a+b)^p \equiv a^p [/mm] + [mm] b^p [/mm] mod p über den "kleinen Fermat"? |
Ich weiss nur, dass [mm] a^p \equiv [/mm] a mod p gilt und [mm] a^{p-1} \equiv [/mm] 1 mod p (falls ggT(a,p) = 1) was mir leider nicht weiterhilft.
|
|
|
| |
|
Hallo nochmal,
> Wie beweist man die Aussage [mm](a+b)^p \equiv a^p[/mm] + [mm]b^p[/mm] mod p
> über den "kleinen Fermat"?
> Ich weiss nur, dass [mm]a^p \equiv[/mm] a mod p gilt und [mm]a^{p-1} \equiv[/mm]
> 1 mod p (falls ggT(a,p) = 1) was mir leider nicht
> weiterhilft.
Wieso hilft das nicht weiter?
Die erste Aussage (die die meisten übrigens vergessen), reicht doch völlig aus.
Damit ist die linke Seite kongruent zu [a+b].
Die rechte Seite ist (ganz unabhängig betrachtet) dann kongruent zu [a]+[b].
Und dass [mm] [a+b]\equiv [a]+[b]\mod{p} [/mm] ist, ist ja eine Grundregel der Modulrechnung.
Fertig. Man könnte (und sollte) das vielleicht noch schöner schreiben, mir ging es um den Gedankengang.
Grüße
reverend
|
|
|
| |
|
Hallo Blake,
das, was Teufel da tut, kannst Du auch in einem Schritt erledigen:
Da 1<i<p (besser wäre hier übrigens 0<i<p) ist, enthält die Primfaktorzerlegung von p! den Faktor p, die von i!(p-i!) aber nicht.
Da die Zerlegung eindeutig ist (Hauptsatz der Arithmetik), gilt [mm] p|\vektor{p\\i}.
[/mm]
Das ist nun genau Teufels Argumentation, nur anders zusammengefasst.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:54 So 19.08.2012 | | Autor: | Blake512 |
Zum Abschluss noch ein Beispiel:
[mm] p|\vektor{p \\ i} [/mm] wobei p=23 und i=5
[mm] \bruch{23!}{5!*(23-5)!} [/mm] = 33649
und [mm] \bruch{33649}{23} [/mm] = 1463
Danke auch Dir reverend!
|
|
|
|
