Ganzzahlige Lösungen einer Funktion

24.09.2009, 15:57

tman

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!

24.09.2009, 16:10

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 $\begin{eqnarray*} 7^x \end{eqnarray*}$ nur für natürliche x ganzzahlig, da 7 eine Primzahl ist. Klar ist dann auch dass $\begin{eqnarray*} 7^x - 11 \end{eqnarray*}$ nur ganzzahlig ist wenn x eine natürliche Zahl ist (mit 0). Das Ganze resultiert dann in der Frage wann

$\begin{eqnarray*} 7^n - 11 ~ n \in \mathbb{N} \end{eqnarray*}$

durch 23 Teilbar ist. Das gehört dann ins Gebiet der Zahlentheorie. Das Problem lässt sich dann wie folgt Formulieren :

$\begin{eqnarray*} 7^n - 11 \mod 23 = 0 \end{eqnarray*}$

dies lässt sich mit Hilfe der Kongruenz schreiben :

$\begin{eqnarray*} 7^n \equiv 11 \mod 23 \end{eqnarray*}$

Aber hier hören meine Zahlentheoretischen Kentnisse auf, allerdings gibt es hier im Board User die sich da besser auskennen Augenzwinkern

24.09.2009, 16:17

tmo

Auf diesen Beitrag antworten »

Systematisches Probieren:

Betrachte $\begin{eqnarray*} a_n = 7^n \mod 23 \end{eqnarray*}$

Es ist
$\begin{eqnarray*} a_1 = 7 a_2 = 3 a_3 = -2 a_4 = 9 a_5 = -6 a_6 = 4 a_7 = 5 a_8 = -11 a_9 = -8 a_{10} = -10 a_{11} = -1 a_{12} = -7 \end{eqnarray*}$

Daraus folgt $\begin{eqnarray*} a_n = - a_{n+11} \end{eqnarray*}$ .

Insbesondere also $\begin{eqnarray*} a_{19} = -a_8 = 11 \end{eqnarray*}$ .

Also ist $\begin{eqnarray*} 7^{19}-11 \equiv 0 \pmod {23} \end{eqnarray*}$ , woraus die Ganzzahligkeit von $\begin{eqnarray*} f(19) \end{eqnarray*}$ folgt.

Insgesamt kann man folgern:

$\begin{eqnarray*} a_{n+22} = - a_{n+11} = -(-a_n) = a_n \end{eqnarray*}$

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

Auf diesen Beitrag antworten »

Der kleine Fermat besagt ja vorab $\begin{eqnarray*} 7^{22} \equiv 1 \bmod 23 \end{eqnarray*}$ , also hält sich das mit dem Probieren noch in erträglichen Grenzen. Augenzwinkern

24.09.2009, 17:30

tman

Auf diesen Beitrag antworten »

Naja, zumindest solang meine Primzahl erträglich klein ist ;-)

24.09.2009, 18:26

Auf diesen Beitrag antworten »

Naja, zum einen musst du wegen

$\begin{eqnarray*} a^{\frac{p-1}{2}} \equiv \pm 1 \bmod p \end{eqnarray*}$ für $\begin{eqnarray*} p \nmid a \end{eqnarray*}$

(ob + oder -, hängt von den konkreten $\begin{eqnarray*} a,p \end{eqnarray*}$ ab) nur maximal bis zur Hälfte gehen - siehe oben, genauso hat es tmo gemacht - zum anderen gibt es für größere $\begin{eqnarray*} p \end{eqnarray*}$ dann ja auch noch Kollege Computer. Augenzwinkern

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

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

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

Neue Frage »

Antworten »

Ganzzahlige Lösungen einer Funktion

Verwandte Themen