Ergebnis mittels modulo Primfaktoren und chinesischer Restsatz |
12.01.2015, 11:31 | smtc | Auf diesen Beitrag antworten » | ||||
Ergebnis mittels modulo Primfaktoren und chinesischer Restsatz Guten Morgen! Folgendes Problem: Zu berechnen ist 2^31 mod 900. Hab ich gemacht indem ich 2^31 errechnet und dividiert habe. Diesem Ergebnid habe ich die Nachkommastellen abgezogen und diese Zahl wiederum mit 900 multipliziert und dann von 2^31 abgezogen. Als Ergebnis erhalte ich 848 Blöderweise habe ich übersehen, dass ich das ganze folgendermaßen lösen soll: Modulo der Primfaktoren (900=4*9*25) rechnen und das Ergebnis mit dem chinesischen Restsatz ermitteln. So und hier hängts mich aus. Problem 1: weder 4 noch 9 noch 25 sind Primfaktoren, sondern Quadrate von Primfaktoren. Problem 2: ja wie geht denn das jetzt? Ich glaube nicht dass das an sich so schwer ist, brauche aber jemanden der mich (mit viel Geduld und Verständnis für meine Doofheit) durch das Beispiel hindurchführt. Meine Ideen: Naja, hab mir mal gedacht ich rechne jeweils 2^32 mod 2,3 und 5 (weil das ja die echten Primfaktoren von 900 sind... Nehme an, dass die angegebenen Zahlen nur angegeben wurden um mir einen Rechenschritt zu ersparen). 2^31 mod 2= 0 2^31 mod 3= 2 2^31 mod 5= 3 Und jetzt suche ich doch ein x \equiv 0 mod 2 x \equiv 2 mod 3 x \equiv 3 mod 5 [/latex] Oder? Leider kann ich nicht behaupten, dass ich den chinesischen Restsatz ganz durchblickt habe aber ich bedanke mich schon mal für jegliche Hilfe! |
||||||
12.01.2015, 11:38 | tmo | Auf diesen Beitrag antworten » | ||||
RE: Ergebnis mittels modulo Primfaktoren und chinesischer Restsatz
Problem 1 ist kein Problem, denn für den chinesischen Restsatz müssen die Reste ja nur paarweise teilerfremd sind. Nirgends wird gefordert, dass es Primzahlen sind. Vielleicht erübrigt sich so ja auch Problem 2... |
||||||
12.01.2015, 12:10 | smtc | Auf diesen Beitrag antworten » | ||||
RE: Ergebnis mittels modulo Primfaktoren und chinesischer Restsatz In der Angabe (bzw im Angabenzusatz) steht allerdings, dass ich modulo der Primfaktoren rechnen soll). Allerdings komme ich ehrlich gesagt auch nicht weiter wenn ich mir das gsnze mit den Zahlen 4, 9 und 25 durcharbeite, da ich maximal bis hierher komme Meine Vermutung ist, dass ich ja dann so weitermachen muss: Und dann eben: 0* (3*5*x1)+2*(2*5*x2)+23*(2*3*x3) Wobei bei mod 4 die erste Klammer 1 und die anderen beiden 0 ergeben mod 9 die zweite Klammer 1 und die anderen beiden 0 ergeben mod 25 die dritte Klammer 1 und die anderen beiden 0 ergeben sollen Aber ich weiß erstens nicht ob das so stimmt und 2. komm ich nicht auf meine 848 ( was nahe legt dass es so nicht stimmt). |
||||||
12.01.2015, 12:21 | tmo | Auf diesen Beitrag antworten » | ||||
RE: Ergebnis mittels modulo Primfaktoren und chinesischer Restsatz
Das solltest du nicht so ernst nehmen. Es ist definitiv das gemeint, was du hier anfängst zu tun:
Das ist alles richtig bis jetzt. (Warum du dann wieder zu den Primzahlen 2,3,5 zurückkehrst weiß ich nicht....) Jetzt musst du mit dem chin. Restsatz also eine Zahl x finden, für die gilt. Und da kommt tatsächlich 848 raus, wie Wolfram Alpha verrät... |
||||||
12.01.2015, 15:40 | smtc | Auf diesen Beitrag antworten » | ||||
RE: Ergebnis mittels modulo Primfaktoren und chinesischer Restsatz Hui, danke mal so weit. Hm, ich schätze die Primzahlen habe ich dem Chaos in meinen Notizen zu verdanken. Entschuldige, das sollte natürlich nicht vorkommen. Also, dann schreib ich mir das so auf: So, daraus mach ich dann Die Berechnung von a spar ich mir mal, für b habe ich 5 erhalten, nur für c komme ich auf kein Ergebnis. :-/ |
||||||
12.01.2015, 16:38 | RavenOnJ | Auf diesen Beitrag antworten » | ||||
RE: Ergebnis mittels modulo Primfaktoren und chinesischer Restsatz Vielleicht arbeitest du mal dieses Beispiel durch. Mehr oder weniger ein Kochrezept, um Lösungen zu finden wie bei deiner Aufgabe. |
||||||
Anzeige | ||||||
|
||||||
12.01.2015, 17:39 | smtc | Auf diesen Beitrag antworten » | ||||
RE: Ergebnis mittels modulo Primfaktoren und chinesischer Restsatz Danke, schau ich mir gleich mal an. Zu dem was ich jetzt mit meinem Bsp gemacht hab: Ich ha einfach x=...=848 gesetzt und dann c herausgerechnet und erhalte dafür 2,111... . Das kommt mir doch ziemlich spanisch vor (mal davon abgesehen, dass ich ja offiziell noch nicht weiß, dass x=848 ist). |
||||||
12.01.2015, 18:44 | smtc | Auf diesen Beitrag antworten » | ||||
RE: Ergebnis mittels modulo Primfaktoren und chinesischer Restsatz Danke, RavenOnJ, es hat endlich funktioniert! Danke auch dir tmo für die Hilfe vorhin! |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
Die Neuesten » |