Modulo rechnen mit Potenzen

02.05.2012, 19:16

zickezacke

Modulo rechnen mit Potenzen

Meine Frage:
Wir sollen den Rest von 17^145 bei der Division mit 13 bestimmen.

Meine Ideen:
Also 17^145 mod 13 oder!?
Kann ich es dann in (17^5)^29 mod 13 auflösen?
17^5 ? 10 mod 13
Kann ich so ansetzen? und wie kann ich das nun weiter auflösen?

02.05.2012, 19:20

soase

Auf diesen Beitrag antworten »

Kleiner Fermat bzw. Satz von Euler verwenden, dann ist hier nichts zu rechnen.

02.05.2012, 19:20

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von zickezacke
Kann ich es dann in (17^5)^29 mod 13 auflösen?

Klar kannst du. Aber in Hinblick auf eine schnelle, effiziente Lösung ist eher

$\begin{eqnarray*} 17^{145} = 17\cdot 17^{144} = 17\cdot \left( 17^{12} \right)^{12} \end{eqnarray*}$

anzuraten, wenn man an den Kleinen Fermat denkt.

02.05.2012, 19:35

zickezacke

Auf diesen Beitrag antworten »

Also kann ich dann sagen, dass
17^12 ≡ 1 mod 13 ?

und wie was mach ich dann mit dem Rest?

02.05.2012, 20:40

zickezacke

Auf diesen Beitrag antworten »

Ich habe nun 17* (17^12)^12 = 17* 17^12 (da 17^12 = 1 mod 13)
= 17*1
also 17= 4 mod 13
Ist das richtig so?

und bei 7^(7^7) mod 10 wäre es doch dann nach dem Satz von Euler:
7^7=1 mod 10
und wie beziehe ich jetzt die letzte 7 da mit ein?
einfach => 7^1= 7 mod 10 ???

03.05.2012, 07:05

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von zickezacke
Ich habe nun 17* (17^12)^12 = 17* 17^12 (da 17^12 = 1 mod 13)

Du meinst natürlich 17* (17^12)^12 = 17* 1^12 mod 13 , dann ist es richtig (und du hast ja im weiteren auch so gerechnet).

Zitat:

Original von zickezacke
und bei 7^(7^7) mod 10 wäre es doch dann nach dem Satz von Euler:
7^7=1 mod 10

Das ist falsch, tatsächlich ist $\begin{eqnarray*} 7^7 \equiv 3 \bmod 10 \end{eqnarray*}$ .

Tatsächlich widmet man sich erstmal allgemein $\begin{eqnarray*} 7^n \bmod 10 \end{eqnarray*}$ , da stellt sich nach dem Satz von Fermat-Euler $\begin{eqnarray*} 7^{\varphi(10)} = 7^4 \equiv 1\bmod 10 \end{eqnarray*}$ heraus, in der Folge also $\begin{eqnarray*} 7^{4k} \equiv 1\bmod 10 \end{eqnarray*}$ für alle natürlichen Zahlen $\begin{eqnarray*} k \end{eqnarray*}$ .

D.h., den Exponenten $\begin{eqnarray*} {\color{red} 7^7} \end{eqnarray*}$ der Potenz $\begin{eqnarray*} 7^{\color{red} 7^7} \end{eqnarray*}$ untersucht man erstmal modulo 4:

$\begin{eqnarray*} 7^7 \equiv (-1)^7 = -1 \equiv 3\bmod 4 \end{eqnarray*}$ .

Und das führt dann zu

$\begin{eqnarray*} 7^{\color{red} 7^7} \equiv 7^{\color{red} 3} \equiv 3 \bmod 10 \end{eqnarray*}$ .

Neue Frage »

Antworten »

Modulo rechnen mit Potenzen

Verwandte Themen