|
|
 | | From: | Gerhard J. Woeginger | | Subject: | [Math]#526: Periodisch | | Date: | 14 Jan 2005 11:08:38 GMT |
|
|
 | Bestimme alle natuerlichen Zahlen m>=2, fuer die gilt:
Fuer jede natuerliche Zahl x ist die Folge
x^1 mod m, x^2 mod m, x^3 mod m, ...
eine periodische Folge.
|
|
| | From: | Rainer aus dem Spring | | Subject: | Re: [Math]#526: Periodisch | | Date: | Sat, 15 Jan 2005 13:06:22 +0100 |
|
|
| Gerhard J. Woeginger wrote:
> Bestimme alle natuerlichen Zahlen m>=2, fuer die gilt:
>
> Fuer jede natuerliche Zahl x ist die Folge
>
> x^1 mod m, x^2 mod m, x^3 mod m, ...
>
> eine periodische Folge.
>
>
Die Periode soll mit dem ersten Glied beginnen?
Sonst ist es wohl etwas einfach :)
Rainer adS
|
|
| | From: | Jan Fricke | | Subject: | Re: [Math]#526: Periodisch | | Date: | Tue, 18 Jan 2005 10:43:38 +0100 |
|
|
| Gerhard J. Woeginger wrote:
> Bestimme alle natuerlichen Zahlen m>=2, fuer die gilt:
>
> Fuer jede natuerliche Zahl x ist die Folge
>
> x^1 mod m, x^2 mod m, x^3 mod m, ...
>
> eine periodische Folge.
>
>
Wie Rainer schon bemerkte, hängt die Lösung davon ab, wie man
"periodisch" versteht. Ich weise dann an den entsprechenden Stellen
darauf hin.
Als erstes bemerkt man, daß die obige Eigenschaft multiplikativ ist,
d.h. teilerfremde a und b haben die Eigenschaft genau dann, wenn a*b sie
hat. Also müssen nur noch Primzahlpotenzen für m untersucht werden.
Sei m=p^k.
- Falls p kein Teiler von x ist, so hat die Folge die Periode eulerphi(m).
- Ist p aber ein Teiler von x, so wird die Folge irgendwann konstant
Null. Sie ist also im weiteren Sinne periodisch, aber im engeren nur
dann, wenn schon x mod m = 0.
Also: Im weiteren Sinne erfüllen das alle Zahlen m, im engeren Sinne nur
die quadratfreien.
Viele Grüße Jan
|
|
|
