Ergebnis mittels modulo Primfaktoren und chinesischer Restsatz

12.01.2015, 11:31

smtc

Ergebnis mittels modulo Primfaktoren und chinesischer Restsatz

Meine Frage:
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 $\begin{eqnarray*} \end{eqnarray*}$
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

Zitat:

Original von smtc
Problem 1: weder 4 noch 9 noch 25 sind Primfaktoren, sondern Quadrate von Primfaktoren.
Problem 2: ja wie geht denn das jetzt?

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
$\begin{eqnarray*} 2^{31} mod 4 = 0 2^{31} mod 9 = 2 2^{31} mod 25 = 23 \end{eqnarray*}$

Meine Vermutung ist, dass ich ja dann so weitermachen muss:
$\begin{eqnarray*} x \equiv 0 mod 2 x \equiv 2 mod 3 x \equiv 3 mod 5 \end{eqnarray*}$

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

Zitat:

Original von smtc
In der Angabe (bzw im Angabenzusatz) steht allerdings, dass ich modulo der Primfaktoren rechnen soll).

Das solltest du nicht so ernst nehmen. Es ist definitiv das gemeint, was du hier anfängst zu tun:

Zitat:

Original von smtc
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
$\begin{eqnarray*} 2^{31} mod 4 = 0 2^{31} mod 9 = 2 2^{31} mod 25 = 23 \end{eqnarray*}$

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

$\begin{align*} x = 0 \pmod 4, x=2 \pmod 9, x=23=-2 \pmod{25} \end{align*}$

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. Hammer

Also, dann schreib ich mir das so auf:
$\begin{eqnarray*} x \equiv 0 mod 4 x \equiv 2 mod 9 x\equiv -2 mod 25 \end{eqnarray*}$
So, daraus mach ich dann
$\begin{eqnarray*} x=0 \cdot 9 \cdot 25 \cdot a + 2 \cdot 4 \cdot 25 \cdot b + (-2) \cdot 4 \cdot 9 \cdot c \end{eqnarray*}$

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.

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! Big Laugh

Neue Frage »

Antworten »

Ergebnis mittels modulo Primfaktoren und chinesischer Restsatz

Verwandte Themen