Euler Phi Funktion

25.07.2016, 19:07

Jayky

Euler Phi Funktion

Meine Frage:
Ich habe ein Problem und komme da leider nicht weiter. Könnte mir vielleicht jemand helfen?

Es geht darum, welchen Rest $\begin{eqnarray*} 19^{96} \end{eqnarray*}$ bei der Division durch 72 hat.

Meine Ideen:
Ich bin nun mithilfe der eulerschen Formel dazu gekommen, dass $\begin{eqnarray*} 19^{96}\equiv 1 \end{eqnarray*}$ mod 72 ist und ich mich so nur noch um $\begin{eqnarray*} 19^{6} \end{eqnarray*}$ kümmern muss. Wie ich das nun allerdings vereinfache ist mir ein Rätsel unglücklich

Wäre froh, wenn mir jemand helfen könnte.

25.07.2016, 19:39

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Jayky
Es geht darum, welchen Rest $\begin{eqnarray*} 19^{96} \end{eqnarray*}$ bei der Division durch 72 hat.

[...]

Ich bin nun mithilfe der eulerschen Formel dazu gekommen, dass $\begin{eqnarray*} 19^{96}\equiv 1 \end{eqnarray*}$ mod 72 ist

Sieht so aus, als bist du damit fertig - es sei denn, du hast dich bei oben in der Aufgabenstellung beim Exponenten verschrieben. verwirrt

25.07.2016, 19:43

Elvis

Auf diesen Beitrag antworten »

Das soll vermutlich ein Scherz sein. Hast Du schon mal 19*19 durch 72 dividiert ?

25.07.2016, 19:47

Leopold

Auf diesen Beitrag antworten »

Zitat:

Original von Elvis
Hast Du schon mal 19*19 durch 72 dividiert ?

Mir fiel da gleich das regelmäßige Fünfeck ein.

25.07.2016, 19:52

Mido

Auf diesen Beitrag antworten »

Ich habe die Frage versehentlich unangemeldet gestellt. Jetzt bin ich angemeldet.

Eigentlich habe ich mich nicht verschrieben... Was ist denn dann der Rest, wenn ich fertig bin? Rest 1?

Ich habe das so zerlegt:

$\begin{eqnarray*} phi (72) = 30 \end{eqnarray*}$

$\begin{eqnarray*} ggT(19,72)=1 \end{eqnarray*}$

Satz von Euler ergibt: $\begin{eqnarray*} 19^{30}\equiv 1 mod 72 \end{eqnarray*}$

$\begin{eqnarray*} 19^{96} \equiv (19^{30} * 19^{2})^{3}\equiv 1*19^{6} mod 72 \end{eqnarray*}$

Aber 19^6 ist ja nicht der Rest.... verwirrt

25.07.2016, 20:00

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Mido
$\begin{eqnarray*} phi (72) = 30 \end{eqnarray*}$