Trick zur Berechnung der Phi-Funktion

22.02.2017, 13:35

MathRev

Trick zur Berechnung der Phi-Funktion

Hallo,

ich habe neulich in einem Klausur folgende Aufgabe gesehen:

Berechnen Sie $\begin{eqnarray*} 5^{99} \mod 104 \end{eqnarray*}$

Der Weg der Lösung ist mir soweit klar.
1. Prüfe ob ggT(5, 104) = 1 (dann sind 5 und 104 Teilerfremd)
2. Falls 1. erfüllt ist wende den Satz von Euler an. ( $\begin{eqnarray*} a^{\varphi(n)} \equiv 1 \mod n \end{eqnarray*}$ )
3. Potenzgesetze anwenden, sodass $\begin{eqnarray*} \varphi(n) \end{eqnarray*}$ im Exponenten steht und man so 1 als Multiplikator erhält.

Da in der Lösungskizze der Klausur steht, dass diese ohne Taschenrechner berechnet werden soll und folgender Schritt als Trivial aufgeführt wurde:

$\begin{eqnarray*} 104 = 13 * 8 \Rightarrow \varphi(104) = \varphi(13) * \varphi(8) \end{eqnarray*}$

frage ich mich wie man das so schnell sehen kann? Bzw. ob es einen Trick gibt die Zahl so zu zerlegen, das man $\begin{eqnarray*} n = p * q \end{eqnarray*}$ mit $\begin{eqnarray*} ggT(p, q) = 1 \end{eqnarray*}$ erhält ohne alle Zahlen durchzuprobieren.
Oder ob es evtl sogar noch einfacheres allgemeineres vorgehen gibt falls $\begin{eqnarray*} \varphi(n) \end{eqnarray*}$ mit n ist keine Primzahl.

22.02.2017, 13:50

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von MathRev
Bzw. ob es einen Trick gibt die Zahl so zu zerlegen, das man $\begin{eqnarray*} n = p * q \end{eqnarray*}$ mit $\begin{eqnarray*} ggT(p, q) = 1 \end{eqnarray*}$ erhält ohne alle Zahlen durchzuprobieren.

Der "Trick" nennt sich Primfaktorzerlegung, und ist nun bei einer so vergleichsweise kleinen Zahl wie 104 kein Hexenwerk: $\begin{align*} 104 = 2^3\cdot 13 \end{align*}$ . Und die einzelnen Faktoren (d.h. Primfaktorpotenzen) einer Primfaktorzerlegung sind nun mal paarweise teilerfremd. Augenzwinkern

D.h., für $\begin{align*} n=p_1^{r_1}\cdot \ldots \cdot p_s^{r_s} \end{align*}$ gilt direkt

$\begin{align*} \varphi(n) = \varphi\left(p_1^{r_1}\right)\cdot \ldots \cdot \varphi\left(p_s^{r_s}\right) = p_1^{r_1-1}(p_1-1)\cdot \ldots \cdot p_s^{r_s-1}(p_s-1) \end{align*}$ .

22.02.2017, 14:04

MathRev

Auf diesen Beitrag antworten »

Zitat:

Der "Trick" nennt sich Primfaktorzerlegung

Stimmt. manchmal sieht man den Wald vor lauter Bäumen nicht Hammer

Vielen Dank Wink

Neue Frage »

Antworten »

Trick zur Berechnung der Phi-Funktion

Verwandte Themen