Restbestimmung bei Kongruenzaufgaben?
Ich muss in einer Hausaufgabe die Reste von folgenden Kongruenzaufgaben bestimmen. a) 10^1337 modulo 9 b) 10^1337 modulo 11 c) 1337^10 modulo 11 d) 1337^11 modulo 11 e) 9^42 modulo 13 und f) Die Endziffer von 7^420
Ich sitze da nun schon mehrere Tage dran und bin am verzweifeln, da ich einfach nicht mehr weiter weiß. Wenn man den kleinen Fermat anwenden kann, wie bei Aufgabe c) klappt es, aber ansonsten weiß ich einfach nicht weiter. Ich wäre so unglaublich glücklich, wenn es mir hier irgendjemand erklären könnte! ( Ich möchte wirklich nicht einfach nur die Lösung, sondern eine Erklärung, sodass ich es auch verstehen und nicht einfach nur abschreiben kann)
Vielen Dank schon mal!
3 Antworten
Mal ein paar billige Erklärungen:
a) 10^1337 modulo 9
Das ist immer 1, da 9^x (x Element Z) immer mindestens eins unter 10^b (b Element Z) ist. Das liegt daran, dass wir ein Zehnersystem haben und die 9 eins darunter ist.
b) 10^1337 modulo 11
Etwas schwierig. Ist bei 10^x das x ungerade, kann man via 11*9^b (b Element Z) bis eins unter 10^x kommen. Ist 10^x gerade, kommt man mit 11*9^b lediglich bis 10 unter die Zahl (logisch, den andere Abstände sind zu 10 nicht möglich, und diese alternieren.
c) 1337^10 modulo 11
Wir haben bei a^10 / 11 immer eine 1 am Ende, weil a 10 mal multipliziert wird, also gerade ist (siehe b). logisch.
d) 1337^11 modulo 11
Das ist leicht schwieriger, im Vergleich zu c) kommt immer noch einmal der Faktor dazu. also erhöht sich der Ergebnis jeweils um 1 und wir die Sequenz 1,2,...,9,10,0,1, logisch. Entsprechend können wir aus 1337 erkennen, was der Modulo ist = 1337 Modulo 11, also a^11 Modulo 11 = a Modulo 11.
e) 9^42 modulo 13
Wir haben hier die Modulo-dreier-Sequenz 1,9,3,1. Also einfach 42 Modulo 3 = 0, also die erste Zahl der Sequenz = 1
und f) Die Endziffer von 7^420
Easy: DAs ist 7^x Modulo 10. Hier haben wir die vierer-Sequenz 1,7,9,3,1. Also 420 Modulo 4 = 0, Endziffer = 1
Zunächst einmal kann man schauen, ob man die Basis reduzieren kann:
Dann kann man schauen, ob man den Exponenten mit Hilfe des kleinen Satzes von Fermat reduzieren kann:
Ich habe dir im folgenden mal zwei eigene Beispiele aufgeschrieben, damit du mit deinen Aufgaben selbst noch etwas üben kannst.
Beispiel 1: Gesucht ist 25¹⁰⁰⁰ mod 12.
Wegen 25 ≡ 1 mod 12 (denn 25 = 2 ⋅ 12 + 1) erhält man
25¹⁰⁰⁰ ≡ 1¹⁰⁰⁰ ≡ 1 mod 12.
Demnach ist 1 der gesuchte Rest.
Beispiel 2: Gesucht ist 3¹⁴³² mod 11.
Mit kleinem Satz von Fermat erhält man 3¹⁰ ≡ 1 mod 11. Daher kann man im Exponenten modulo 10 rechnen. Teilen mit Rest liefert 1432 = 143 ⋅ 10 + 2.
3¹⁴³² ≡ (3¹⁰)¹⁴³ ⋅ 3² ≡ 1¹⁴³ ⋅ 3² ≡ 3² ≡ 9 mod 11
Man hat also den Exponenten 1432 modulo 10 reduzieren können, um dann nur noch 3² rechnen zu müssen.
============
Hier habe ich dir mal einen Lösungsvorschlag zu deiner Aufgabe aufgeschrieben:
Ah, Ich glaube jetzt hat es bei mir endgültig klick gemacht, vielen vielen vielen Dank!
Welche Aufgabe denn. Sind alle recht einfach.
a) z.B.
10^1337 modulo 9 = 1^1337 modulo 9 = 1
Was genau bekommst du denn nicht hin?
b) funktioniert analog.
Worin liegt die Schwierigkeit?
Kannst du das eventuell erklären? Also die ersten Aufgaben gehen auch noch, aber am schlimmsten finde ich eigentlich e) und f). Da verstehe ich gar nicht, wie das funktionieren soll... Das Prinzip des Rechnens mit modulo ist mir schon klar, aber die Umkehrung irgendwie nicht. Wahrscheinlich ist es total einfach und ich sehe einfach nur den Wald vor lauter Bäumen nicht, aber eine Erklärung wäre mir daher ganz lieb.
Ich kann dir ja noch mal e) vorrechnen.
9^42 modulo 13
Dann gibt es einen hilfreichen Satz:
Satz von Euler:
a^p(n) ≡ 1 mod n , wenn a,n teilerfremd sind.
p(n) ist dabei die eulerische phifunktion die fuer Primzahlen
p(n) = n-1 ist
a ist also 9 = 3^2
n ist 13
p(13) = 12
Da die Zahlen keine gleichen Teiler haben sind sie teilerfemd (ggt(a,n) = 1) und man kann den Satz von Euler anwenden.
9^42 mod 13 haben wir
Wir wissen durch Euler, dass
9^12 ≡ 1 mod 13
ist
Jetzt versuchen wir mit den Potenzgesetzen unser Problem zu vereinfachen.
42=12*3 + 6
Also koennen wir umformen
9^42 = (9^12)^3 * 9^6
aber 9^12 ist ja grade nach Euler 1 mod 13
Daher:
9^42 ≡ (9^12)^3 * 9^6 ≡ 1^3 * 9^6 ≡ 9^6 mod 13
Ab hier kann man weiter vereinfachen
9^6 = (9^2)^3 = 81^3
81^3 ≡ 3^3 ≡ 27 ≡ 1 mod 13
Alles klar, vielen Dank, ich glaube jetzt habe ich es einigermaßen verstanden!
Gut. Falls du einen Zwischenschritt nicht verstehst, dann kannst du gerne Fragen und ich erklare es etwas kleinschrittiger.
Vielen Dank für die allgemeine Erklärung, allerdings hört sich das für mich alles ein bisschen spanisch an. Kannst du das vielleicht anhand eines Beispiels erklären? Ich verstehe nämlich immer noch nicht, wie mir das in hinblick auf meine Restbestimmung hilft.