mod p < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | | Sei p eine Primzahl, und sei [mm] a\not=0 [/mm] mod p und [mm] a\not=1 [/mm] mod p . Beweisen Sie, dass [mm] 1+a+a^2+...+a^{p-2}=0 [/mm] mod p. |
Hi,
also ich habe dies jetzt für mehrere Beispiele ausprobiert und es funktioniert (offensichtlich).
Offenbar ist die Summe aller Potenzen von a bis [mm] a^{p-2} [/mm] durch p teilbar. Ich kann diese Summe also schreiben als k*p, wobei k irgendein ganzzahliger Faktor ist. Weiterhin weiß ich, dass p alle Zahlen ab a-2 teilt, wobei a maximal (p-1) sein kann.
Wie kann ich dies jetzt nutzen um etwas für die Summe zu beweisen ?
Lg
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 17:54 Mi 18.11.2009 | | Autor: | abakus |
> Sei p eine Primzahl, und sei [mm]a\not=0[/mm] mod p und [mm]a\not=1[/mm] mod
> p . Beweisen Sie, dass [mm]1+a+a^2+...+a^{p-2}=0[/mm] mod p.
> Hi,
>
> also ich habe dies jetzt für mehrere Beispiele ausprobiert
> und es funktioniert (offensichtlich).
> Offenbar ist die Summe aller Potenzen von a bis [mm]a^{p-2}[/mm]
> durch p teilbar. Ich kann diese Summe also schreiben als
> k*p, wobei k irgendein ganzzahliger Faktor ist. Weiterhin
> weiß ich, dass p alle Zahlen ab a-2 teilt, wobei a maximal
> (p-1) sein kann.
>
> Wie kann ich dies jetzt nutzen um etwas für die Summe zu
> beweisen ?
>
> Lg
Hallo, nur zwei Tipps:
[mm] 1+a+a^2+...+a^{p-2} [/mm] lässt sich mit der Summenformel der geometrischen Reihe als Qotient zweier Terme schreiben. Vielleicht hilft es.
Außerdem lassen die insgesamt (p-1) Summanden alle einen anderen Rest bei Teilung durch p (wenn nicht, gäbe es zwei Potenzen [mm] a^c [/mm] und [mm] a^d [/mm] mit gleichem Rest, deren Dfferenz dann durch p teilbar wäre. Welche Konsequenz hätte das?)
Gruß Abakus
EDIT: Ich muss mich im zweiten Teil korrigieren. Es müssen nicht alle Reste auiftreten. Sobald einmal der Rest 1 aufgetreten ist, ist die Restefolge periodisch, wobei die Periodenlänge ein Teiler von p-1 ist.
Gruß Abakus
|
|
|
| |
|
hi,
okay, also dann kann ich dies umschreiben als: [mm] \bruch{1-a^{p-1}}{1-a}. [/mm] Die Konsequenz aus deinem zweiten Tipp kommt mir noch nicht ganz in den kopf.
Würde das dann nicht der Aufgabenstellung widersprechen, wenn die Differenz durch p teilbar wäre, weil a und a-1 ja teilerfremd zu p sein sollen ?
Lg
|
|
|
| |
|
Hallo nochmal,
> okay, also dann kann ich dies umschreiben als:
> [mm]\bruch{1-a^{p-1}}{1-a}.[/mm]
Ja, genau. Oder vielleicht besser [mm] \bruch{a^{p-1}-1}{a-1}, [/mm] was ja das gleiche ist.
Die Aufgabenstellung behauptet ja nun, dass [mm] \bruch{a^{p-1}-1}{a-1}\equiv 0\mod{p} [/mm] ist.
Ich behaupte, dass dann auch [mm] a^{p-1}-1\equiv 0\mod{p} [/mm] sein muss.
Oder anders gesagt: [mm] a^{p-1}\equiv 1\mod{p}
[/mm]
Das sollte Dir bekannt vorkommen.
> Die Konsequenz aus deinem zweiten
> Tipp kommt mir noch nicht ganz in den kopf.
> Würde das dann nicht der Aufgabenstellung widersprechen,
> wenn die Differenz durch p teilbar wäre, weil a und a-1 ja
> teilerfremd zu p sein sollen ?
Nein, warum? Nehmen wir c<d an, dann folgt doch, dass [mm] (a^{d-c}-1) [/mm] durch p teilbar ist.
Im Moment sehe ich aber auch gerade nicht, wie dieser Tipp Dich zur Lösung führt, aber das kann einfach mein eigener Tunnelblick sein.
edit: Tunnelblick mit geschlossenen Augen und Augenklappe. Der Tipp ist natürlich gut. Man müsste sich dann nur noch Gedanken über Summen der Art [mm] \blue{\summe_{k=1}^{n}k} [/mm] machen...
Grüße
reverend
|
|
|
| |
|
> Hallo nochmal,
>
> > okay, also dann kann ich dies umschreiben als:
> > [mm]\bruch{1-a^{p-1}}{1-a}.[/mm]
>
> Ja, genau. Oder vielleicht besser [mm]\bruch{a^{p-1}-1}{a-1},[/mm]
> was ja das gleiche ist.
>
> Die Aufgabenstellung behauptet ja nun, dass
> [mm]\bruch{a^{p-1}-1}{a-1}\equiv 0\mod{p}[/mm] ist.
>
> Ich behaupte, dass dann auch [mm]a^{p-1}-1\equiv 0\mod{p}[/mm] sein
> muss.
Genau hier weiß ich nicht genau wie ich das zeigen kann.
Edit: Also ich kann die Kongruenz mit a-1=a-1 mod p multiplizieren um das von dir genannte zu erhalten. Denn jede Zahl a = a mod m ! Reicht es danach den kleinen fermat'schen Satz zu beweisen ?
> Oder anders gesagt: [mm]a^{p-1}\equiv 1\mod{p}[/mm]
>
> Das sollte Dir bekannt vorkommen.
Das ist der kleine Fermat'sche Satz, den wir auch in der Vorlesung bewiesen haben.
> > Die Konsequenz aus deinem zweiten
> > Tipp kommt mir noch nicht ganz in den kopf.
> > Würde das dann nicht der Aufgabenstellung widersprechen,
> > wenn die Differenz durch p teilbar wäre, weil a und a-1 ja
> > teilerfremd zu p sein sollen ?
>
> Nein, warum? Nehmen wir c<d an, dann folgt doch, dass
> [mm](a^{d-c}-1)[/mm] durch p teilbar ist.
> Im Moment sehe ich aber auch gerade nicht, wie dieser Tipp
> Dich zur Lösung führt, aber das kann einfach mein eigener
> Tunnelblick sein.
>
> edit: Tunnelblick mit geschlossenen Augen und Augenklappe.
> Der Tipp ist natürlich gut. Man müsste sich dann nur noch
> Gedanken über Summen der Art [mm]\blue{\summe_{k=1}^{n}k}[/mm]
> machen...
Dein Tunnelblick ist mein Tunnelblick. Diesen Tipp verstehe ich auch nach gut 1,5 stunden noch nicht...
> Grüße
> reverend
Ich fühle mich im Mathe-Studium manchmal wie der erste Mensch...
Lg,
exeqter
|
|
|
| |
|
Hallo exeqter,
pardon übrigens für die stete Kleinschreibung, aber ich kann mir nicht richtig die Groß-/Klein-Verteilung merken. Zu faul...
> > Ich behaupte, dass dann auch [mm]a^{p-1}-1\equiv 0\mod{p}[/mm] sein
> > muss.
>
> Genau hier weiß ich nicht genau wie ich das zeigen kann.
>
> Edit: Also ich kann die Kongruenz mit a-1=a-1 mod p
> multiplizieren um das von dir genannte zu erhalten. Denn
> jede Zahl a = a mod m !
Ich meine ja, dass dafür a-1 nicht [mm] 0\mod{p} [/mm] sein darf, aber das ist ja auch ausgeschlossen. Jedefalls ist es sonst nicht notwendig äquivalent, bzw. man muss sich über die Richtung der Folgerung Gedanken machen: Zwar ist [mm] 30\equiv 0\mod{5}, [/mm] aber aus der [mm] \tfrac{30}{15} \equiv 0\mod{5} [/mm] hätten wir das schon deswegen nicht folgern können, weil die Äquivalenz nicht stimmt.
Hmmm. Trotzdem falsch überlegt. Wenn eine wahre Äquivalenz gegeben ist wie [mm] \tfrac{75}{15} \equiv 0\mod{5}, [/mm] dann gilt sicher auch [mm] 75\equiv 0\mod{5}.
[/mm]
Das war noch 'ne Denkblockade.
> Reicht es danach den kleinen fermat'schen Satz zu beweisen ?
>
> > Oder anders gesagt: [mm]a^{p-1}\equiv 1\mod{p}[/mm]
> >
> > Das sollte Dir bekannt vorkommen.
>
> Das ist der kleine Fermat'sche Satz, den wir auch in der
> Vorlesung bewiesen haben.
Dann brauchst Du ihn doch nicht mehr z beweisen, sondern kannst ihn einfach benutzen. Aufgabe fertig.
> Dein Tunnelblick ist mein Tunnelblick. Diesen Tipp verstehe
> ich auch nach gut 1,5 stunden noch nicht...
Ich habe gerade ein paar Stunden ganz andere Dinge gemacht. Gerade komme ich nicht mehr drauf, warum der zweite Tipp von abakus ein Problem aufwirft. Wenn aber alle Reste verschieden sind (was sie ja sind), dann braucht man den kleinen Fermatschen Satz nicht noch zusätzlich - den beweist man ja gerade damit.
> Ich fühle mich im Mathe-Studium manchmal wie der erste
> Mensch...
Du bist im Mathestudium der erste Mensch.
Das Riesengebäude der Mathematik ist von vielen Tausenden vor Dir gebaut worden. Aber nur, wenn Du es selbst komplett und selbständig nachbauen kannst, darfst Du darin wohnen und auch Neues bauen. Alle anderen dürfen nur kommen und staunen (ich zum Beispiel, aber ich habe auch Eintritt bezahlt).
> Lg,
>
> exeqter
Alles Gute,
reverend
|
|
|
| |
|
Hallo exeqter,
wenn Du den Tipp von abakus verfolgst (er führt zum Ziel), gibt es noch eine Hürde, die Multiplikation mit (a-1). Du musst (und kannst) sicherstellen, dass [mm] a-1\not= 0\mod{p} [/mm] ist. Außerdem brauchst Du noch den "kleinen Fermat". Dann bist Du schnell fertig.
Grüße
reverend
|
|
|
|
