Exponent herausfinden

Neue Frage »

Adramelec Auf diesen Beitrag antworten »
Exponent herausfinden
Hallo, folgende Aufgabe:

Bestimmen Sie x. (Ansatz über Primfaktorenzerlegung des Modulus)

Okay, ich habe mal den Modulus mal in die Primfaktoren zerlegt:
1155 = 3, 5, 7, 11.

Aufgrund von Lösung von Wolframalpha, weiß ich bereits das x = 43 ist.
Ich weiß das 43 eine Primzahl ist. Also kann die 43 nicht mit den Primfaktoren zusammenhängen?
Ich weiß daher überhaupt nicht, inwiefern mir hier die Primfaktorenzerlegung weiterhelfen sollte.

Da wir auch gerade den Satz von Euler u.s.w. kennen lernten, könnte ich mir vorstellen, dass es zusätzlich mit dem auch zusammenhängt. Es ergibt sich für mich aber keinen unmittelbaren Hinweis.

Danke!
HAL 9000 Auf diesen Beitrag antworten »
RE: Exponent herausfinden
Zitat:
Original von Adramelec
Okay, ich habe mal den Modulus mal in die Primfaktoren zerlegt:
1155 = 3, 5, 7, 11.

Ja und? Warum machst du hier dann nicht konsequent weiter? Damit ist die Ausgangskongruenz äquivalent zum simultanen Bestehen der vier Kongruenzen




.

Aus den vier Einzellösungen kannst du dann via Chinesischen Restsatz die Lösung(en) der Originalkongruenz wieder zusammenbasteln.

Zitat:
Original von Adramelec
Aufgrund von Lösung von Wolframalpha, weiß ich bereits das x = 43 ist.

Diese Angabe ist nicht exakt - vollständig lautet die Lösung .
Adramelec Auf diesen Beitrag antworten »

Ah ok smile

Nur um das für mich nochmal zusammenzufassen:
Die ursprüngliche Aufgabenstellung entspricht den 4 Kongruenzen:



Aber wie ich den chinesischen Restsatz nun anwende ist mir nicht klar. Ich kenne das nur, wenn auf der linken Seite nur x steht. Also wie ich daraus auf 43 mod 60 komme, weiß ich nicht?
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von Adramelec
Aber wie ich den chinesischen Restsatz nun anwende ist mir nicht klar. Ich kenne das nur, wenn auf der linken Seite nur x steht.

Oje, dir muss man wirklich auch jeden Schritt erklären. Du musst natürlich vorher diese vier Einzelkongruenzen für sowie die oben ermittelten zugehörigen -Werte lösen! Das kann man leicht "von Hand":

Rechne schlicht die Werte für aus bis du wieder bei Wert 1 angelangt bist, der zugehörige x-Wert ist die Periodenlänge der Lösung. Laut Kleinem Fermat gilt , also wird hier bei deinen Werten die Liste nicht allzu lang.

Merke dir außerdem die Position mit (sollte es keine geben, dann hat die Gesamtkongruenz keine Lösung). Dann ist die Lösung von einfach .

Zitat:
Original von Adramelec

Die von mir genannten Werte hast du hiermit berechnet, die sind in der Reihenfolge 1,3,1,3. Fehlen noch die , die sind (überprüf das selbst) ebenfalls in der Reihenfolge 2,4,3,10.

Es ist also das Kongruenzsystem



zu lösen. Und das geht ganz schnell: Die erste Kongruenz gilt automatisch, wenn die zweite erfüllt ist. Aus jener sowie der letzten folgt zusammen , also . Die noch verbliebene Bedingung ergibt , insgesamt daher .
Adramelec Auf diesen Beitrag antworten »

Sorry, ich bin gerade etwas kränklich und kann daher nur langsam die Dinge aufarbeiten.

Danke für deine Hilfe! Mit der ausführlichen Erklärung habe ichs nun endlich auch verstanden Gott
Adramelec Auf diesen Beitrag antworten »

Ich muss nochmal nachfragen, ein Studienkollege hat das Beispiel mit folgenden Kongruenzen gelöst:



Mittels chinesischen Restsatz kommt 883 mod 1155. Das ist ja auch eine Lösung. Funktioniert das immer oder ist das nur Zufall?
Denn falls das funktioniert, um eine Lösung zu eruieren erspart man sich einen Schritt, richtig?

Danke!
 
 
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von Adramelec
Ich muss nochmal nachfragen, ein Studienkollege hat das Beispiel mit folgenden Kongruenzen gelöst:

Mit das Beispiel meinst du aber nicht das obige Beispiel, oder? verwirrt

Falls doch: mag eine Lösung sein, weil zufällig gerade gilt.

Aber es sind gewiss nicht alle mit Lösung deiner Original-Kongruenz, nehmen wir beispielsweise :

Nachrechnen ergibt statt 338. unglücklich

Zitat:
Original von Adramelec
Mit der ausführlichen Erklärung habe ichs nun endlich auch verstanden

Anscheinend nicht, sonst wärst du jetzt nicht mit dieser vermeintlichen "Abkürzung", die meiner Erklärung oben klar widerspricht, angekommen. unglücklich
Adramelec Auf diesen Beitrag antworten »

Danke für die Erklärung :-)
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »