Wie berechne ich mit Euler-Fermat

27.06.2015, 15:44

adasd

Wie berechne ich mit Euler-Fermat

Meine Frage:
Wie löse ich dies mit Euler-Fermat 6^(3^{17}) mod 11
Wenn nicht möglich, dann mit Chinesischer Restsatz

Meine Ideen:
Ich weiß, dass 6 und 11 teilerfremd sind, also es geht mit E-F, und habe phi(11)=10 und wie geht's witer?

27.06.2015, 15:52

HAL 9000

Auf diesen Beitrag antworten »

Kerngedanke solcher Rechnungen ist oft die Aussage

Zitat:

Sind $\begin{align*} a,m \end{align*}$ teilerfremd sowie $\begin{align*} u,v \end{align*}$ natürliche Zahlen mit $\begin{align*} u\equiv v\bmod\varphi(m) \end{align*}$ , dann gilt $\begin{align*} a^u\equiv a^v\bmod m \end{align*}$ .

die sich leicht mit Euler-Fermat begründen lässt.

Damit lassen sich die großen Exponenten herunterbrechen auf handliche Werte. In deinem Fall wäre also zunächst die Berechnung von $\begin{align*} 3^{17}\bmod 10 \end{align*}$ angesagt.

P.S.: Genau genommen kann man $\begin{align*} \varphi \end{align*}$ in dieser Aussage auch durch die Carmichael-Funktion $\begin{align*} \lambda \end{align*}$ ersetzen. Aber das bringt zum einen nur etwas bei Nichtprimzahlen $\begin{align*} m \end{align*}$ , zum anderen ist diese Carmichael-Funktion deutlich weniger bekannt. Augenzwinkern

27.06.2015, 16:00

Widderchen

Auf diesen Beitrag antworten »

Hallo,

es gilt doch : $\begin{eqnarray*} a^{\phi(n)} \equiv 1 mod \, n \end{eqnarray*}$ , falls $\begin{eqnarray*} ggt(a,n) = 1 \end{eqnarray*}$ .

Also gilt: $\begin{eqnarray*} 6^{10} \equiv 1 mod 11 \end{eqnarray*}$ . Du musst also den Exponenten 3^{17} als Vielfaches von 10 mit Rest darstellen:

$\begin{eqnarray*} 3^{17} = p \cdot 10 + q \end{eqnarray*}$ . Die Parameter p und q sind gesucht. Es gilt sogar:

$\begin{eqnarray*} 3^{17} \equiv 3 mod 10 \end{eqnarray*}$ . Ich hoffe, das war hilfreich.

Viele grüße
Widderchen

Neue Frage »

Antworten »

Wie berechne ich mit Euler-Fermat

Verwandte Themen