Restklassen < Gruppe, Ring, Körper < Algebra < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
Status: |
(Frage) beantwortet | Datum: | 15:15 Sa 04.10.2008 | Autor: | jokerose |
Aufgabe | Sei p eine Primzahl. Zeige:
a) [mm] \vektor{p \\ k} \equiv [/mm] mod p , für 0 < k < p
b) für m [mm] \ge [/mm] 1 gilt (1 + [mm] x)^{p^m} [/mm] = 1 + [mm] x^{p^m} [/mm] in [mm] \IZ/p[x]
[/mm]
c) für m [mm] \ge [/mm] 1 und 0 < j < [mm] p^m [/mm] gilt:
[mm] \vektor{p^m \\ j} \equiv [/mm] 0 mod p |
Bei a) habe ich mal so begonnen:
[mm] \vektor{p \\ k} [/mm] = [mm] \bruch{p!}{k! * (p-k)!} [/mm] = [mm] \bruch{p * (p-1) * ... * (p-k+1)}{k!}.
[/mm]
Doch danach wusste ich nicht mehr wie ich weiterfahren soll.
Sehe gerade nicht weiter...!
Bei b) habe ich so umgeformt:
(1 + [mm] x)^{p^m} [/mm] = [mm] \summe_{k=0}^{p^m} \vektor{p^m \\ k} x^k [/mm] = 1 + [mm] \summe_{k=1}^{p^m} \vektor{p^m \\ k} x^k
[/mm]
und mit der Behauptung von Aufgabe c) folgt dann:
= 1 + 0 + 0 + ... + 0 + [mm] \vektor{p^m \\ p^m} x^{p^m} [/mm] = 1 + [mm] x^{p^m}.
[/mm]
Ist dies korrekt?
Dann müsste ich also einfach noch die Behauptung bei c) beweisen.
Könnte ich da dann ähnlich vorgehen wie bei a)?
|
|
|
|
Status: |
(Antwort) fertig | Datum: | 16:23 Sa 04.10.2008 | Autor: | andreas |
hi
> Sei p eine Primzahl. Zeige:
>
> a) [mm]\vektor{p \\ k} \equiv[/mm] mod p , für 0 < k < p
>
> b) für m [mm]\ge[/mm] 1 gilt (1 + [mm]x)^{p^m}[/mm] = 1 + [mm]x^{p^m}[/mm] in
> [mm]\IZ/p[x][/mm]
>
> c) für m [mm]\ge[/mm] 1 und 0 < j < [mm]p^m[/mm] gilt:
>
> [mm]\vektor{p^m \\ j} \equiv[/mm] 0 mod p
> Bei a) habe ich mal so begonnen:
>
> [mm]\vektor{p \\ k}[/mm] = [mm]\bruch{p!}{k! * (p-k)!}[/mm] = [mm]\bruch{p * (p-1) * ... * (p-k+1)}{k!}.[/mm]
>
> Doch danach wusste ich nicht mehr wie ich weiterfahren
> soll.
> Sehe gerade nicht weiter...!
teilt $p$ den zähler? teilt $p$ auch den nenner (beachte $0 < k <p$, $p$ prim)? teilt $p$ dann den quotienten?
> Bei b) habe ich so umgeformt:
>
> (1 + [mm]x)^{p^m}[/mm] = [mm]\summe_{k=0}^{p^m} \vektor{p^m \\ k} x^k[/mm] =
> 1 + [mm]\summe_{k=1}^{p^m} \vektor{p^m \\ k} x^k[/mm]
>
> und mit der Behauptung von Aufgabe c) folgt dann:
>
> = 1 + 0 + 0 + ... + 0 + [mm]\vektor{p^m \\ p^m} x^{p^m}[/mm] = 1 +
> [mm]x^{p^m}.[/mm]
>
> Ist dies korrekt?
ja, wenn man c) gezeigt hat, ist man dann fertig. ich befürchte aber, es ist nicht ganz so einfach c) direkt zu zeigen (möglicherweise geht das schon, wenn man sich mal ein paar beispiele anschaut und dann eine idee hat, wie man zeigen kann, dass der $p$-exponent des zählers größer ist, als der des nenners). ich kann mir hier aber auch vorstellen, dass man teil b) mit hilfe von teil a) und vollständiger induktion zeigen kann. dann könnte man mit einer ähnlichen rechnung wie bei dir daraus c) folgern. allerdings habe ich das noch nicht durchgerechnet - nur mal so als anstoß.
grüße
andreas
|
|
|
|
|
Status: |
(Frage) beantwortet | Datum: | 17:42 Sa 04.10.2008 | Autor: | jokerose |
Hallo
> teilt [mm]p[/mm] den zähler? teilt [mm]p[/mm] auch den nenner (beachte [mm]0 < k
> [mm]p[/mm] prim)? teilt [mm]p[/mm] dann den quotienten?
>
Ja der Zähler teilt p. Und der Nenner sollte p dann eigentlich nicht teilen. Doch wie kann man dies veranschaulichen?
>
> > Bei b) habe ich so umgeformt:
> >
> > (1 + [mm]x)^{p^m}[/mm] = [mm]\summe_{k=0}^{p^m} \vektor{p^m \\ k} x^k[/mm] =
> > 1 + [mm]\summe_{k=1}^{p^m} \vektor{p^m \\ k} x^k[/mm]
> >
> > und mit der Behauptung von Aufgabe c) folgt dann:
> >
> > = 1 + 0 + 0 + ... + 0 + [mm]\vektor{p^m \\ p^m} x^{p^m}[/mm] = 1 +
> > [mm]x^{p^m}.[/mm]
> >
> > Ist dies korrekt?
>
> ja, wenn man c) gezeigt hat, ist man dann fertig. ich
> befürchte aber, es ist nicht ganz so einfach c) direkt zu
> zeigen (möglicherweise geht das schon, wenn man sich mal
> ein paar beispiele anschaut und dann eine idee hat, wie man
> zeigen kann, dass der [mm]p[/mm]-exponent des zählers größer ist,
> als der des nenners). ich kann mir hier aber auch
> vorstellen, dass man teil b) mit hilfe von teil a) und
> vollständiger induktion zeigen kann. dann könnte man mit
> einer ähnlichen rechnung wie bei dir daraus c) folgern.
> allerdings habe ich das noch nicht durchgerechnet - nur mal
> so als anstoß.
>
Die Idee mit der vollständigen Induktion finde ich nicht schlecht.
Für m = 1 ist der Fall trivial. (mit Hilfe von a)).
Dann für m+ 1:
[mm] (1+x)^{p^{m+1}} [/mm] = [mm] \summe_{k=0}^{p^{m+1}}\vektor{p^{m+1} \\ k}x^{p^{k}} [/mm] =1 + [mm] \summe_{k=1}^{p^{m+1}}\vektor{p^{m+1} \\ k}x^{p^{k}}...!
[/mm]
Eventuell könnte der "kleiner Fermatescher Satz" weiterhelfen:
Sei p eine Primzahl, dann [mm] a^p [/mm] = a [mm] \forall [/mm] a [mm] \in \IZ/p.
[/mm]
Oder wie kann man sonst da weitermachen?
|
|
|
|
|
Status: |
(Antwort) fertig | Datum: | 18:05 Sa 04.10.2008 | Autor: | andreas |
hi
> > teilt [mm]p[/mm] den zähler? teilt [mm]p[/mm] auch den nenner (beachte [mm]0 < k
> > [mm]p[/mm] prim)? teilt [mm]p[/mm] dann den quotienten?
> >
>
> Ja der Zähler teilt p.
du meinst vermutlich $p$ teilt den zähler.
> Und der Nenner sollte p dann
> eigentlich nicht teilen. Doch wie kann man dies
> veranschaulichen?
wie groß sind den die faktoren, welche im nenner vorkommen? kann da irgendwo ein $p$ drinstecken?
> Die Idee mit der vollständigen Induktion finde ich nicht
> schlecht.
>
> Für m = 1 ist der Fall trivial. (mit Hilfe von a)).
ganz trivial ist das nicht. aber das folgt ziemlich schnell aus der a), da hast du recht.
> Dann für m+ 1:
> [mm](1+x)^{p^{m+1}}[/mm] = [mm]\summe_{k=0}^{p^{m+1}}\vektor{p^{m+1} \\ k}x^{p^{k}}[/mm]
> =1 + [mm]\summe_{k=1}^{p^{m+1}}\vektor{p^{m+1} \\ k}x^{p^{k}}...![/mm]
beachte $(1 + [mm] x)^{p^{m + 1}} [/mm] = [mm] \left[(1 + x)^{p^m}\right]^p$.
[/mm]
grüße
andreas
|
|
|
|
|
Status: |
(Frage) beantwortet | Datum: | 12:04 So 05.10.2008 | Autor: | jokerose |
Hallo
>
> > > teilt [mm]p[/mm] den zähler? teilt [mm]p[/mm] auch den nenner (beachte [mm]0 < k
> > > [mm]p[/mm] prim)? teilt [mm]p[/mm] dann den quotienten?
> > >
> >
> > Ja der Zähler teilt p.
>
> du meinst vermutlich [mm]p[/mm] teilt den zähler.
JA!
>
> > Und der Nenner sollte p dann
> > eigentlich nicht teilen. Doch wie kann man dies
> > veranschaulichen?
>
> wie groß sind den die faktoren, welche im nenner vorkommen?
> kann da irgendwo ein [mm]p[/mm] drinstecken?
>
>
Nein, da kann kein p drinstecken. Aber die einzelnen Faktoren können natürlich zusammen dann grösser als p sein. Wer oder was kann mir dann aber gewährleisten, dass p den Nenner nicht teilt?
Die anderen beiden Aufgaben habe ich dann mittlerweilen knacken können.
Nun habe ich aber noch hier ein kleines Problem:
Sei p weiterhin eine Primzahl.
Zeige: für m [mm] \ge [/mm] 1 und k mit ggT(p,k) = 1 gilt
p [mm] \not| \vektor{p^mk\\ p^m}.
[/mm]
Kann mir jemand da einen Gedankenanstoss geben?
|
|
|
|
|
Status: |
(Antwort) fertig | Datum: | 16:04 So 05.10.2008 | Autor: | felixf |
Hallo
> > wie groß sind den die faktoren, welche im nenner vorkommen?
> > kann da irgendwo ein [mm]p[/mm] drinstecken?
> >
> >
>
> Nein, da kann kein p drinstecken. Aber die einzelnen
> Faktoren können natürlich zusammen dann grösser als p sein.
> Wer oder was kann mir dann aber gewährleisten, dass p den
> Nenner nicht teilt?
Wie ist denn eine Primzahl definiert? Das ist doch enie Zahl $p$ so, dass fuer jede Zahlen $a, b$ mit $p$ teilt $a * b$ gilt, dass $p$ bereits entweder $a$ oder $b$ teilt.
Wenn du jetzt also ein Produkt von vielen Zahlen hast, wobei jeder Faktor von $p$ nicht geteilt wird, kann das Produkt dann durch $p$ geteilt werden?
> Die anderen beiden Aufgaben habe ich dann mittlerweilen
> knacken können.
>
> Nun habe ich aber noch hier ein kleines Problem:
>
> Sei p weiterhin eine Primzahl.
> Zeige: für m [mm]\ge[/mm] 1 und k mit ggT(p,k) = 1 gilt
>
> p [mm]\not| \vektor{p^mk\\ p^m}.[/mm]
>
> Kann mir jemand da einen Gedankenanstoss geben?
Hier musst du zaehlen, wie oft $p$ im Nenner und im Zaehler vorkommt.
Machen wir das mal explizit fuer den Nenner; fuer den Zaehler geht es aehnlich.
Dazu benutzen wir folgenden Trick: sei $M$ eine Menge von ganzen Zahlen (ungleich 0) und sei [mm] $a_k$ [/mm] die Anzahl der Zahlen im $M$, die durch [mm] $p^k$ [/mm] geteilt wird, $k [mm] \in \IN$. [/mm] Dann ist die genaue Zahl der $p$, die [mm] $\prod_{m \in M} [/mm] m$ teilt, gerade [mm] $\sum_{k=1}^\infty a_k$.
[/mm]
(Ueberleg dir doch mal warum das so ist. Anleitung dazu: definiere [mm] $\tilde{a}_k$ [/mm] als die Anzahl der Zahlen im $M$, die durch [mm] $p^k$, [/mm] aber nicht durch [mm] $p^{k+1}$ [/mm] geteilt werden; dann ist [mm] $\tilde{a}_k [/mm] = [mm] a_k [/mm] - [mm] a_{k+1}$. [/mm] Weiter ist die Anzahl der $p$, die im Produkt vorkommt, ist [mm] $\sum_{k=1}^\infty [/mm] k [mm] \tilde{a}_k$. [/mm] Jetzt setz das doch mal zusammen.)
Jetzt haben wir ja, dass [mm] $(p^m)! [/mm] = [mm] \prod_{n \in \IN} [/mm] N$ ist mit $N = [mm] \{ 1, 2, 3, \dots, p^m \}$ [/mm] ist. Ist $k [mm] \le [/mm] m$, so wird ja jede [mm] $p^k$-te [/mm] Zahl in $N$ durch [mm] $p^k$ [/mm] geteilt; damit ist [mm] $a_k [/mm] = [mm] \frac{|N|}{p^k} [/mm] = [mm] p^{m - k}$ [/mm] (das Argument funktioniert im Zaehler fast genauso). Ist $k > m$, so sind alle Zahlen $< [mm] p^k$, [/mm] womit keine durch $N$ geteilt wird (das Argument funktioniert im Zaehler nicht, da musst du was tun). Damit ist [mm] $a_k [/mm] = 0$ fuer $k > m$.
Insgesamt wird der Nenner also [mm] $\sum_{k=1}^m p^{m-k}$ [/mm] mal durch $p$ geteilt.
So. Jetzt musst du das auch noch fuer den Zaehler nachrechnen; wenn genau das gleiche herauskommt, kuerzen sich alle $p$s aus dem Nenner mit denen aus dem Zaehler weg, und [mm] $\binom{p^m k}{p^m}$ [/mm] ist nicht durch $p$ teilbar.
LG Felix
|
|
|
|
|
Status: |
(Mitteilung) Reaktion unnötig | Datum: | 18:34 So 05.10.2008 | Autor: | jokerose |
Vielen Dank für die ausführliche Antwort. Ich muss mir dies nun mal in Ruhe durch den Kopf gehen lassen.
|
|
|
|
|
Status: |
(Antwort) fertig | Datum: | 13:01 So 05.10.2008 | Autor: | abakus |
> Sei p eine Primzahl. Zeige:
>
> a) [mm]\vektor{p \\ k} \equiv[/mm] mod p , für 0 < k < p
>
> b) für m [mm]\ge[/mm] 1 gilt (1 + [mm]x)^{p^m}[/mm] = 1 + [mm]x^{p^m}[/mm] in
> [mm]\IZ/p[x][/mm]
>
> c) für m [mm]\ge[/mm] 1 und 0 < j < [mm]p^m[/mm] gilt:
>
> [mm]\vektor{p^m \\ j} \equiv[/mm] 0 mod p
> Bei a) habe ich mal so begonnen:
>
> [mm]\vektor{p \\ k}[/mm] = [mm]\bruch{p!}{k! * (p-k)!}[/mm] = [mm]\bruch{p * (p-1) * ... * (p-k+1)}{k!}.[/mm]
>
> Doch danach wusste ich nicht mehr wie ich weiterfahren
> soll.
> Sehe gerade nicht weiter...!
Hallo,
unter k aufeinanderfolgenden Zahlen ist stets genau eine durch k teilbar. Damit kann man alle Nenner wegkürzen, weil im Zähler k aufeinander folgende Faktoren stehen.
Gruß
Abakus
>
> Bei b) habe ich so umgeformt:
>
> (1 + [mm]x)^{p^m}[/mm] = [mm]\summe_{k=0}^{p^m} \vektor{p^m \\ k} x^k[/mm] =
> 1 + [mm]\summe_{k=1}^{p^m} \vektor{p^m \\ k} x^k[/mm]
>
> und mit der Behauptung von Aufgabe c) folgt dann:
>
> = 1 + 0 + 0 + ... + 0 + [mm]\vektor{p^m \\ p^m} x^{p^m}[/mm] = 1 +
> [mm]x^{p^m}.[/mm]
>
> Ist dies korrekt?
> Dann müsste ich also einfach noch die Behauptung bei c)
> beweisen.
> Könnte ich da dann ähnlich vorgehen wie bei a)?
|
|
|
|
|
Status: |
(Frage) beantwortet | Datum: | 13:11 So 05.10.2008 | Autor: | jokerose |
Hallo
> >
> > [mm]\vektor{p \\ k}[/mm] = [mm]\bruch{p!}{k! * (p-k)!}[/mm] = [mm]\bruch{p * (p-1) * ... * (p-k+1)}{k!}.[/mm]
>
> >
> > Doch danach wusste ich nicht mehr wie ich weiterfahren
> > soll.
> > Sehe gerade nicht weiter...!
>
> Hallo,
> unter k aufeinanderfolgenden Zahlen ist stets genau eine
> durch k teilbar. Damit kann man alle Nenner wegkürzen, weil
> im Zähler k aufeinander folgende Faktoren stehen.
> Gruß
> Abakus
Also ich habe gerade nicht genau verstanden wie du das meinst, aber ich sehe auch denn Sinn nicht, was dies mit der Frage zu tun hat.
Es gilt ja zu zeigen, dass p den Nenner nicht teilt...!!!?
|
|
|
|
|
Hallo jokerose,
> Hallo
>
>
> > >
> > > [mm]\vektor{p \\ k}[/mm] = [mm]\bruch{p!}{k! * (p-k)!}[/mm] = [mm]\bruch{p * (p-1) * ... * (p-k+1)}{k!}.[/mm]
>
> >
> > >
> > > Doch danach wusste ich nicht mehr wie ich weiterfahren
> > > soll.
> > > Sehe gerade nicht weiter...!
> >
> > Hallo,
> > unter k aufeinanderfolgenden Zahlen ist stets genau eine
> > durch k teilbar. Damit kann man alle Nenner wegkürzen, weil
> > im Zähler k aufeinander folgende Faktoren stehen.
> > Gruß
> > Abakus
>
> Also ich habe gerade nicht genau verstanden wie du das
> meinst, aber ich sehe auch denn Sinn nicht, was dies mit
> der Frage zu tun hat.
> Es gilt ja zu zeigen, dass p den Nenner nicht teilt...!!!?
Es gilt doch für [mm] $p\in\mathbb{P}$:
[/mm]
[mm] $p\mid a\cdot{}b\Rightarrow (p\mid a\vee p\mid [/mm] b)$
Folglich äquivalent (Kontraposition)
[mm] $(p\not| [/mm] \ a \ [mm] \wedge [/mm] \ [mm] p\not| [/mm] \ [mm] b)\Rightarrow p\not| [/mm] \ [mm] a\cdot{}b$
[/mm]
Wenn $p$ also keinen der Faktoren teilt, kann es auch das Produkt nicht teilen
LG
schachuzipus
|
|
|
|
|
Status: |
(Frage) beantwortet | Datum: | 18:34 So 05.10.2008 | Autor: | jokerose |
Danke für die tolle Antwort. Jetzt ists völlig klar.
Sorry, sollte eigentlich kein Frageartikel sein...!
Weiss aber gerade nicht, wie ich dies rückgängig machen kann...
|
|
|
|