Hallo,
ich studiere Maschinenbau und lerne geraddamit einer alten Klausur in der die folgende Aufgabe gestellt wurde.
Berechnen Sie, welchen Rest die Division von 1+7^77 durch 10 ergibt.
Wir dürfen keinen Taschenrechner benutzen!!
Gibt es einen Trick wie man das lösen kann?
Hallo,
rechne mal – um das Prinzip zu erkennen – mit dem Taschenrechner 7n von n = 0 ab aus (bis n = irgendwas zwischen 12 und 15 sollte reichen) und schreib die Ergebnisse untereinander. Markiere jeweils die letzte Ziffer, denn die gibt ja 7n mod 10 an. Fällt Dir was auf?
70 mod 10 = ?
74 mod 10 = ?
71000000 mod 10 = ?
776 mod 10 = ?
71 mod 10 = ?
75 mod 10 = ?
71000001 mod 10 = ?
777 mod 10 = ?
1 + 71 mod 10 = ?
1 + 75 mod 10 = ?
1+ 71000001 mod 10 = ?
1 + 777 mod 10 = ?
Reicht das als Hilfestellung?
Gruß
Martin
Ja da kommen die Endziffern 1;7;9;3 raus die sich ja immer wiederholen aber wie macht man nun weiter?
Ich muss ja noch +1 und durch 10 rechnen?
Hallo
Ja da kommen die Endziffern 1;7;9;3 raus die sich ja immer wiederholen aber wie macht man nun weiter?
Ich hab das eben (ohne die Antwort von Martin und deine Antwort darauf gelesen zu haben) kurz im Kopf gerechnet und die Ergebnisse mit Papier und Bleistift festgehalten. Man braucht überhaupt keinen Taschenrechner, die Rückseite von einem kleinen Kassenzettel reicht.
Es genügt völlig, die Einerstellen mit 7 zu multiplizieren, um auf die Einerstelle der nächsten Potenz zu kommen.
Meine kleine Tabelle sah zuerst so aus (statt 7^1, 7^2 schreibe ich einfach 1, 2):
1 7
2 9
3 3
4 1
Dann habe ich kurz überlegt, 4*20 = 80 gerechnet und meine Tabelle erweitert (rechts unten angefangen:
1 7 77
2 9 78
3 3 79
4 1 80
Und dann ist die Lösung eigentlich offensichtlich, du musst nur noch die richtige Zahl auswählen und 1 addieren.
Schöne Grüsse
dodeka
Hallo,
das kann man recht gut mit dem Square-and-Multiply-Verfahren ausrechnen. Das Prinzip dabei ist, dass die Potenz zerlegt wird. Bei 2er-Potenzen als Exponent ist das ja recht einfach.
Also
3^8 = ((3^2)^2)^2
Bei anderen Potenzen kommt jeweils noch eine Multiplikation dazu:
3^5
= 3 * 3^4
= 3 * (3^2)^2
Wenn man sich den Exponenten vorher in eine Binärzahl umwandelt, kann man die Reihenfolge direkt abschreiben. Eine 0 bedeutet dabei einfach „square“, also quadrieren und eine 1 bedeutet „square and multiply“. Es wird bei 1 begonnen:
für 3^10:
exponent = 10_{10} = 1010_2
3^{10}
= (((1^2 * 3)^2)^2 * 3)^2
Die Reihenfolge ist also (beginnend mit der 1):
square and multiply, square, square and multiply, square.
Somit kannst du die Potenz zerlegen. Das schöne an der Modulo-Rechnung ist, dass sie auf jeden Teilschritt direkt angewandt werden kann. Also jedes mal wenn du square oder multiply ausgeführt hast, kannst du sofort modulo rechnen und die Zahl verkleinert sich. Wenn wir wie oben 3^10 mod 5 berechnen wöllten, könnten wir also:
3^{10}
\equiv (((1^2 * 3)^2)^2 * 3)^2
\equiv (((3)^2)^2 * 3)^2
\equiv ((9)^2 * 3)^2
\equiv ((4)^2 * 3)^2
\equiv (16 * 3)^2
\equiv (1 * 3)^2
\equiv (3)^2
\equiv 9
\equiv 4
Dass sich das hier nun zufällig so periodisch wiederholt, war nicht beabsichtigt und ist im Allgemeinen auch nicht der Fall.
In deinem Fall musst du zum Schluss noch 1 dazuaddieren (der unteilbare Rest erhöht sich natürlich um 1, wenn du zur ursprünglichen Zahl 1 dazu addierst; oder er springt auf 0 zurück).
Nico
Hallo!
Wenn du rechnest: 7^0, 7^1, 7^2, wirst du feststellen, dass sich die letzte Ziffer des Ergebnis in 4er Gruppen wiederholt: 1, 7, 9, 3. Der Rest sollte ein Leichtes sein. Vergiss aber nicht: +1!
Gruß Werner
Hallo,
die Rückseite von einem kleinen Kassenzettel reicht.
lach… OK, dann schau Dir mal die Briefmarken-Lösung an:
1 + 777 ≡ 1 + 71 + 2 · 38 ≡ 1 + 7 · 4938 ≡ 1 + 7 · (–1)38 ≡ 1 + 7 · 1 ≡ 8
Es genügt völlig, die Einerstellen mit 7 zu multiplizieren, um
auf die Einerstelle der nächsten Potenz zu kommen.
Ja, das funktioniert, aber – s. o. – es geht sogar noch schneller und kürzer.
Gruß
Martin
Hallo Martin
Briefmarken-Lösung
Das ist genial! 
Aber kannst du mir bitte noch erklären, wie du auf 4938 ≡ (–1)38 kommst? Ich bin mathematisch leider noch nicht so weit, dass ich es fachsprachlich korrekt ausdrücken kann. Die fortgesetzte Potenzierung einer auf 9 endenden Zahl bringt natürlich immer abwechselnd 9 und 1 als letzte Ziffer, das ist evident. Dadurch wird es auch noch einfacher, wie du schreibst. Aber warum kommst du auf (–1)38? Die Modulo-Rechnung vertehe ich vom Prinzip her schon, aber da hätte ich jetzt 4938 ≡ 1 38 erwartet, was – o glückliche Fügung – zum gleichen Ergebnis geführt hätte…
Herzlichen Gruss
dodeka
smile
wie du auf 4938 ≡ (–1)38 kommst?
Das ist trivial:
… ≡ –31 ≡ –21 ≡ –11 ≡ –1 ≡ 9 ≡ 19 ≡ 29 ≡ 39 ≡ 49 ≡ 59 ≡ 69 ≡ … (mod 10)
wobei die „…“ andeuten sollen, dass es links und rechts ad infinitum weitergeht.
Ich habe mir von den unendlich vielen Zahlen, zu denen 49 kongruent ist, die –1 herausgepickt, weil –1 als Basis einer Potenz spitzenmäßig vorteilhaft ist.
Die fortgesetzte Potenzierung einer auf 9 endenden Zahl bringt natürlich immer
abwechselnd 9 und 1 als letzte Ziffer, das ist evident.
Das stimmt zwar; Betrachtungen dieser Art gehen aber in die Briefmarken-Rechnung nicht ein.
hätte ich jetzt 4938 ≡ 1 38 erwartet
Hey, Vorsicht: 49 ist nicht mod-10-kongruent zu 1!
Martin
mod 10
Ja, das war der Schlauch, auf dem ich stand! Ich hatte mit mod 9 gerechnet, aber jetzt ist es klar. Und irgendwie hatte ich zwar auch gesehen, dass man mit mod 10 auf -1 kommt, habe aber dann entweder zu kompliziert oder zu simpel gedacht, so dass ich der Meinung war, es müsste hier um mod 9 gehen…
Ich habe mir von den unendlich vielen Zahlen, zu denen 49 kongruent ist, die –1 herausgepickt, weil –1 als Basis einer Potenz spitzenmäßig vorteilhaft ist.
Das leuchtet ein.
Herzlichen Dank für die Aufklärung!
Und einen schönen Sonntag
dodeka