Lösbarkeit von Gleichungen in Z



  • Hallo

    Eine neuliche Übungsaufgabe war es, festzustellen, ob a5+7=b2 in Z lösbar ist.
    Nun, wenn die Gleichung in einem Restklassenring Z/mZ nicht lösbar ist, dann ist sie insb. auch nicht in Z lösbar (denn eine Lösung in Z wäre insb. eine Lösung in allen Restklassenringen).
    Ich war faul und habe ein kleines Program geschrieben, das versucht die Gleichung in kleinen Restklassenringen zu lösen. Mein Program gab aus, dass die Gleichung in Z/11Z (und allen vielfachen von 11) nicht lösbar sei.
    Kann man diese Zahl (11) auch algorithmisch ohne Durchprobieren ausrechnen?

    LG



  • Es ist 5 = (11-1)/2. Also ist a⁵ == +-1 (mod 11) nach dem Euler-Kriterium. Daher musst du nur ausrechnen, dass die Legendresymbole (6/11) und (8/11) gleich -1 sind.



  • ... und dass (7/11) = -1.



  • Gib mal eine Rückmeldung zu meinen AntWORD97en.



  • Kenner der Kongruenzen schrieb:

    Gib mal eine Rückmeldung zu meinen AntWORD97en.

    Danke für die Antworten. Wenn ich das richtig sehe, dann ist das ein geschickterer Ansatz fürs Probieren, aber letzten Endes doch nur Probieren.
    Ich meinte eher, ob es einen deterministischen Algorithmus gibt, der für ein gegebenes Polynom mit endlich vielen Variablen entscheidet, ob es Nullstellen in Z hat.
    In der Zwischenzeit habe ich herausgefunden, dass das allgemein nicht möglich ist.


Log in to reply