Polynomkongruenz < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | | Hat die Kongruenz [mm] 28*x^6+28*x^4-8*x^3+7*x^2-4*x-22\equiv [/mm] 0 mod(1591) eine Lösung? |
Hallo hallo!
Ich versuche gerade mit den Mitteln aus unserer Vorlesung diese Aufgabe zu lösen. Alles was mir jedoch dazu einfällt ist:
[mm] 28*x^6+28*x^4-8*x^3+7*x^2-4*x-22\equiv [/mm] 0 mod(1591)
[mm] \gdw
[/mm]
[mm] 28*x^6+28*x^4-8*x^3+7*x^2-4*x-22\equiv [/mm] 0 mod(37)
[mm] 28*x^6+28*x^4-8*x^3+7*x^2-4*x-22\equiv [/mm] 0 mod(43)
wegen 1591=37*43
und: Wenn eine von den letzten beiden Gleichungen keine Lösung besitzt, dann besitzt auch die erste keine.
Mehr hatten wir nicht zu Polynomkongruenzen vom Grad größer als 3. Gibt es da noch ein paar Tricks oder Herangehensweisen von denen man wissen sollte? Oder soll ich jetzt stupide Restklassen modulo 37 und 43 einsetzen. Glaub ich nicht.
Freue mich über Anregung
Gruß, kulli
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 21:48 Sa 13.07.2013 | | Autor: | felixf |
Moin!
> Hat die Kongruenz [mm]28*x^6+28*x^4-8*x^3+7*x^2-4*x-22\equiv[/mm] 0
> mod(1591) eine Lösung?
>
> Ich versuche gerade mit den Mitteln aus unserer Vorlesung
> diese Aufgabe zu lösen. Alles was mir jedoch dazu
> einfällt ist:
>
> [mm]28*x^6+28*x^4-8*x^3+7*x^2-4*x-22\equiv[/mm] 0 mod(1591)
>
> [mm]\gdw[/mm]
>
> [mm]28*x^6+28*x^4-8*x^3+7*x^2-4*x-22\equiv[/mm] 0 mod(37)
> [mm]28*x^6+28*x^4-8*x^3+7*x^2-4*x-22\equiv[/mm] 0 mod(43)
>
> wegen 1591=37*43
Genau, das ist der chinesische Restsatz.
> und: Wenn eine von den letzten beiden Gleichungen keine
> Lösung besitzt, dann besitzt auch die erste keine.
![[ok]](/images/smileys/ok.gif "[ok]")
> Mehr hatten wir nicht zu Polynomkongruenzen vom Grad
> größer als 3. Gibt es da noch ein paar Tricks oder
> Herangehensweisen von denen man wissen sollte? Oder soll
> ich jetzt stupide Restklassen modulo 37 und 43 einsetzen.
> Glaub ich nicht.
Wenn ihr irgendwelche Faktorisierungsalgorithmen hattet fuer Polynome ueber endlichen Koerpern, kannst du die hier mal anwenden. Alternativ kannst du mit [mm] $ggT(X^q [/mm] - X, f) [mm] \neq [/mm] 1$ testen, ob $f [mm] \in \IF_q[X]$ [/mm] eine Nullstelle in [mm] $\IF_q$ [/mm] hat (dazu braucht man ein wenig Wissen ueber endliche Koerper).
Oder du probierst halt (am besten mit einem Computer) alle Restklassen aus, wie du schon schriebst. Ist nicht spannend (lass es den Computer machen!), fuehrt hier aber zum Ziel. (Dann haette man aber auch genauso gut bis 1591 hochgehen koennen...)
(Tipp: modulo 43 gibt es keine Nullstelle, modulo 37 dagegen drei.)
LG Felix
|
|
|
| |
|
> Moin!
>
> > Hat die Kongruenz [mm]28*x^6+28*x^4-8*x^3+7*x^2-4*x-22\equiv[/mm] 0
> > mod(1591) eine Lösung?
> >
> > Ich versuche gerade mit den Mitteln aus unserer Vorlesung
> > diese Aufgabe zu lösen. Alles was mir jedoch dazu
> > einfällt ist:
> >
> > [mm]28*x^6+28*x^4-8*x^3+7*x^2-4*x-22\equiv[/mm] 0 mod(1591)
> >
> > [mm]\gdw[/mm]
> >
> > [mm]28*x^6+28*x^4-8*x^3+7*x^2-4*x-22\equiv[/mm] 0 mod(37)
> > [mm]28*x^6+28*x^4-8*x^3+7*x^2-4*x-22\equiv[/mm] 0 mod(43)
> >
> > wegen 1591=37*43
>
> Genau, das ist der chinesische Restsatz.
>
> > und: Wenn eine von den letzten beiden Gleichungen keine
> > Lösung besitzt, dann besitzt auch die erste keine.
>
>
>
> > Mehr hatten wir nicht zu Polynomkongruenzen vom Grad
> > größer als 3. Gibt es da noch ein paar Tricks oder
> > Herangehensweisen von denen man wissen sollte? Oder soll
> > ich jetzt stupide Restklassen modulo 37 und 43 einsetzen.
> > Glaub ich nicht.
>
> Wenn ihr irgendwelche Faktorisierungsalgorithmen hattet
> fuer Polynome ueber endlichen Koerpern, kannst du die hier
> mal anwenden. Alternativ kannst du mit [mm]ggT(X^q - X, f) \neq 1[/mm]
> testen, ob [mm]f \in \IF_q[X][/mm] eine Nullstelle in [mm]\IF_q[/mm] hat
> (dazu braucht man ein wenig Wissen ueber endliche
> Koerper).
>
> Oder du probierst halt (am besten mit einem Computer) alle
> Restklassen aus, wie du schon schriebst. Ist nicht spannend
> (lass es den Computer machen!), fuehrt hier aber zum Ziel.
> (Dann haette man aber auch genauso gut bis 1591 hochgehen
> koennen...)
>
> (Tipp: modulo 43 gibt es keine Nullstelle, modulo 37
> dagegen drei.)
>
> LG Felix
>
Moin moin, das ist leider eine Aufgabe aus der Probeklausur. Also ist nichts mit Computer oder Taschenrechner :(
Was ich noch in meinen Unterlagen gefunden habe ist folgendes Lemma:
Sei [mm] a\in\IZ [/mm] und [mm] f\in\IZ[x]. [/mm] Dann existiert ein [mm] q\in\IZ[x] [/mm] so dass gilt:
f(x)-f(a)=(x-a)*q(x) und Grad(q)=Grad(f)-1
Alles andere darf man ja wie immer nicht verwenden. Ich kann mir aber auch vorstellen dass wir das mit einsetzen raus finden sollen. Der Prof scheut leider keine langen sinnlosen Rechnereien.
Falls dir noch was in Verbindung mit dem Lemma einfällt lass es mich wissen :)
Ansonsten Danke, vielleicht gibts ja noch eine Musterlösung.
Gruß, kulli
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:02 So 14.07.2013 | | Autor: | felixf |
Moin!
> > Wenn ihr irgendwelche Faktorisierungsalgorithmen hattet
> > fuer Polynome ueber endlichen Koerpern, kannst du die hier
> > mal anwenden. Alternativ kannst du mit [mm]ggT(X^q - X, f) \neq 1[/mm]
> > testen, ob [mm]f \in \IF_q[X][/mm] eine Nullstelle in [mm]\IF_q[/mm] hat
> > (dazu braucht man ein wenig Wissen ueber endliche
> > Koerper).
>
> Moin moin, das ist leider eine Aufgabe aus der
> Probeklausur. Also ist nichts mit Computer oder
> Taschenrechner :(
>
> Was ich noch in meinen Unterlagen gefunden habe ist
> folgendes Lemma:
>
> Sei [mm]a\in\IZ[/mm] und [mm]f\in\IZ[x].[/mm] Dann existiert ein [mm]q\in\IZ[x][/mm]
> so dass gilt:
>
> f(x)-f(a)=(x-a)*q(x) und Grad(q)=Grad(f)-1
Ich glaub das bringt hier nichts.
> Alles andere darf man ja wie immer nicht verwenden. Ich
> kann mir aber auch vorstellen dass wir das mit einsetzen
> raus finden sollen. Der Prof scheut leider keine langen
> sinnlosen Rechnereien.
Hmm, unschoen.
Am wenigsten Rechnerei ist vermutlich die Berechnung von [mm] $ggT(X^p [/mm] - X, f)$ fuer $p = 37$ und $p = 43$, wenn du binaere Exponentiation verwendest. (Dazu musst du aber ein Minimalwissen ueber endliche Koerper haben: [mm] $X^p [/mm] - X$ hat genau alle Elemente aus [mm] $\IZ/p\IZ [/mm] = [mm] \IF_p$ [/mm] als Nullstelle.) Ekelig ist es aber trotzdem.
> Ansonsten Danke, vielleicht gibts ja noch eine
> Musterlösung.
Wenn es eine gibt, schreib doch bitte was man laut der machen soll. Ich bin da echt gespannt...
LG Felix
|
|
|
| |
|
So hier die Lösung zu [mm] 28*x^6+28*x^4-8*x^3-4*x-22\equiv [/mm] 0 mod(1591):
[mm] 28*x^6+28*x^4-8*x^3-4*x-22
[/mm]
[mm] =7*(2*x^3+x)^2-4*(2*x^3+x)-22
[/mm]
Substitution [mm] y=2*x^3+x
[/mm]
[mm] 7*y^2-4*y-22 \equiv [/mm] 0 mod(1591) [mm] \gdw
[/mm]
[mm] 7^2*y^2-4*7*y-22*7\equiv [/mm] 0 mod(1591) [mm] \gdw
[/mm]
[mm] (7y-2)^2-158\equiv [/mm] 0 mod(1591) [mm] \gdw
[/mm]
[mm] z^2\equiv [/mm] 158 mod(1591)
also muss man nur noch das Jacobi Symbol [mm] (\bruch{158}{1591}) [/mm] berechnen und das ist negativ.
Sehr schön der Lösungsweg!
Gruß, kulli
|
|
|
|
