Zahlentheorie, loesen von Kongruenzen

05.12.2006, 22:26

liselotte28

Zahlentheorie, loesen von Kongruenzen

Hallo,
ich verstehe leider nur Bahnhof und muss aber noch eine Klausur schreiben....
Koennte mir jemand "fuer Dummis" erklaeren, wie ich Aufgaben wie die folgende loese?

x^3+x^2-4 kongruent 0 (mod 7^3)

Waere wirklich sehr, sehr dankbar!!!!

05.12.2006, 22:39

Auf diesen Beitrag antworten »

RE: Zahlentheorie, loesen von Kongruenzen
Schrittweise nach Primzahlpotenzmodulen lösen: Der Reihe nach

$\begin{eqnarray*} x^3+x^2-4 \equiv 0 \mod 7 \end{eqnarray*}$
$\begin{eqnarray*} x^3+x^2-4 \equiv 0 \mod 7^2 \end{eqnarray*}$
$\begin{eqnarray*} x^3+x^2-4 \equiv 0 \mod 7^3 \end{eqnarray*}$

lösen und immer das Ergebnis der vorherigen Stufe nutzen.

EDIT: Manchmal genügt schon die erste Stufe. Augenzwinkern

05.12.2006, 23:09

liselotte28

Auf diesen Beitrag antworten »

aber...
wenn ich x^3+x^2-4 kongruent (mod 7) mal versuche zu loesen, heißt das doch, ich setzte erstmal alle moeglichen Reste (0, 1, 2, 3, 4, 5, 6) fuer x ein und gucke, was rauskommt. Oder? Falls irgendwo 0 rauskommt, waere das die Loesung? Ich kriege aber keine 0 raus, also gibt es keine Loesung??

05.12.2006, 23:14

Auf diesen Beitrag antworten »

RE: aber...

Zitat:

Original von liselotte28
wenn ich x^3+x^2-4 kongruent (mod 7) mal versuche zu loesen, heißt das doch, ich setzte erstmal alle moeglichen Reste (0, 1, 2, 3, 4, 5, 6) fuer x ein und gucke, was rauskommt. Oder? Falls irgendwo 0 rauskommt, waere das die Loesung?

Das wäre die Lösung von $\begin{eqnarray*} x^3+x^2-4\equiv 0\mod 7 \end{eqnarray*}$ . Wenn das z.B. $\begin{eqnarray*} x\equiv a\mod 7 \end{eqnarray*}$ wäre, könntest du $\begin{eqnarray*} x=7y+a \end{eqnarray*}$ ansetzen, einsetzen und die nächste Gleichung $\begin{eqnarray*} x^3+x^2-4=(7y+a)^3+(7y+a)^2-4\equiv 0\mod 7^2 \end{eqnarray*}$ betrachten usw.

Zitat:

Original von liselotte28
Ich kriege aber keine 0 raus, also gibt es keine Loesung??

Ja, das ist das angenehme: Wenn $\begin{eqnarray*} x^3+x^2-4\equiv 0\mod 7 \end{eqnarray*}$ keine Lösung hat, dann natürlich auch nicht $\begin{eqnarray*} x^3+x^2-4\equiv 0\mod 7^3 \end{eqnarray*}$ . smile

05.12.2006, 23:25

liselotte28

Auf diesen Beitrag antworten »

ok
danke! Und noch eine Frage:
Wenn ich jetzt vor den x Zahlen stehen haette, die ein Vielfaches von 7 sind, koennte ich die dann einfach rausschmeißen und es bliebe -4 kongruent 0 (mod 7)? Was wieder bedeuten wuerde, es gibt keine Loesung?

05.12.2006, 23:29

Auf diesen Beitrag antworten »

RE: ok
Wenn du sowas wie z.B. $\begin{eqnarray*} 21x^3-14x^2-4\equiv 0\mod 7 \end{eqnarray*}$ meinst: Ja!

05.12.2006, 23:36

liselotte28

Auf diesen Beitrag antworten »

ja
meine ich. Dann habe ich es ja hoffentlich richtig gemacht!? Der analoge Versuch:
Jetzt habe ich die naechste Aufgabe (x^3+2x^2-1 kongruent 0 (mod2^3 3^2) in zwei Aufgaben geteilt und nach dem Einsetzen von x=1+2y (Lsg. bei mod 2) in die naechst hoehere Potenz (mod 2^2) raus: 2+14y+20y^2+8y^3 kongruent 0 (mod2^2). Jetzt kann ich da alles rausschmeißen, weil es durch 2 teilbar ist? Es gibt also wieder keine Lsg.? Oder was ist 0 kongruent 0 fuer eine Lsg.? Ich kann mir eigentlich nicht vorstellen, dass wir lauter Aufgaben ohne Lsg. bekommen.... )-:

05.12.2006, 23:43

Auf diesen Beitrag antworten »

RE: ja

Zitat:

Original von liselotte28
2+14y+20y^2+8y^3 kongruent 0 (mod2^2). Jetzt kann ich da alles rausschmeißen, weil es durch 2 teilbar ist? Es gibt also wieder keine Lsg.?

Erstens kannst du nicht alles rausschmeißen, weil es ja um modulo 2^2 geht, nicht nur um modulo 2. Was du machen kannst, ja machen solltest: Die gesamte Gleichung durch 2 teilen:

$\begin{eqnarray*} 2+14y+20y^2+8y^3 \equiv 0 \mod 2^2 \end{eqnarray*}$

ergibt nach Division durch 2

$\begin{eqnarray*} 1+7y+10y^2+4y^3 \equiv 1+y \equiv 0 \mod 2 \end{eqnarray*}$ .

Und zweitens: $\begin{eqnarray*} 0\equiv 0\mod 2 \end{eqnarray*}$ heißt, dass alle $\begin{eqnarray*} x \end{eqnarray*}$ Lösung sind!!!

05.12.2006, 23:54

liselotte28

Auf diesen Beitrag antworten »

oh - ach so
aber, wie komme ich auf 1+y?

05.12.2006, 23:56

Auf diesen Beitrag antworten »

$\begin{eqnarray*} 7\equiv 1\mod 2 \end{eqnarray*}$ , was denn sonst?

06.12.2006, 00:01

liselotte28

Auf diesen Beitrag antworten »

hä?
10y^2 und 4y^3 darf ich jetzt (doch) rausschmeißen?
Ich sagte doch, ich verstehe das nicht so ganz, aber so langsam wirds, hoffe ich. Ich versuche es mal weiter, x=1+y jetzt mit (mod 2^3). Mal sehen, wie lange es dauert, bis ich wieder was fragen muss...
Bevor du gleich nicht mehr da bist (weiß ich ja nicht) noch eben zur naechsten Aufgabe: x^3-52x-21 kongruent 0 (mod 5^3). Da habe ich jetzt fuer die reste 3 und 4 eine 0 raus. Wie kann das sein? Verrechnet??

06.12.2006, 00:03

Auf diesen Beitrag antworten »

RE: hä?
Wieso "hä" ???

$\begin{eqnarray*} 10\equiv 0\mod 2 \end{eqnarray*}$ , also $\begin{eqnarray*} 10y^2\equiv 0y^2=0\mod 2 \end{eqnarray*}$ .

$\begin{eqnarray*} 7\equiv 1\mod 2 \end{eqnarray*}$ , also $\begin{eqnarray*} 7y\equiv 1y=y\mod 2 \end{eqnarray*}$ , was ist daran denn "hä?" unglücklich

06.12.2006, 00:14

liselotte28

Auf diesen Beitrag antworten »

ach...
da jetzt gar nichts mehr, ich hab es verstanden, zumindest mit 10 und 4.
Vielleicht koenntest du mir aber noch sagen: 2+7y+5y^2+y^3 kongruent 0 (mod 2^3), kann ich da noch irgendwas machen? Ist das nun mein Ergebnis der ganzen Aufgabe?
Wobei ich nichtmal weiß, was mein Ergebnis auf die Aufgabe bezogen dann bedeuten soll... )-:

06.12.2006, 09:10

Auf diesen Beitrag antworten »

Bei $\begin{eqnarray*} 2+7y+5y^2+y^3 \equiv 0 \mod 2^3 \end{eqnarray*}$ kannst du natürlich auch die o.g. Techniken anwenden, also erst mod 2, mod 2^2. Allerdings kannst du bei nur $\begin{eqnarray*} 2^3=8 \end{eqnarray*}$ Restklassen diese auch gleich alle durchtesten, das geht vermutlich schneller. Augenzwinkern

06.12.2006, 12:34

mYthos

Auf diesen Beitrag antworten »

Es genügt, die Gleichung

$\begin{eqnarray*} x^3 + x^2 - 4 = 0 \end{eqnarray*}$

nur auf Lösungen, die Teiler von 4 sind, zu untersuchen. Denn es kommen hier nur ganzahlige Werte in Frage.

Schnell erkennen wir, dass solche (1, -1, 2, -2, 4, -4) nicht existieren.

mY+

06.12.2006, 13:14

Auf diesen Beitrag antworten »

Für die Gleichung $\begin{eqnarray*} x^3+x^2-4=0 \end{eqnarray*}$ mag das stimmen. Hier im Thread ging es aber um die Kongruenz $\begin{eqnarray*} x^3+x^2-4\equiv 0\mod 7^3 \end{eqnarray*}$ ...

07.12.2006, 22:19

liselotte28

Auf diesen Beitrag antworten »

danke! - und noch mehr Fragen....
Hallo erstmal!
Meine oben schon mal erwaehnte Aufgabe: x^3+^2x^2-1 kongruent 0 (mod2^3 3^2) habe ich jetzt in zwei, hoffe ich, aequivalente Kongruenzen aufgeteilt:
1. x^3+2x^2-1 kongruent mod 2^3 und
2. x^3+2^x^2-1 kongruent mod 3^2.
und die 1. fuer 2^1 (x=2k+1), 2^2 (k=2l+1) und 2^3 (l=1) ausgerechnet.
Ich habe dabei das neue Ergebnis immer schon waehrend der Rechnung in das vorherige eingetragen, also z.B. von 2^2: k=2l+1 in x=2k+1=2(2l+1)+1=4l+3 und das (4l+3) fuer den naechsten Schritt fuer x eingesetzt. Ist das richtig?
Alles wieder rueckwaerts eingesetzt ergibt x=7, was bei der Probe in die 1. Kongruenz auch passt. was ist 7 jetzt? Keine Restklasse, oder? Teil einer Restklasse? Welcher? Mit 15 wuerde die Gleichung auch aufgehen.....
Fuer die 2. habe ich fuer mod 3 heraus: x=3k+2 und mod 3^2: k=2, was rueckwaerts eingesetzt x=8 ergibt und als Loesung fuer die 2. passt. Stellen sich mir die gleichen Fragen wie eben...
Aber das kann ja noch nicht die Loesung der ganzen Aufgabe sein, fuer die Ausgangsgleichung mit mod 2^3 3^2 passt ja keine dieser x Loesungen.
Soweit habe ich es heute abgegeben, aber ich moechte es doch gerne bis zum Ende versuchen und verstehen - Musterloesungen gibt es immer erst Wochen spaeter, wo die Ergebnisse immer offensichtlich seien, nur mir nicht )-:
Ich vermute mal, jetzt muss wieder der chinesische Restsatz ran, aber welche Kongruenzen muss ich hier jetzt nehmen? Die zuletzt fuer jede Gleichung rauskamen? Also l kongruent 1 mod 2 (bei mod 2^3) und 2k kongruent 1 mod 3 (bei mod 3^2)? We mache ich das jetzt??

07.12.2006, 22:42

Auf diesen Beitrag antworten »

Rückwärts heißt das ausführlich eigentlich folgendes:

l = 1 mod 2
k = 2l+1 = 3 mod 4
x = 2k+1 = 7 mod 8

Analog dann modulo 3:

k = 2 mod 3
x = 3k+2 = 8 mod 9

Und jetzt tatsächlich chinesischer Restsatz. Die gemeinsame Lösung modulo 72 sieht man übrigens direkt, wenn man das Kongruenzsystem eher so schreibt:

x = -1 mod 8
x = -1 mod 9

07.12.2006, 23:03

liselotte28

Auf diesen Beitrag antworten »

also
interessieren die letzten Kongruenzzeilen kein bisschen, sondern ich muss die Ergebnisse fuer x einfach kongruent x mod Ausgangsmod setzen und die Kongruenz(en) dann loesen, ja?
Das heißt, auf meine Frage von oben: die Ergebnisse sind immer Restklassen?
OK, als Ergebnis wuerde ich mal so erkennen: 71?
Ist das jetzt die einzige Loesung? Oder sind jetzt alle Vielfachen von 71 auch Loesung? Wie gibt man das dann an?

Danke! Find ich echt gut, dass man hier fragen kann und auch verstehbare Antworten bekommt.

08.12.2006, 00:20

Auf diesen Beitrag antworten »

RE: also

Zitat:

Original von liselotte28
OK, als Ergebnis wuerde ich mal so erkennen: 71?

Richtig, aber als Restklasse: $\begin{eqnarray*} 71 \mod 72 \end{eqnarray*}$

Zitat:

Original von liselotte28
Ist das jetzt die einzige Loesung? Oder sind jetzt alle Vielfachen von 71 auch Loesung?

Das vergiss mal ganz schnell: Setz mal 2*71=142 ein, da siehst du, dass das Unsinn ist.

Allgemein ist es doch so: Aus $\begin{eqnarray*} x\equiv y\mod m \end{eqnarray*}$ folgt $\begin{eqnarray*} p(x)\equiv p(y)\mod m \end{eqnarray*}$ für alle Polynome $\begin{eqnarray*} p \end{eqnarray*}$ mit ganzzahligen Koeffizienten. Und genau solche Strukturen hast du ja hier betrachtet.

10.12.2006, 21:24

liselotte28

Auf diesen Beitrag antworten »

ja
stimmt, mit 71 geht es nicht. Ich dachte nur, wenn 71 als Restklasse gesehen werden muss, muss man die allgemein noch wieder angeben. Wohl zu kurz gedacht.
Dann wohl x=72+71n, richtig? Oder gibt man das nicht mehr an, weil es eh jeder weiß?

10.12.2006, 21:25

Auf diesen Beitrag antworten »

RE: ja
Nein!!! x=71+72n ist richtig.

10.12.2006, 21:43

liselotte28

Auf diesen Beitrag antworten »

falsch getippt
Entschuldigung und danke! ich hatte es auch so auf meinen Zettel geschrieben, nur hier falsch abgetippt.

Neue Frage »

Antworten »

Zahlentheorie, loesen von Kongruenzen

Verwandte Themen