Wie berechne ich den Rest von 3^2012 / 7 ?

Wissenschaft Mathematik
#1

Ist es sinnvolL zuerst die Potenz zu berechnen ?
Mit den Potenzgesetzen komme ich so weit:

3^2012= 3^2000 * 3^12= 3^2000 * 531441…
…wie kann ich die 2000 so aufspalten, dass ich den Exponenten mit dem TRS aus rechnen kann ?

Ich habe mir überlegt, dass die Potzen eine ziemlich lange Zahl ergibt, die ich möglicherweise erst garnich brauch, um den Rest zu berechnen, oder ?! Kennt jemand einen Weg dafür?
Vllt. wie man nur die letzten beiden Ziffern der Potenz berechnen kann ?

Die letzte Ziffer ist (denke ich mal) eine 3, weil die Potenz eine Periode von 4 hat: 3;9;7;1;3;9;7;1;3;9;7;1;…
und da 2012:4=503 ist, ist die letzte Ziffer eine 3. Ist das denn überhaupt richtig?’

Vielen Dank im Voraus (:

#2

Ist es sinnvolL zuerst die Potenz zu berechnen ?

Nein.

Aber ist das zufällig eine Wettbewerbsaufgabe oder etwas in der Art? Darauf würde zumindest die 2012 hinweisen, die Jahreszahl wird dabei ja gerne benutzt.

Ansonsten eine kleine Anregung:
ab mod m = ((a mod m) * (b mod m)) mod m
Das würde ich jedenfalls in Java benutzen…

Die letzte Ziffer ist (denke ich mal) eine 3, weil die Potenz eine Periode von 4 hat: 3;9;7;1;3;9;7;1;3;9;7;1;…
und da 2012:4=503 ist, ist die letzte Ziffer eine 3. Ist das denn überhaupt richtig?’

Die Argumentation verstehe ich nicht…
Die Potenz hat eine Periode von 4? Bezüglich ihrer Nachkommastelle?
Aber wieso rechnest du 2012/4?

mfg,
Ché Netzer

#3

Hallo Ben,

du kannst Verfahren wie Square&Multiply oder ähnliche benutzen um weniger Multiplikationen durchführen zu müssen. Zumal kannst du nach jedem Schritt modulo 7 reduzieren. Als Beispiel hier:
Zunächst gilt ja:

3^{2012} = 3^{1024+512+256+128+64+16+8+4}

Dann berechnen wir mal die Potenzen, die wir brauchen, habs mal ausführlich hingeschrieben.

3^2 \equiv 9 \equiv 2 \textrm{ (mod 7)}

3^4 \equiv (3^2)^2 \equiv 2^2 \equiv 4 \textrm{ (mod 7)}

3^8 \equiv 4^2 \equiv 2 \textrm{ (mod 7)}

3^{16} \equiv 2^2 \equiv 4 \textrm{ (mod 7)}

3^{32} \equiv 4^2 \equiv 2 \textrm{ (mod 7)}

3^{64} \equiv 2^2 \equiv 4 \textrm{ (mod 7)}

3^{128} \equiv 4^2 \equiv 2 \textrm{ (mod 7)}

3^{256} \equiv 2^2 \equiv 4 \textrm{ (mod 7)}

3^{512} \equiv 4^2 \equiv 2 \textrm{ (mod 7)}

3^{1024} \equiv 2^2 \equiv 4 \textrm{ (mod 7)}

So jetzt können wir alles wieder zusammensetzen.

3^{2012} \equiv 3^{1024+512+256+128+64+16+8+4} \equiv
4 * 2 * 4 * 2 * 4 * 4 * 2 * 4 \textrm{ (mod 7)}

\equiv (2^3)^4 * 2 \equiv 1*2 \equiv 2 \textrm{ (mod 7)}

Puh, das war viel getexe…

Gruß
Sven

#4

3^2 \equiv 9 \equiv 2

Dies Aussage überrascht dann doch sehr … :wink:

#5

Du hast das „mod 7“ nicht mit zitiert.

Der Rest der Division von 9 durch 7 ist 2, ist schon richtig.

#6

Hallo,

Ist es sinnvolL zuerst die Potenz zu berechnen ?

nein.

…wie kann ich die 2000 so aufspalten, dass ich den
Exponenten mit dem TRS aus rechnen kann ?

Du musst weder den Exponenten 2012 ausrechnen, denn der ist ja bekannt, noch die Potenz. Du musst lediglich den Exponenten clever zerlegen, und zwar am besten in 2012 = irgendeine Primzahl + eine kleine Zahl. Die Primzahl hat den Grund, dass Du dann den sogenannten kleinen Fermatschen Satz anwenden kannst. Damit wird die Lösung zu einem Einzeiler.

Ich habe mir überlegt, dass die Potzen eine ziemlich lange Zahl ergibt,

Ja. Ein gewöhnlicher wissenschaftlicher Taschenrechner reicht übrigens, um herauszufinden, wie groß sie genau ist, und sogar, wie ihre ersten Ziffern lauten:

\log(3^{2012}) = 2012 \log(3) = 959.96796…

\Rightarrow\quad
3^{2012}
\approx 10^{959.96796}
= 10^{0.96796} \cdot 10^{959}
= 9.288 \cdot 10^{959}

32012 hat also exakt 960 Dezimalstellen und startet mit den Ziffern „9288“.

Vllt. wie man nur die letzten beiden Ziffern der Potenz
berechnen kann ?

Die letzten beiden Ziffern von 32012 sind natürlich 32012 mod 100, und das ist praktisch dieselbe Aufgabe, nur mit 100 statt 7. Aber die Kenntnis der letzten beiden Ziffern würde Dir überhaupt nichts nutzen, denn Du kannst leider nicht von „mod 100“ auf „mod 7“ schließen: 100, 1000 und 10000 enden zwar alle auf „00“, haben aber verschiedene 7-Divisionsreste, nämlich 2, 6 und 4.

Die letzte Ziffer ist (denke ich mal) eine 3, weil die Potenz
eine Periode von 4 hat: 3;9;7;1;3;9;7;1;3;9;7;1;…

Richtig, die Potenz hat diese Periode, aber deshalb ist die letzte Ziffer von 32012 nicht eine 3, sondern eine 1. Nicht so schlampig, bitteschön. Aber, wie gesagt, dieses Wissen hat keinen Nutzen.

Mach Dich über den kleinen Fermatschen Satz schlau und probier Dein Glück damit.

Gruß
Martin

#7

Hallo!

Du hast das „mod 7“ nicht mit zitiert.

Der Rest der Division von 9 durch 7 ist 2, ist schon richtig.

ich weiß. Aber so wie es dastand …

Richtig hätte es heißen müssen:

32 = 9; 9 mod 7 = 2

Aber der Einwand war ja auch nicht als Kritik gedacht, sondern als kleiner Scherz. Nix für Ungut! Michael

#8

ich weiß. Aber so wie es dastand …

Richtig hätte es heißen müssen:

32 = 9; 9 mod 7 = 2

So wie es dastand, war doch alles in Ordnung… Immerhin hat er ja keine Gleichheitszeichen benutzt: http://de.wikipedia.org/wiki/Kongruenz_%28Zahlentheo…

mfg,
Ché Netzer

#9

Hallo;

ich glaube, das war der Scherz. Immerhin ist 3² KONGRUENT 9 (nicht GLEICH) etwas seltsam.

mfG

#10

Du musst weder den Exponenten 2012 ausrechnen, denn der ist ja
bekannt, noch die Potenz. Du musst lediglich den Exponenten
clever zerlegen, und zwar am besten in 2012 = irgendeine
Primzahl + eine kleine Zahl. Die Primzahl hat den Grund, dass
Du dann den sogenannten kleinen Fermatschen Satz anwenden
kannst. Damit wird die Lösung zu einem Einzeiler.

Oh man. Da ist das was ich gemacht habe ja schon ziemlich blöd. Dein Weg ist viel schöner und kürzer. Über die Weihnachtsferien habe ich definitiv zu viel Analysis gelernt und Zahlentheorie vergessen. Gut, dass die Klausur erst im Februar ist :smile:

Allerdings doch wohl eher:
2012 = X*a + eine kleine Zahl
Wobei das X in besonderer Beziehung zum Modulus 7 steht, was der UP selbst herausfinden darf.
Oder übersehe ich wieder etwas?

Gruß
Sven

#11

Immerhin ist 3² KONGRUENT 9 (nicht GLEICH) etwas seltsam.

Nö, 3^2 liegt ja trivialerweise in der gleichen Äquivalenzklasse wie 9 in Z/7Z.
3^2 und 9 lassen bei Division durch 7 offensichtlich den gleichen Rest, damit sind sie kongruent.
Klar, ich hätte auch ganz links immer „=“ schreiben können. Aber wenn man immer „kongruent“ schreibt, dann schreibt man üblicherweise ganz rechts irgendwann mal hin bzgl was man modulo rechnet. Damit ist dann die ganze „Kongruenzkette“ gemeint.

Gruß
Sven

#12

Hallo!

Okay, mein Fehler. Ich kannte die drei Striche „≡“ bisher nur als das Zeichen für „identisch“. 3² ist identisch mit 9, aber 9 ist keinesfalls identisch mit 2.

Ich bin aber auch kein Zahlentheoretiker.

Sorry!
Michael

#13

Korrektur
Nochmal hallo,

und sorry, weil ich mich in einem Punkt selbst berichtigen muss:

Um den kleinen Satz von Fermat anwenden zu dürfen, darf man 2012 nicht gemäß „2012 = irgendeine Primzahl + eine kleine Zahl“ zerlegen, sondern muss das nach diesem Schema machen:

2012 = k · 7n + eine kleine Zahl

(k und n sind natürliche Zahlen.)

Danke an Attilius für den Hinweis auf meinen Irrtum.

Gruß
Martin