Kongruenzrechnung

20.06.2011, 11:26

PI2011

Kongruenzrechnung

Meine Frage:
Hallo liebe Mitmathematiker,
ich sitze gerade an folgender Aufgabe:

Berechne die letzten beiden Ziffern mittels Kongruenzen
7^7^7^7 - 7^7^7

Meine Ideen:
Also zuerst kann man dies ja schreiben als 7^343 - 7^49

Mit dem Satz von Euler wäre ja 7^40 = 1 mod 100 und somit auch 7^320 = 1 mod 100.

somit kann man die Differenz doch vereinfachen in
7^23 - 7^9

Nun weiß ich leider nicht wie man das weiter löst, ohne das Ergebnis durch einen Taschenrechner zu jagen. Wäre toll wenn mir hier jemand einen Denkanstoß geben würde.
MfG PI

20.06.2011, 13:33

René Gruber

Auf diesen Beitrag antworten »

Zitat:

Original von PI2011
Also zuerst kann man dies ja schreiben als 7^343 - 7^49

Da wäre ich mir nicht so sicher: Ich denke eher, es ist im Sinne

7^(7^(7^7)) - 7^(7^7)

gemeint, zumindest ist das die Entsprechung von $\begin{eqnarray*} 7^{7^{7^7}}-7^{7^7} \end{eqnarray*}$ .

Tipp: Berechne als Vorüberlegung $\begin{eqnarray*} 7^4 \bmod 100 \end{eqnarray*}$ .

20.06.2011, 15:05

PI2011

Auf diesen Beitrag antworten »

Achso stimmt, das war ja doof von mir.

okay also:

$\begin{eqnarray*} 7^{7} = 7^{4} * 7^{3} \end{eqnarray*}$ und $\begin{eqnarray*} 7^{4} mod 100 = 01 \end{eqnarray*}$ und somit sollte $\begin{eqnarray*} 7^{3} mod 100 = 7^{7} mod 100 = 43 \end{eqnarray*}$

Nun müsste ich das ja mehrfach anwenden oder?!

20.06.2011, 15:11

René Gruber

Auf diesen Beitrag antworten »

Für meinen Geschmack rechnest du schon viel zu viel: Aus diesem $\begin{eqnarray*} 7^4\equiv 1\bmod 100 \end{eqnarray*}$ lässt sich (über Potenzabspaltung) unmittelbar folgern

$\begin{eqnarray*} 7^a \equiv 7^b\bmod 100 \end{eqnarray*}$ für $\begin{eqnarray*} a\equiv b\bmod 4 \end{eqnarray*}$ .

Es genügt also, die beiden Exponenten $\begin{eqnarray*} 7^7 \end{eqnarray*}$ bzw. $\begin{eqnarray*} 7^{7^7} \end{eqnarray*}$ modulo 4 zu reduzieren.

20.06.2011, 15:28

PI2011

Auf diesen Beitrag antworten »

okay also kann man $\begin{eqnarray*} 7^{7} modulo 4 \end{eqnarray*}$ als $\begin{eqnarray*} 3^{3} modulo 4 \end{eqnarray*}$ und das wäre ja die Restklasse 3.

kann man das so machen?!

und wie komme ich dann auf die letzten beiden ziffern wenn wir nun nicht mir mod 100 sind sondern mod 4? so kann man sicherlich eine zahl die hinten mit 01 endet rausfinden aber man bekommt ja nicht die letzten beiden ziffern so bestimmt. verwirrt

20.06.2011, 15:32

René Gruber

Auf diesen Beitrag antworten »

Es ist nicht nur $\begin{eqnarray*} 7\equiv 3\bmod 4 \end{eqnarray*}$ , es ist auch $\begin{eqnarray*} 7\equiv -1\bmod 4 \end{eqnarray*}$ . Mit Basis $\begin{eqnarray*} (-1) \end{eqnarray*}$ lassen sich Potenzen hervorragend schnell berechnen. Augenzwinkern

Zitat:

Original von PI2011
und wie komme ich dann auf die letzten beiden ziffern wenn wir nun nicht mir mod 100 sind sondern mod 4?

Das habe ich doch gerade gesagt!!!

Zitat:

Original von René Gruber
$\begin{eqnarray*} 7^a \equiv 7^b\bmod 100 \end{eqnarray*}$ für $\begin{eqnarray*} a\equiv b\bmod 4 \end{eqnarray*}$ . (*)

Konkret heißt das, dass aus $\begin{eqnarray*} 7^7\equiv 3\bmod 4 \end{eqnarray*}$ dann $\begin{eqnarray*} 7^{7^7} \equiv 7^3\bmod 100 \end{eqnarray*}$ folgt.

Begründung von (*) mit Potenzgesetzen:

$\begin{eqnarray*} 7^{4k+r} = 7^{4k}\cdot 7^r = (7^4)^k\cdot 7^r \equiv 1^k\cdot 7^r = 7^r\bmod 100 \end{eqnarray*}$

20.06.2011, 15:39

PI2011

Auf diesen Beitrag antworten »

Somit weiß ich das $\begin{eqnarray*} 7^{7^{7^{7}}} mod 4 = 3 \end{eqnarray*}$ ist aber wie bekomme ich nun rückwärts wieder mod 100 hin sodass ich die letzten beiden ziffern herausfinde...?

20.06.2011, 15:41

PI2011

Auf diesen Beitrag antworten »

verzeihung den letzten eintrag einfach überlesen.... da war ich wohl zu schnell

20.06.2011, 15:41

René Gruber

Auf diesen Beitrag antworten »

Eher zu langsam. Augenzwinkern

20.06.2011, 15:59

PI2011

Auf diesen Beitrag antworten »

okay also ist $\begin{eqnarray*} 7^{7^{7}} \equiv 43 mod 100 \end{eqnarray*}$

wenn ich das aber auf $\begin{eqnarray*} 7^{7^{7^{7}}} \end{eqnarray*}$ anwende bekomme ich für den exponenten heraus: $\begin{eqnarray*} 7^{7^{7}} \equiv 3 mod 4 \end{eqnarray*}$ und somit auch wieder wieder $\begin{eqnarray*} 7^{7^{7^{7}}} \equiv 43 mod 100 \end{eqnarray*}$

wenn ich nun subtrahiere bekomme ich aber die restklasse 00 raus... unglücklich

wenn ich dein ansatz unter (*) überprüfe komm ich auf $\begin{eqnarray*} 7^{3} \equiv 43 mod 100 \end{eqnarray*}$ aber wenn ich es durch den taschenrechner jage ist $\begin{eqnarray*} 7^{7^{7}} \equiv 07 mod 100 \end{eqnarray*}$

20.06.2011, 16:14

René Gruber

Auf diesen Beitrag antworten »

Zitat:

Original von PI2011
wenn ich nun subtrahiere bekomme ich aber die restklasse 00 raus...

... was das richtige Ergebnis ist.

Zitat:

Original von PI2011
aber wenn ich es durch den taschenrechner jage ist $\begin{eqnarray*} 7^{7^{7}} \equiv 07 mod 100 \end{eqnarray*}$

Sieht ganz so aus, als hat da so ein Schlaumeier wieder

$\begin{eqnarray*} \left( 7^7 \right)^7 \bmod 100 \end{eqnarray*}$ statt $\begin{eqnarray*} 7^{7^7} = 7^{\left( 7^7 \right)} \bmod 100 \end{eqnarray*}$

gerechnet. Forum Kloppe

Neue Frage »

Antworten »

Kongruenzrechnung

Verwandte Themen