Periodische Folgen < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 19:37 Mo 11.01.2010 | | Autor: | pitmat |
| Aufgabe | | Man soll zeigen: Ist p prim, dann ist ([n] mod p hoch n) n aus N periodisch und die Periodenlänge ist p(p-1). |
Ich hab mich erst geirrt und hab gedacht, ich kann das so zeigen:
Periodenlänge ist [n]p hoch n = [n + k]p hoch n + k für alle n aus N und k ist das kleinste k.
1) man soll zeigen, dass die Periodenlänge k ein Vielfaches von p ist.
Da dachte ich:
[n + k]p hoch n + k = [n + x*p]p hoch n + x*p = [n]p hoch n + x*p = [n]p hoch n * [n]p hoch x*p
Wie zeigt man aber jetzt, dass [n]p hoch x*p = [1]p ? Ich dachte erst mit Fermat, aber das geht ja nicht. Hat wer einen Tipp?
Und meine 2. Frage: Wie kann man zeigen, dass das überhaupt periodisch ist?
(Mein Problem: Ich kann zeitlich nicht zu den Mathevorlesungen gehen, mach die Übungszettel allein für mich (brauch keinen Schein mehr, aber muss das für die Prüfung können) und hab deswegen so viele Fragen ...)
#danke für eure Hilfe, ich find das super, wie hilfsbereit ihr hier seid! :)
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 20:06 Mo 11.01.2010 | | Autor: | Niladhoc |
Hallo,
stimmt die Aufgabe so wie sie da steht, oder steh ich auf dem Schlauch?
ist p>1, dann ist doch [mm] p^n [/mm] stets größer als n und somit ist n mod [mm] p^n [/mm] =n, was nicht periodisch ist. (n mod [mm] p)^n [/mm] ist glaube ich auch nicht periodisch [mm] (=n^{n+kp} k\in \IN).
[/mm]
lg
|
|
|
| |
|
| Status: |
(Frage) beantwortet  | | Datum: | 20:25 Mo 11.01.2010 | | Autor: | pitmat |
| Aufgabe | Aufgabe umgeformt:
[mm] n^n [/mm] mod p = (n + [mm] k)^n [/mm] + k mod p
bzw. zu zeigen ist:
[mm] (n^n [/mm] mod p)n aus N ist periodisch |
Ich glaube, du hast das anders verstanden, oder steh ich nun auf dem Schlauch?
|
|
|
| |
|
Hallo pitmat,
so kann die Aufgabe auch noch nicht stimmen. Wenn ich mal vom Ergebnis her rekonstruiere, sollst Du wahrscheinlich folgendes zeigen:
Sei p prim und n beliebig, aber nicht [mm] n\equiv 0\mod{p} [/mm] (will heißen, n ist kein Vielfaches von p).
Zeige, dass [mm] n^k\mod{\blue{p^2}} [/mm] periodisch in k ist und die Periodenlänge p(p-1) beträgt.
Es genügt dafür zu zeigen, dass erstens [mm] n^{p(p-1)} \equiv 1\mod{p^2} [/mm] und zweitens, dass es mindestens ein n gibt, für das die Periodenlänge nicht kleiner ist.
"Zweitens" ist dabei der schwierigere Teil...
lg
reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:32 Mo 11.01.2010 | | Autor: | pitmat |
hm, das sieht gänzlich anders aus - ich glaub, ich frag mal wen aus dem Kurs, der weiß, ob es korrigiert so richtig ist! und melde mich evtl. später noch mal ... also die nächsten Tage
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:24 Mo 11.01.2010 | | Autor: | reverend |
Hallo pitmat,
ich verstehe Deine Notation nicht, also auch nicht, was da zu zeigen ist. Stimmt die Interpretation von Niladhoc? Dann sehe ich da das gleiche Problem.
Nebenbei: [mm] a^b [/mm] schreibt man hier einfach a^{b}. Wenn der Exponent nur ein Zeichen lang ist, kannst Du die geschweiften Klammern auch weglassen, sonst nicht.
Ansonsten findest Du Eingabehilfen für den Formelsatz unter dem Eingabefenster. Unter Umständen musst du vorher noch das blaue [+] am Ende der ersten Zeile nach dem Eingabefenster anklicken. Der Formeleditor ist ziemlich komfortabel und basiert auf der LaTeX-Syntax.
lg
reverend
|
|
|
| |
|
| Status: |
(Frage) reagiert/warte auf Reaktion | | Datum: | 21:04 Mo 11.01.2010 | | Autor: | pitmat |
| Aufgabe | Noch ein Versuch:
(n mod [mm] p)^n [/mm] = ([n + k] mod [mm] p)^{n + k}
[/mm]
Folge: (( n mod [mm] p)^n)n [/mm] aus N |
Ich hoffe, jetzt ist es klar? Anders kann ich es nicht mehr schreiben!
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:11 Mo 11.01.2010 | | Autor: | reverend |
OK. so ist es lesbar, aber nicht lösbar.
Siehe meinen Beitrag oben, "Aufgabenstellung korrigiert". Ohne das [mm] \blue{p^2} [/mm] macht die Periodenlänge doch keinen Sinn.
Grüße
rev
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 21:13 Mo 11.01.2010 | | Autor: | pitmat |
| Aufgabe | | Wir kann ich zeigen, dass es für alle Elemente aus Z/p ohne [0]p ein a gibt, so dass [mm] n^a [/mm] mod p = 1 mod p? |
Das würde mir auch prima helfen! :)
|
|
|
| |
|
Hallo nochmal,
das ist eine andere Frage:
Die einfachste Möglichkeit ist der Beweis für den "kleinen Fermat". Den habt Ihr sicher in der Vorlesung gehabt, sonst ist auch der Beweis leicht zu googeln.
Noch einfacher ist es, wenn Ihr "erzeugende Elemente" hattet...
lg
rev
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 21:21 Mo 11.01.2010 | | Autor: | pitmat |
aber dann müsste ja jedes x mod p aus Z/p ein erzeugendes Element von Z/p ohne die 0 sein - ist das denn so?
|
|
|
| |
|
Ja, so ist es.
Oops. Überreaktion.
Nein, so ist es nicht! Aber es gibt in jedem primen Restklassenring erzeugende Elemente. Für p=7 ist z.B. die 3 ein solches, aber die 2 nicht.
Sorry. So einfach ist es dann doch nicht - weißt Du denn noch mehr über erzeugende Elemente, oder nur wie sie definiert sind und dass es sie gibt/geben kann?
Grüße
rev
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 21:36 Mo 11.01.2010 | | Autor: | pitmat |
nee, mehr weiß ich da leider nicht :(
aber wenn die Aufgabenstellung eh falsch ist, kann ich das sowieso vielleicht gar nicht brauchen und muss das anders lösen. oder gibt es noch was, was man darüber wissen muss und wodurch man das lösen kann?
|
|
|
| |
|
Hi,
falls das der Tipp zur Aufgabe war, sehe ich noch nicht, wozu er nötig ist. Den kleinen Fermat darfst du doch sicher auch sonst benutzen, oder? Interessanter ist hier aber seine Ausweitung, der sog. Euler-Fermat (hatten wir doch heute auch schon...)
Viel Erfolg erstmal bei der Klärung der Aufgabe.
Ciao,
reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:53 Mo 11.01.2010 | | Autor: | pitmat |
nee, zu der Frage war ich selbst gekommen. Aber mit der vermutlich falschen Aufgabenstellung. Insofern ist es wohl eh falsch. Ich meld mich ggf. noch mal, wenn es mit der neuen Aufgabenstellung nicht klappt! danke bisher für deine Hilfe!
|
|
|
|
