Eulerische phi-Funktion

11.07.2010, 14:36

alu

Eulerische phi-Funktion

Meine Frage:
Folgendes Problem:

Berechnen Sie bitte: $\begin{eqnarray*} 13^{13^{12}} mod 43 \end{eqnarray*}$

Meine Ideen:
Mein Lösungsvorschlag wäre:

Eulerische phi-Funktion von 43 ist 42
ggT (13,42)=1 und $\begin{eqnarray*} 13^{12} mod 42 ist b \end{eqnarray*}$
daraus folgt $\begin{eqnarray*} 13^{13^{12}} mod 43 gleich 13^{b} \end{eqnarray*}$

Berechnung von b mit dem kleinen Satz von Fermat:

aus ggT(13,42)=1 folgt $\begin{eqnarray*} 13^{12} mod 43 gleich 1 \end{eqnarray*}$ , woraus folgt b=1

Einsetzen in die obere Gleichung gibt $\begin{eqnarray*} 13^{1} = 1 \end{eqnarray*}$

Damit ist 13 die Lösung von $\begin{eqnarray*} 13^{13^{12}} mod 43 \end{eqnarray*}$

Eine Frage habe ich allerdings noch:
Wie genau berechne ich die Eulerische phi-Funktion von 42 (ohne in einer Tabelle nachzusehen)?

Ich kann 42 leider nicht in eine Form $\begin{eqnarray*} a^{b} \cdot c^{d} \end{eqnarray*}$ bringen. Könnte mir hier bitte jemand weiterhelfen?

11.07.2010, 14:41

Auf diesen Beitrag antworten »

RE: Eulerische phi-Funktion
$\begin{eqnarray*} 42 = 2\cdot 3\cdot 7 \end{eqnarray*}$ , also ist

$\begin{eqnarray*} \varphi(42) = (2-1)\cdot (3-1)\cdot (7-1) = 12 \end{eqnarray*}$ .

Eine Frage: Wenn du das nicht weißt, wie konntest du das hier

Zitat:

Original von alu
aus ggT(13,42)=1 folgt $\begin{eqnarray*} 13^{12} mod 43 gleich 1 \end{eqnarray*}$ , woraus folgt b=1

berechnen? verwirrt

12.07.2010, 10:09

system-agent

Auf diesen Beitrag antworten »

Ich habe das mal verschoben, da das eher keine Analysis ist Augenzwinkern

Neue Frage »

Antworten »

Eulerische phi-Funktion

Verwandte Themen