Satz von Euler anwenden

31.08.2017, 14:24

Stevenson

Satz von Euler anwenden

Meine Frage:
Hey Leute,

der Satz von Euler ist ja $\begin{eqnarray*} a^{\varphi (m)} \equiv 1\ (mod\ m) \end{eqnarray*}$ , wenn ggT(a,m) = 1 bzw., mit Umformungen $\begin{eqnarray*} a^{k\varphi (m)+b} \equiv a^b\ (mod\ m) \end{eqnarray*}$

Meine Ideen:
Aber ich verstehe nicht ganz wie ich das anwende... Damit kann ich ja die Restklasse einer Potenz modulo m bestimmen. Nur wie? Ich sauge mir mal etwas aus den Fingern:

$\begin{eqnarray*} 6^{524}\ mod\ 8 \end{eqnarray*}$

Wie gehe ich vor? Bin dankbar für jede Hilfe smile

EDIT: Das Beispiel ist wohl schlecht gewählt, oder? Da ggT(6,8) > 1

31.08.2017, 16:52

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Stevenson
EDIT: Das Beispiel ist wohl schlecht gewählt, oder? Da ggT(6,8) > 1

Gut erkannt ... das ist kein Fall von Euler-Fermat, sondern einfach so berechenbar:

$\begin{align*} 6^{524} = 2^{524}\cdot 3^{524}\equiv 0\bmod 8 \end{align*}$ ,

da offenkundig $\begin{align*} 2^{524} \end{align*}$ durch $\begin{align*} 2^3=8 \end{align*}$ teilbar ist. Aber schauen wir uns nur den zweiten Faktor an: Wegen $\begin{align*} \varphi(8)=4 \end{align*}$ folgt

$\begin{align*} 3^{524} = 3^{131\cdot 4}\equiv 1\bmod 8 \end{align*}$ .

Bei zusammengesetzten Modulen ist übrigens in vielen Fällen die Carmichael-Funktion die feinere Klinge, so auch hier: Statt $\begin{align*} \varphi(8)=4 \end{align*}$ arbeitet sie mit $\begin{align*} \lambda(8)=2 \end{align*}$ und liefert die Aussage $\begin{align*} a^2\equiv 1\bmod 8 \end{align*}$ für alle zu 8 teilerfremden Zahlen (was nebenbei bemerkt just die ungeraden Zahlen sind).

Neue Frage »

Antworten »

Satz von Euler anwenden

Verwandte Themen