Endziffer bei Potenzen/ Kongruenzen

01.04.2012, 18:06

Jewels

Endziffer bei Potenzen/ Kongruenzen

Meine Frage:
Hey!

Ich komm einfach nicht dahinter, wie man die Endziffer (auch Einerziffer genannt) mit Hilfe von Kongruenzen rausbekommt.
Hier die gegebene Zahl: 8 ^ 100

Meine Ideen:
Klar ist: Zuerst schau ich was die 8 für Endziffern annehmen kann:

8^1 Endziffer 8
8^2 Endziffer 4
8^3 Endziffer 2
8^4 Endziffer 6

Jetzt geht es darum zu schauen, wo, in welcher Zeile die 100 stehen würde. Man könnte es auch abzählen, aber bei der 1000 würde das schon etwas schwieriger aussehen.

Dann die Schreibweise mit Kongruenzen:

8^2 = 4 mod 10
8^3 = 2 mod 10
8^4 = 6 mod 10
8^5 = 8 mod 10

Lösung würde dann so aussehen:
8^100 = (8^5)^20 = 8^20 = (8^5)^4 = 8^4 = 6 mod 10, also Endziffer ist 6

Ich verstehe alles, bis auf die letzte "Gleichung"
Ich könnte ja genauso gut schreiben 8^20= (8^4)^5 = 8^5 und hätte dann 8 als Einerziffer raus.
Wo ist jetzt also der Sinn in dem Ganzen? Und warum schreibe ich am Ende nicht nochmal 8^4= (8^2)^2???

Komme einfach nicht weiter!

Vielen Dank schon mal smile

01.04.2012, 18:13

galoisseinbruder

Auf diesen Beitrag antworten »

Hallo und natürlich auch Willkommen

Zitat:

8^20= (8^4)^5 = 8^5

Nein, denn $\begin{eqnarray*} 8^4\equiv 6 \mod 10 \end{eqnarray*}$ man könnte also $\begin{eqnarray*} 8^20= (8^4)^5 = 6^5 \end{eqnarray*}$ schreiben, aber die 6-er Potenzen mod 10 hast du ja noch nicht berechnet.

Zitat:

Und warum schreibe ich am Ende nicht nochmal 8^4= (8^2)^2???

Weil du 8^4 ja bereits modulo 10 berechnet hast.

Allgemein rechnen sich solche Aufgaben deutlich einfacher wenn man den Satz von Euler kennt (was man hier implizit ausnützt) oder sogar die Carmichael-Funktion.

01.04.2012, 18:20

Jewels

Auf diesen Beitrag antworten »

Ja genau 8^4 = 6 mod 10, aber das ja auch: 8^20 = 6 mod 10

Warum kann ich zum Beispiel nicht auch 8^100= (8^25)^4 oder (8^4)^25 schreiben?

Wie wähle ich die Potenzen denn aus?

01.04.2012, 18:31

galoisseinbruder

Auf diesen Beitrag antworten »

Bei $\begin{eqnarray*} (8^4)^{25}\equiv 6^{25} \mod 10 \end{eqnarray*}$ aber die Potenzen von 6 mod 10 müsstest du erst noch ausrechnen, die von 8 kennst du bereits.
Bei $\begin{eqnarray*} (8^25)^4 \equiv(( 8^5)^5)^4 \equiv (8^5)^4\equiv 8^4=6 \mod 10 \end{eqnarray*}$ ist im Wesentlichen das Vorgehen der Lösung.
Der Trick ist das $\begin{eqnarray*} 8^{100} \end{eqnarray*}$ auf kleinere Potenzen von 8 zurückzuführen. Und das geht hier am besten mit 8^5, da $\begin{eqnarray*} 8^5 \equiv 8 \mod 10 \end{eqnarray*}$ , und 5 ist die kleinste Zahl n(größer als 1) mit $\begin{eqnarray*} 8^n\equiv 8 \mod 10 \end{eqnarray*}$

01.04.2012, 18:51

Jewels

Auf diesen Beitrag antworten »

Ahhhhh Suuuuper, habe es verstanden smile

Habe es grade mal mit 2^1000 ausprobiert und kam auf das richtige Ergebnis.

Nur mit 7^84 klappts noch nicht so ganz...
Ich weiß:

7^1 = 7 mod 10
7^2 = 9 mod 10
7^3 = 3 mod 10
7^4 = 1 mod 10

aber wie stelle ich 7^84 mit Hilfe von 7^5 oder 7^9 dar?

So: 7^84 = (7^5)^16+4 = 7^16 + 7^4 = 1+1 ??

01.04.2012, 18:59

galoisseinbruder

Auf diesen Beitrag antworten »

Die 8 modulo 10 ist als Anfangsbeispiel etwas ungut. Denn eigentlich versucht man ein n zu finden mit $\begin{eqnarray*} a^n\equiv 1 \mod m \end{eqnarray*}$ . Das geht bei der 8 modulo 10 nicht, da 8 und 10 nicht teilerfremd sind.
Hier wäre also 4 das Geschickteste. Dann Ansatz funktioniert aber auch ziemlich gut, allerdings ist ein Fehler drin. Wo Plus steht müsste ein Mal stehen:
$\begin{eqnarray*} 7^{84} = (7^5)^{16} \cdot 7^4 = 7^{16} \cdot 7^4 =1\cdot 1 \end{eqnarray*}$

01.04.2012, 20:14

Mystic

Auf diesen Beitrag antworten »

Ich denke, wenn der Modul (hier 10) zusammengesetzt ist, sollte man ihn prinzipiell in die maximalen Teiler, welche Primzahlpotenzen sind, aufspalten, also hier die Zerlegung

$\begin{eqnarray*} 10 = 2 \cdot 5 \end{eqnarray*}$

verwenden... Da man ohnehin weiß, dass das Ergebnis der Potenzbildung gerade sein muss, genügt es hier die fragliche Potenz mod 5 zu berechnen:

$\begin{eqnarray*} 8^{100} = (8^2)^{50} \equiv (-1)^{50} \equiv 1\mod 5 \end{eqnarray*}$

Damit kommen mod 10 nur die Zahlen 1 und 6 in Frage, wobei 1 als ungerade Zahl, wie schon erwähnt, ausscheidet...

01.04.2012, 20:16

Jewels

Auf diesen Beitrag antworten »

Aber es ist ja nach der Endstelle gefragt, dann bringt es mir ja nichts wenn ich mod 5 da stehen habe?

01.04.2012, 20:53

Mystic

Auf diesen Beitrag antworten »

Zitat:

Original von Jewels
Aber es ist ja nach der Endstelle gefragt, dann bringt es mir ja nichts wenn ich mod 5 da stehen habe?

Hm, hast du meinen Beitrag überhaupt gelesen? geschockt

Ich sagte doch darin ganz klar, dass man von allen Lösungen, die man mod 5 erhält, die geraden nehmen muss, und bin damit auch auf die Lösung 6 gekommen...

01.04.2012, 21:03

Jewels

Auf diesen Beitrag antworten »

Hast du ja erst im Nachhinein editiert Augenzwinkern

Aber finde es trotzdem ganz schön umständlich. Hier war jetzt nur nach der Endstelle gefragt, aber wenn man dann ne Aufgabe hat, wo zum Beispiel nach dem Rest von x^y beim Teilen von 13 gefragt ist, hilft mir das auch nicht weiter.

Meine Frage hat sich auf jeden Fall geklärt Augenzwinkern

01.04.2012, 21:16

Mystic

Auf diesen Beitrag antworten »

Zitat:

Original von Jewels
Hast du ja erst im Nachhinein editiert Augenzwinkern

Ne, das stand schon vorher so da... Ich habe beim Editieren nur die Berechnung von $\begin{eqnarray*} 8^{100} \end{eqnarray*}$ mod 5 etwas ausführlicher dargestellt...

Zitat:

Original von Jewels
Aber finde es trotzdem ganz schön umständlich. Hier war jetzt nur nach der Endstelle gefragt, aber wenn man dann ne Aufgabe hat, wo zum Beispiel nach dem Rest von x^y beim Teilen von 13 gefragt ist, hilft mir das auch nicht weiter.

Da hast das Grundproblem nicht erkannt, dass hier darin bestand, dass 8 und 10 nicht teilerfremd sind, weshalb sich die Berechnung von Potenzen von 8 mod 10 schwieriger gestaltet, als z.B. die Berechnung von Potenzen von 3 mod 10... Beim Modul 13 hat man dieses Problem von vornhererin nicht, da 13 ja eine Primzahl ist...

Neue Frage »

Antworten »

Endziffer bei Potenzen/ Kongruenzen

Verwandte Themen