Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Rest von hohen Potenzen bestimmen

Rest von hohen Potenzen bestimmen

Universität / Fachhochschule

Algebraische Zahlentheorie

Tags: Algebraische Zahlentheorie, modulo, Potenz, restklassen

rancidrufus aktiv_icon

10:15 Uhr, 22.10.2017

Hallo allerseits,

mich ärgert eine Übungsaufgabe, in der folgende Mengen zu bestimmen sind:

{x

aus Zmodulo29Z mit

x^{86} = 6}

{x

aus

Z

mit

x^{39} = 3

modulo

13}

Ich kam leider noch nicht sonderlich weit;

x^{86} = x^{64} \cdot x^{16} \cdot x^{4} \cdot x^{2}

Und

x^{39} = {(x^{12})}^{3} \cdot x^{3},

wobei

x^{12}

nach Fermat gleich 1 modulo

13

ist, falls

x

kein Teiler von

13

.

Kann wer helfen??

Hierzu passend bei OnlineMathe:
Potenzregeln (Mathematischer Grundbegriff)
Rechnen mit Potenzen

michaL aktiv_icon

11:02 Uhr, 22.10.2017

Hallo,

man rechnet leicht nach, dass

ℤ / 29 ℤ \ {0}

und

ℤ / 13 ℤ \ {0}

bzgl. der Multiplikation abelsche Gruppen sind.

Wenn du sogar schon weißt, dass es sich um bei beiden um die Einheitengruppen der zugehörigen Körper handelt (und diese als solche sogar zyklisch sind), dann brauchst du den Nachweis der Gruppeneigenschaften nicht mal zu führen.

Insbesondere gelten also gemäß Fermat (vielleicht habt ihr auch nur den zur Verfügung?!):

x^{28} \equiv 1

mod 29 bzw.

x^{12} \equiv 1

mod 13

Damit lassen sich die Exponenten stark reduzieren.
Der Rest ist ein Suchen, was mit einer Tabellenkalkulation am einfachsten geht.

Alles klar?

Mfg Michael