Ganzzahlige Lösungen einer Funktion |
24.09.2009, 15:57 | tman | Auf diesen Beitrag antworten » | ||
Ganzzahlige Lösungen einer Funktion Wenn ich bspw. die Funktion f(x) = (7^x - 11) / 23 habe, wie bekomme ich dann heraus für welche ganzzahligen x mein f(x) ebenfalls ganzzahlig ist? Ich weiß, dass dies das erste mal für x = 19 gilt. Dann ist nämlich f(x) = 495604138494484. Allerdings weiß ich das nur durch Ausprobieren. Wie kann man so etwas mathematisch Lösen? Gibt es überhaupt eine Art mathematische Formel, die ausdrückt, dass eine Zahl ganzzahlig ist? Vielen Dank! |
||||
24.09.2009, 16:10 | Mazze | Auf diesen Beitrag antworten » | ||
Ertsmal ist klar das nur für natürliche x ganzzahlig, da 7 eine Primzahl ist. Klar ist dann auch dass nur ganzzahlig ist wenn x eine natürliche Zahl ist (mit 0). Das Ganze resultiert dann in der Frage wann durch 23 Teilbar ist. Das gehört dann ins Gebiet der Zahlentheorie. Das Problem lässt sich dann wie folgt Formulieren : dies lässt sich mit Hilfe der Kongruenz schreiben : Aber hier hören meine Zahlentheoretischen Kentnisse auf, allerdings gibt es hier im Board User die sich da besser auskennen . |
||||
24.09.2009, 16:17 | tmo | Auf diesen Beitrag antworten » | ||
Systematisches Probieren: Betrachte Es ist Daraus folgt . Insbesondere also . Also ist , woraus die Ganzzahligkeit von folgt. Insgesamt kann man folgern: |
||||
24.09.2009, 17:02 | tman | Auf diesen Beitrag antworten » | ||
Vielen Dank erstmal für die schnellen Antworten! Also wie es aussieht kann ich also algebraisch / zahlentheoretisch meine Fälle, die ich testen muss einschränken, aber ganz kommt man um das Testen nicht herum... Ich war natürlich daran interessiert, wie man sowas komplett ohne Ausprobieren löst :-( Also wenn noch einer eine Idee hat, wäre ich dankbar. Ansonsten geht es wohl einfach nicht... (??) |
||||
24.09.2009, 17:25 | AD | Auf diesen Beitrag antworten » | ||
Der kleine Fermat besagt ja vorab , also hält sich das mit dem Probieren noch in erträglichen Grenzen. |
||||
24.09.2009, 17:30 | tman | Auf diesen Beitrag antworten » | ||
Naja, zumindest solang meine Primzahl erträglich klein ist ;-) |
||||
Anzeige | ||||
|
||||
24.09.2009, 18:26 | AD | Auf diesen Beitrag antworten » | ||
Naja, zum einen musst du wegen für (ob + oder -, hängt von den konkreten ab) nur maximal bis zur Hälfte gehen - siehe oben, genauso hat es tmo gemacht - zum anderen gibt es für größere dann ja auch noch Kollege Computer. |
||||
24.09.2009, 21:31 | Mystic | Auf diesen Beitrag antworten » | ||
Nur halt dass für mehrhunderstellige p auch der Computer keine Chance mehr hat... Immerhin geht es dabei um das Problem des diskreten Logarithmus (DLP) welches das "schwierige mathematische Problem" hinter vielen kryptographischen Verfahren ist, in ähnlicher Weise wie das Faktorisierungsproblem großer ganzer Zahlen hinter RSA... Obiger Link gibt wieder mal in vorbildlicher Weiser Auskunft über die gängigsten Algorithmen zur Lösung, wobei die Index-Calculus Methode der mit Abstand beste ist... |
||||
24.09.2009, 21:40 | AD | Auf diesen Beitrag antworten » | ||
An derartige Übertreibungen hatte ich auch nicht mehr gedacht. |
||||
24.09.2009, 21:58 | Mystic | Auf diesen Beitrag antworten » | ||
Ist jetzt nicht wirklich eine Übertreibung... DLP's mit etwa 100-stelligem p sollten für Computer kein Problem darstellen, bei etwa 200-stelligem p liegt etwa z.Z. die Grenze des Machbaren, während in der Kryptographie für diese Zwecke dann Primzahlen p mit mehr als 300 Stellen verwendet werden... |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |
|