Geradengleichung in ℕ mit quadratischen Funktionswerten?
Neulig kam in Gesellschaft folgende Frage auf:
Sei g(x) = m • x + b gegeben mit m und b ∈ ℕ.
Gesucht sind Werte für x ∈ ℕ, so dass der Funktionswert g(x) eine Quadratzahl ist.
Oder anders geschrieben:
m • x + b = c2. mit m, x, b, c ∈ ℕ
Mit Ausprobieren könnte ich da natürlich Paare finden, aber gibt es dafür bessere Lösungsmöglichkeiten? Meine Mathekenntnisse helfen mir nicht weiter. Hat jemand einen Tipp? In Zahlentheorie bin ich eine Niete. Daher komme ich nur bis zum Thema Restklassen, ohne eine Idee damit zu haben, wie man da weiterkommt.
2 Antworten
Wie bereits geschrieben wurde, kann man die Gleichung umformen zu:
Wenn nun c, b und m natürlich sind, dann ist x exakt dann ganzzahlig, wenn c² - b ein Vielfaches von m ist. Oder anders ausgedrückt:
Die Theorie, um solche modulare quadratische Gleichungen zu lösen, ist leider etwas kompliziert. Falls du dich davon nicht abschrecken lässt:
Falls m eine ungerade Primzahl ist:
Wenn m eine ungerade Primzahl ist, kann man mithilfe des eulerschen Kriteriums prüfen, ob die Gleichung überhaupt eine Lösung besitzt.
Falls es eine Lösung c gibt, dann ist auch -c eine Lösung. Im Restklassenring modulo m sind das dann die einzigen beiden Lösungen der Gleichung.
Beispiel: Die Gleichung
hat in Z_3 exakt die beiden Lösungen c = 1 und c = -1 = 2.
Einschub: Weil uns aber nicht modulare Lösungen interessieren, sondern natürliche Lösungen, sollten wir uns an dieser Stelle klar machen, dass man so eine Lösung c liften kann: Mit c ist auch c + m, c + 2m, c + 3m etc eine Lösung der Gleichung.
Preisfrage: Wenn es eine Lösung für c gibt, wie findet man sie? Tja, hier geht's leider schon los. Für gewisse Primzahlen m sind Formeln dafür bekannt. Zum Beispiel wenn
ist, dann erhält man eine Lösung mittels
(Falls es dich interessiert: Es gibt auch Formeln für den Fall m = 5 mod 8).
Im Allgemeinen ist aber keine Formel zum Ermitteln eines quadratischen Rests bekannt, selbst bei dem einfachen Fall, dass m eine Primzahl ist. Somit bleibt dir schlimmstenfalls nur "ausprobieren".
Falls m keine Primzahl ist:
Wie du dir vorstellen kannst, wird es hier nicht einfacher ;) Ich verweise mal abkürzend auf folgendes Skript, für welches obiges Wissen vorausgesetzt wird.
https://www.uvm.edu/~cvincen1/files/teaching/spring2017-math255/quadraticequation.pdf
Beachte, dass der Ausdruck
in diesem Skript nicht für den Bruch a/b steht, sondern für das Legendre-Symbol.
Kein Thema.
Vielleicht als kleine Ergänzung: Wenn du dich nicht für den Rechenweg interessierst, kannst du die modulare Gleichung einfach in einen Rechner wie Wolframalpha eintippen und erhältst die möglichen Lösungen für c - vorausgesetzt die Zahlen sind handhabbar genug um nicht die benötigte Rechenleistung zu sprengen ;)
Du weißt doch, dass bei
y=mx+b
alle y Quadratzahlen sind. Wenn du jetzt umformst, kommst du auf
x=(y–b)/m
Da b und m gegeben sind und du für y alle Quadratzahlen durchgehen kannst, hast du alle x gefunden, also
x=(1–b)/m
x=(4–b)/m
x=(9–b)/m
usw.
Man kann alle x auch als Menge schreiben:
{x∈ℕ: x=(c²–b)/m, c∈ℕ}
Sei dir aber bewusst, dass du nicht zu jeder Quadratzahl ein x finden kannst.
Ich suche auch keine Gerade sondern Paare (x, c), für die die Geradengleichung passt.
War ich zu undeutlich? Dachte, dass ich das sauber beschrieben habe, dass ich die Stellen x suche, wo der Funktionswert eine Quadratzahl ist.
Ich suche für gegebenen m und b nur die Stellen x, keine Gleichung.
Noch einmal, ich suche keine Geradengleichung sondern Wertepaare, die eine gegebene Geradengleichung erfüllen mit einer Quadratzahl als Funktionswert.
Das hat nichts mit Funktionsgleichungen sondern wie angegeben vermutlich was mit Zahlentheorie zu tun.
Für beispielsweise f(x) = 2 • x + 5 ist das noch trivial. Da finde ich schnell im Kopf viele Werte für x, beispielsweise 2, 10, 22, 38, 58, 82, ...
Und wenn nun m = 4711 und b = 7411 ist, wie finde ich dann die x, ohne zu suchen?
In meiner Frage hatte ich mit "Mit Ausprobieren könnte ich da natürlich Paare finden" eine Suche selbst schon angegeben, aber explizit nicht nach Suche sondern Berechung gefragt.
Dann kannst kannst du m und b einsetzen.
x = (c² – 7411) / 7411
Für jedes natürliche c hast du dann ein x, für das der rechte Ausdruck auch natürlich ist.
Der rechte Ausdruck ist immer dann natürlich, wenn m ein Teiler von c²–b ist. Das liegt aber nicht nur an m und b, sondern auch an c, also musst du es jedes Mal prüfen bzw. prüfen lassen. (Taschrechner).
Ich danke dir für die ausführliche Antwort.
Bin noch nicht in die Tiefe gegangen, denke aber, dass ich das aufgrund deiner Beschreibung hinbekomme.