Hilfe,
habe morgen Examensprüfung und grübele jetzt schon seit Tagen immer wieder über folgender Frage:
Nach dem Satz von Euler-Fermat kann man mit den primen Restklassen auch den 1000er-Rest von 7°9999 ausrechnen, indem man mit der Anzahl der primen Restklassen und mod 1 rechnet.
Wie also kann ich 7°9999 mod 1000 ausrechnen??
Bitte dringen, vielen Dank.
Hallo!
habe morgen Examensprüfung
Dann hast Du die Frage wohl zu spät eingestellt. Aber ich will Dich ja nicht dumm sterben lassen, nur weil Deine Prüfung vorbei ist. Deshalb hier die Lösung:
Nach dem Satz von Euler-Fermat kann man mit den primen
Restklassen auch den 1000er-Rest von 7°9999 ausrechnen
Lassen wir mal Fachbegriffe wie „prime Restklassen“ beiseite, die brauchen wir hier nicht. Was sagt denn Euler-Fermat? Am besten merkt man sich Sätze in der Form „Voraussetzungen - Folgerung“. Also:
Voraussetzung: a,n in Z; ggT(a,n)=1 (d.h. a und n sind teilerfremde ganze Zahlen).
Folgerung: aφ(n) ≡ 1 mod n.
Wie also kann ich 7°9999 mod 1000 ausrechnen??
Deine Aufgabe legt erst einmal a und n fest, denn a ist ja die Basis der zu berechnenden Potenz (in Deiner Aufgabe also 7), während n der Modulus ist (also 1000).
Wir überprüfen die Voraussetzung und stellen fest: Ja, 7 und 1000 sind teilerfremd, Euler-Fermat lässt sich also anwenden.
Um den Satz nun anzuwenden, benötigen wir φ(n), also φ(1000). Um den Wert der Euler’schen φ-Funktion an einer Stelle zu bestimmen, müssen wir das Argument in Primfaktoren zerlegen, was hier nicht weiter schwierig ist:
1000 = 10³ = (2*5)³ = 2³*5³.
Damit ist φ(1000) = φ(2³*5³) = φ(2³)*φ(5³) = 2²*1*5²*4 = 400.
Nun sagt der Satz: 7⁴⁰⁰ ≡ 1 mod 1000.
Damit ist auch 7k*400 ≡ 1 mod 1000 für alle natürlichen Zahlen k. Nun können wir Deine Aufgabe zerlegen:
7⁹⁹⁹⁹ = 7⁹⁶⁰⁰⁺³⁹⁹ = 7⁹⁶⁰⁰*7³⁹⁹ ≡ 1*7³⁹⁹ = 7³⁹⁹ mod 1000.
Jetzt müsstest Du noch 7³⁹⁹ bestimmen, näher kommst Du nicht an das gewünschte Ergebnis heran; insofern ist die Aufgabe etwas ungeschickt gewählt, denn das ist jetzt natürlich ein Heidenaufwand. Aber ich denke mal, dass es Dir nur ums Prinzip ging und Du dieses hiermit verstanden hast.
Liebe Grüße
Immo
Hallo,
Jetzt müsstest Du noch 7399 bestimmen, näher kommst
Du nicht an das gewünschte Ergebnis heran; insofern ist die Aufgabe
etwas ungeschickt gewählt, denn das ist jetzt natürlich ein
Heidenaufwand.
so man einen Taschenrechner benutzen darf, ist 7399 mod 1000 schnell erledigt.
399 = 3 · 7 · 19 ⇒ 7399 = ((73)7)19
73 = 343, aber leider ist 3437 schon zu groß für den Taschenrechner.
Also probieren wir, obs vielleicht mit ((77)3)19 besser geht:
77 = 823543 = 543. Da das nur in die 3. Potenz zu erheben ist, gibts kein Problem: 5433 = 160103007 = 007. Das ist erfreulich klein; dennoch packt ein Taschenrechner 00719 nicht in einem Stück. Also zerlegen: 00719 = 00710 · 0079 = 282475249 · 40353607 = 249 · 607 = 151143 = 143.
Ergebnis: 79999 mod 1000 = 143
Gruß
Martin
PS: Ich hoffe, es stört sich niemand an „823543 = 543“ etc. Man denke sich hinter allem immer das „mod 1000“ hinzu, das ich der Übersichtlichkeit halber weggelassen habe.
Hallo,
so man einen Taschenrechner benutzen darf, ist 7399
mod 1000 schnell erledigt.
falls nicht, könnte man das so schnell im Kopf erledigen:
Wir wissen bereits, dass 7400 ≡ 1. Also ist 7399 das Inverse zur 7. Das lässt sich über den erweiterten euklidischen Algorithmus berechnen (angewandt auf 1000 und 7):
1000 = 142 * 7 + 6
7 = 6 * 1 + 1
=> 1 = 7 - (1000 - 142 * 7) = 143 * 7 - 1000
Also ist 143 * 7 ≡ 1 und 143 die gesuchte Zahl.
Andreas
Hallo Andreas,
an den Euklid hatte ich auch schon gedacht, schreckte dann aber davor zurück, weil ich mir nicht sicher war, ob in Restklassenringen die Inversen immer eindeutig sind.
Allerdings hast Du ja recht, wir haben einen kommutativen Ring mit Eins, und wenn sich ein Inverses findet, dann ist es das einzige. Klar.
Liebe Grüße
Immo
Hallo Andreas,
thanks a lot, daran hab ich überhaupt nicht mehr gedacht. So geht es natürlich noch viel besser, und damit wäre wohl auch geklärt, wie ein Testkandidat vermutlich diese Aufgabe lösen soll:
Problem: 79999 mod 1000 = ?
Lösung:
1000 = 23 · 53 ⇒ φ(1000) = 23 – 1 (2 – 1) · 53 – 1 · (5 – 1) = 4 · 1 · 25 · 4 = 400
Wegen gcd(7, 1000) = 1 ist der Satz von Euler-Fermat anwendbar und er sagt 7400 = 1 (mod 1000). Mithin ist auch 710000 = 1 (mod 1000), weil 10000 ein ganzzahliges Vielfaches von 400 ist.
Andererseits ist 710000 = 79999 · 7 und das bedeutet, dass 79999 das (mod 1000)-Inverse zu 7 ist, welches sich mit dem erweiterten euklidischen Algorithmus zu 143 ergibt.
Ergebnis: 79999 mod 1000 = 143.
Und wie man sich schnell überlegen kann, trifft das Ergebnis sogar für alle Exponenten mit beliebig vielen Neunen zu, solange es vier oder mehr sind. Es ist also z. B. auch
79999999999999999 mod 1000 = 143.
Gruß
Martin