Ganzzahlige Lösungen einer Funktion

Neue Frage »

tman Auf diesen Beitrag antworten »
Ganzzahlige Lösungen einer Funktion
Hallo!

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!
Mazze Auf diesen Beitrag antworten »

Zitat:
Gibt es überhaupt eine Art mathematische Formel, die ausdrückt, dass eine Zahl ganzzahlig ist?


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 Augenzwinkern .
 
 
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:

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... (??)
AD Auf diesen Beitrag antworten »

Der kleine Fermat besagt ja vorab , also hält sich das mit dem Probieren noch in erträglichen Grenzen. Augenzwinkern
tman Auf diesen Beitrag antworten »

Naja, zumindest solang meine Primzahl erträglich klein ist ;-)
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. Augenzwinkern
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...
AD Auf diesen Beitrag antworten »

Zitat:
Original von Mystic
Nur halt dass für mehrhunderstellige p auch der Computer keine Chance mehr hat...

An derartige Übertreibungen hatte ich auch nicht mehr gedacht. Augenzwinkern
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...
Neue Frage »
Antworten »



Verwandte Themen

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