Frage zu Restklassen (Mathematik)

[Diarrhorus]

Hi,

Mir ist gerade zufällig aufgefallen das die Restklassen [a^3]_6 und [a]_6 identisch sind.
Mir gelingt es aber nicht das mathematisch zu beweisen :(. Kann mir da irgend jemand auf die Sprünge helfen?

[Tesseract]

es gilt doch sowieso allgemein (a^n)%b = a%b oder?

edit: nein, doch nicht. aber interessanterweise trifft das auf ziemlich viele zu.

[Diarrhorus]

Nein, z.B. ist (2^2)%5 != 2 % 5

EDIT: zu deinem EDIT: ich glaub das trifft immer dann zu wenn "n teilt b" gilt. Das ist jedenfalls meine Vermutung.

[Gnafoo]

http://de.wikipedia.org/wiki/Satz_von_Euler

Für n=6=3*2*1 gibt es 2 teilerfremde Reste modulo 6. Nämlich: 4 und 5. Dagegen fliegen 1, 2 und 3 raus, weil sie zu 6 nicht teilerfremd sind (die Primfaktorzerlegung hat gemeinsame Faktoren). Also gilt phi(6)=2.

Damit ist nach dem Eulerschen Satz:
a^phi(6)=a^2 = 1 mod 6

und a^3 = a*a^phi(6) = a*1 mod 6.

Ich hoffe mal ich habe nicht gerade irgendeinen Müll verzapft, was das mit der Teilerfremdheit oben angeht XD. Btw. das ist die Idee die hinter RSA steckt. Da wird bloß der Exponent, bei dem a wieder rauskommt in zwei Zahlen geteilt. Den Enkodierschlüssel und den Dekodierschlüssel ;).

Edit: zu beachten ist, dass der Satz nur gilt, wenn ggT(a,n)=1.

[Diarrhorus]

Vielen Dank erstmal, aber aufgrund der ggT Bedingung beweist das ja leider nicht wirklich was, oder?

[Gnafoo]

Hm naja für n=6 ist das leicht bewiesen. Einfach für jede Restklasse einmal zeigen und fertig. Ich vermute aber, dass deine Aussage im allgemeinen Fall (also für größere n) einfach nicht gilt.