Periodizität einer Folge?
Ist die Folge aus a²+a mit a Element N modulo p für jedes p irgendwann periodisch?
2 Antworten
Sorry. Ich weiß nicht genau, ob ich richtig verstanden habe, um welche Folge es geht.
Um solch eine rekursive Folge...?
Und was ist mit „a Element N modulo p“ gemeint? Ist mit „N modulo p“ vielleicht der Restklassenring ℤₚ gemeint?
Dann wird die Folge natürlich periodisch sein, da aₙ höchstens p verschiedene Werte annehmen kann. Spätestens nach p Schritten hat man da also einen Wert, den man zuvor auch schon hatte. Und da das nächste Glied nur vom Glied direkt davor abhängt, erhält man dann ab diesem gleichen Glied wieder die gleichen nächsten Werte wie zuvor.
============
Oder meinst du die Folge...?
Diese ist periodisch, da...
... ist und (n mod p) sich periodisch mit Periode p wiederholt.
------------
Denn: Bedenke, dass im Restklassenring ℤₚ allgemein...
...ist. Damit ist dann im konkreten Fall...
------------
Die Folge ist also periodisch mit Periode p (oder vielleicht einer kleineren Periodenlänge, die ein Teiler von p ist, wenn p keine Primzahl ist).
Ah, ok, also die zweite Möglichkeit in meiner Antwort.
Moment. Da ergänze ich gleich noch eine Begründung, warum diese Folge periodisch ist oder nicht.
Die Begründung steht jetzt darunter.
Allgemein kann man so auch begründen, dass für jedes Polynom q und jede positive ganze Zahl p die durch...
aₙ = q(n) mod p
... gegebene Folge periodisch ist.
😉
Sie ist periodisch und die Periodenlänge ist p (oder ein Teiler von p).
Es ist a^2 + a kongruent zu (a+p)^2 + (a+p) zum Modul p.
Dazu muss man beweisen, dass
((a+p)^2 + (a+p)) - (a^2 - a) durch p teilbar ist.
Und das ist wirklich nicht schwierig.
Also: Wir haben eine Folge, die sich zusammensetzt aus a²+a, a1=1²+1, a2=2²+2, a3=3²+3... ist diese Folge immer irgendwann periodisch wenn man sie modulo p betrachtet und wenn ja, wieso?