Gleichung mit 2 unbekannten - Modulo

26.01.2014, 19:22

free.dom

Gleichung mit 2 unbekannten - Modulo

Hallo,

ich habe ein Problem bei folgender Aufgabe:

Finden Sie alle Paare (a,b) von Zahlen a,b aus Z12, die die Gleichung
5^a2 + 2b^2 ≡ 3(mod 12) erfüllen.

Hinweis: Lösen Sie zuerst die Gleichung 5x +2y ≡ 3 (mod 12) und überlegen Sie dann, welche
der Lösungen als Quadrate mod 12 darstellbar sind.

Mein Ansatz ist, dass die Lösungsmenge der Gleichung 5x + 2y ≡ 3 (mod 12) für das Paar 5x mod 12 und 2y mod 12 {(3,0), (2,1), (1,2), (0,3)} sein muss.

Demnach kann man folgende Gleichungssysteme aufstellen:

5a mod 12 = 3
2b mod 12 = 0
=> a = 3 und b = 0 und b = 6

5a mod 12 = 2
2b mod 12 = 1
WIDERSPRUCH - 2b mod 12 kann niemals ungerade sein

5a mod 12 = 1
2b mod 12 = 2
=> a = 5 und b = 7 und b = 1

5a mod 12 = 0
2b mod 12 = 3
WIDERSPRUCH - gleiche wie oben

Wenn ich jetzt aber bei den 2 verbliebenen Gleichungssystemen die quadrate von a und b einsetze bekomme ich dort aber auch Widersprüche heraus.. Wo ist mein Fehler? Ich hab ja das Gefühl, dass ich den Ansatz schon versemmelt hab unglücklich

26.01.2014, 19:28

free.dom

Auf diesen Beitrag antworten »

Ich war leider noch nicht angemeldet als ich den Beitrag erstellt habe und kann ihn jetzt nicht mehr editieren.
Die kryptischen Zeichen sollen Kongruenzzeichen sein.

$\begin{eqnarray*} 5a^2 + 2b^2 \equiv 3 (mod 12) \end{eqnarray*}$

Hinweis: Lösen Sie zuerst die Gleichung $\begin{eqnarray*} 5x +2y \equiv 3 (mod 12) \end{eqnarray*}$ und überlegen Sie dann, welche
der Lösungen als Quadrate mod 12 darstellbar sind.

26.01.2014, 19:37

Helferlein

Auf diesen Beitrag antworten »

Du machst im zweiten Teil einen Denkfehler: Du sollst nicht a² einsetzen, sondern überlegen/nachweisen wann es $\begin{eqnarray*} c,d \in Z_{12} \end{eqnarray*}$ mit $\begin{eqnarray*} c²=a \end{eqnarray*}$ und $\begin{eqnarray*} d²=b \end{eqnarray*}$ gibt.

26.01.2014, 19:44

free.dom

Auf diesen Beitrag antworten »

Aber in dem Hinweis steht doch: "und überlegen Sie dann, welche
der Lösungen als Quadrate mod 12 darstellbar sind."

Verstehe ich das falsch? Es muss doch anscheinend eine Lösung geben, welche als Quadrat mod 12 darstellbar ist. Meine Lösungen sind ja:

a1 = 3
b1 = 0 oder 6

a2 = 5
b2 = 1 oder 7

Also müsste eine dieser Lösungen als Quadrat in mod 12 darstellbar sein? Da käme dann nur
a1 = 3 und b1 = 0 in Frage, da diese quadriert immernoch kleiner 12 sind.

26.01.2014, 20:01

free.dom

Auf diesen Beitrag antworten »

Achso vielen Danke erstmal für die schnelle Antwort! Was ich noch vergessen hab ist, dass der Thread wohl auch eher ins Forum Hochschulmathematik sollte... Ich habs irgendwie total versaut beim posten. Sitz einfach schon zu lange an der Aufgabe unglücklich

. Wäre also nett, wenn jemand der dazu befugt ist den Thread verschieben könnte!

26.01.2014, 20:32

Helferlein

Auf diesen Beitrag antworten »

Du bist also der Meinung, dass eine Zahl deren Quadrat in $\begin{eqnarray*} \mathbb{R} \end{eqnarray*}$ größer als 12 ist, nicht als Lösung in Frage kommt?
Wie erklärst Du Dir dann, dass in $\begin{eqnarray*} Z_{12} \end{eqnarray*}$ z.B. $\begin{eqnarray*} 5²=1 \end{eqnarray*}$ gilt?

Ich kann nur meinen Hinweis von oben wiederholen: Suche nach Lösungen der Gleichungen c²=a uind d²=b, dann sind diese c,d auch Lösungen deiner Ausganggleichung. (Leider hast Du a,b schon als Variablen verwendet, so dass die Lösungen dann nicht mehr der Benennung der Aufgabe folgen)

26.01.2014, 20:46

free.dom

Auf diesen Beitrag antworten »

Okay das war Quatsch.. Wie bereits gesagt bin ich nicht mehr so gut konzentriert. Die Quadrate der Zahlen modulo 12 müssen natürlich auch im Raum $\begin{eqnarray*} \mathbb Z12 \end{eqnarray*}$ liegen.

Der einfachheit halber kann ich die a und b die ich bereits verwendet hab ja x und y nennen, so wie in der Aufgabenstellung. Also muss ich schauen, wann es ein $\begin{eqnarray*} a, b \end{eqnarray*}$ geben kann, dass $\begin{eqnarray*} a^2 = x, b^2 = y \end{eqnarray*}$ erfüllt.

also wäre z.B: $\begin{eqnarray*} a=a^2=0 \end{eqnarray*}$ für $\begin{eqnarray*} x=0 \end{eqnarray*}$ und für $\begin{eqnarray*} y =3 \end{eqnarray*}$ würde es kein $\begin{eqnarray*} b^2 \end{eqnarray*}$ geben, da alle $\begin{eqnarray*} 3+12*n \end{eqnarray*}$ mit $\begin{eqnarray*} n \in \mathbb Z12 \end{eqnarray*}$ in Frage kämen, aber $\begin{eqnarray*} b^2 \end{eqnarray*}$ keinesdas quadrat einer Zahl zwischen 0 und 11 ist..?? das muss ich jetzt noch mit der anderen lösung ausprobieren?

26.01.2014, 20:56

Helferlein

Auf diesen Beitrag antworten »

RE: Gleichung mit 2 unbekannten - Modulo
Den selben Fehler hast Du schon zu Beginn gemacht:

Zitat:

Original von free.dom
Mein Ansatz ist, dass die Lösungsmenge der Gleichung 5x + 2y = 3 (mod 12) für das Paar 5x mod 12 und 2y mod 12 {(3,0), (2,1), (1,2), (0,3)} sein muss.

Auch hier kann 5x durchaus einen größeren Rest als 3 haben. Da alles durchzuprobieren ist sehr unsystematisch. Ich würde versuchen erst einmal herauszufinden, welche Reste 5x und 2y überhaupt annehmen können, um dann die Wertepaare herauszufiltern, deren Summe den Rest 3 lässt.
Bei diesen (11) Lösungen stellt sich dann erneut die Frage nach dem Quadrat.

26.01.2014, 21:53

free.dom

Auf diesen Beitrag antworten »

Okay ich sehe endlich was der Fehler war! Natürlich würde für 5x = 10 und 2y = 5 auch die Lösung 3 rauskommen!

Also die Reste, die 5x modulo 12 annehmen kann sind:

x=0: 0
x=1: 5
x=2: 10
x=3: 3
x=4: 8
x=5: 1
x=6: 6
x=7: 11
x=8: 4
x=9: 9
x=10: 2
x=11: 7

Also als Menge zusammengefasst $\begin{eqnarray*} \left\{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11\right\} \end{eqnarray*}$ .

Das ganze nochmal für y gemacht ergibt dann $\begin{eqnarray*} \left\{0, 2, 4, 6, 8, 10\right\} \end{eqnarray*}$ .

Damit würden folgende Reste 3 ergeben (alles wo 3, 15, 27, 3+n*12 rauskommen würde): { (1, 2), (3,0), (5,10), (7, 8), (9, 6), (11, 4) }.

Damit wäre die Lösungsmenge für x, y { (5, 2), (5, 7), (3, 0),(3,6)(1, 5), (1, 11), (11, 4), (11, 10), (9, 3), (9, 9), (7, 2), (7, 8)}

Stimmt das soweit? Dann müsste ich mir jetzt das ganze noch für die Quadrate anschauen.

Edit(Helferlein): Latex-Klammern entfernt, da Mischung BB-Code mit Latex nicht funktioniert. Vorherigen Beitrag gelöscht, da doppelt.

26.01.2014, 23:22

Helferlein

Auf diesen Beitrag antworten »

Die Kombinationen sind richtig, hatte mich oben auch um eins vertan.
Bleibt nur noch die Frage welche davon aus Paaren von Quadratzahlen in $\begin{eqnarray*} Z_{12} \end{eqnarray*}$ bestehen.

27.01.2014, 10:32

free.dom

Auf diesen Beitrag antworten »

Danke fürs editieren.. Bin da bei den Paaren durcheinandergekommen. Das erste muss auch (5, 1) sein. Jetzt bin ich auch wieder fitter nach der Pause.

Um zu schauen, ob die Quadratzahlen auch den Rest 3 ergeben würde ich jetzt von jedem Paar das Quadrat bilden und Modulo 12 rechnen.

Da kommen bei mir aber nur die Reste 2, 5, 6 und 9 raus. Also keine der Lösungspaare quadriert ergibt den Rest 3 unglücklich

. Es ist doch zum verzweifeln.. Wahrscheinlich denke ich hier wieder falsch?

27.01.2014, 11:10

free.dom

Auf diesen Beitrag antworten »

Okay ich kann leider nicht mehr editieren, aber hab nochmal nach oben gescrollt. Ich sollte ja nicht einsetzen, sondern schauen, wann $\begin{eqnarray*} x=a^2 \end{eqnarray*}$ und $\begin{eqnarray*} y=b^2 \end{eqnarray*}$ sein kann.

Diese sollte es doch immer geben, wenn $\begin{eqnarray*} x^2 mod 12 = x \end{eqnarray*}$ gilt.? Ich denke, dass hierfür erstmal nur alle Zahlen in Betracht gezogen werden können, die einen ggT mit 12 haben > 1. Also klartext 3, 6 und 9.
Nach ausprobieren erweist sich nur das Paar (9 ,9) als Lösung, welches mit $\begin{eqnarray*} x=x^2 mod 12 \end{eqnarray*}$ und $\begin{eqnarray*} y = y^2 mod 12 \end{eqnarray*}$ ebenfalls das Paar (9, 9) bildet.?
Außerdem ergibt das quadrat des Paares (3, 9) ebenfalls das Paar (9, 9).

Jetzt hab ich allerdings doch irgendwie wieder eingesetzt... Wenigstens sollten die 2 Paare stimmen. Zumindest laut meiner Lösung, die ich mir mit einem kleinen Programm errechnet habe. Allerdings würden mir noch weitere Paare fehlen. Das Programm (einfach 2 For-Schleifen ineinander verschachtelt und durchlaufen lassen und auf (a*a + b*b) mod 12 == 3 geprüft - was ernsthaft einfach viiiieeel schneller geht als das ganze ausprobiere und getue per Hand) hat folgende Lösungen:

a b
3 3
3 9
9 3
9 9

Also durch überlegen kann man natürlich argumentieren, dass 3² = 9 und deshalb (3, 3) auch ein Paar sein muss, aber für so richtig schlüssig ist mir das nicht, da $\begin{eqnarray*} 2b^2 mod 12 \end{eqnarray*}$ mit b = 3 ja den Rest 6 ergibt und $\begin{eqnarray*} 5a^2 mod 12 \end{eqnarray*}$ mit a = 3 den Rest 9 ergibt. Das passt zwar, ich kann aber nicht den Zusammenhang erklären warum, da (3, 3) ja keine Lösung der Gleichung aus dem Hinweis ist.

Gibt es nicht auch irgendeine Möglichkeit das einfach durch Lösen einer Gleichung oder ähnlichem schneller zu machen? Ich hab ja nun doch eher viel probiert und wenig gerechnet.

EDIT: Okay, ich nehme mal an, dass es miit der Kongruenz von 3, 9 und 12 zutuen hat...

27.01.2014, 20:38

Helferlein

Auf diesen Beitrag antworten »

Klar kann ein Programm das schneller berechnen, dafür gibt es sie ja.
Sinn eines Studiums ist es aber doch gerade, dass Du auch weisst, wieso das Programm zu einer Lösung kommt oder wie alternative/effektivere Wege aussehen könnten.

Zur Aufgabe: Es ist doch recht einfach die Quadratzahlen in $\begin{eqnarray*} Z_{12} \end{eqnarray*}$ zu bestimmen, nämlich indem Du die 12 Zahlen einfach quadrierst.

Das ergibt dann:
0²=0 , 1²=1 , 2²=4 , 3²=9 , 4²=4 , 5²=1
6²=0 , 7²=1 , 8²=4 , 9²=9 , 10²=4 , 11²=1

Also sind 0,1,4 und 9 Quadratzahlen in $\begin{eqnarray*} Z_{12} \end{eqnarray*}$ . Danach durchsuchst Du deine Lösungen.

28.01.2014, 00:26

etzwane

Auf diesen Beitrag antworten »

Hallo, ich habe, gestützt auf eure Angaben, auch versucht, diese Aufgabe durchzurechnen und komme auf das Ergebnis:

Alle Paare a=3^m und b=3^n mit m,n >=1 erfüllen 5*a^2 + 2*b^2 = 3 (mod 12)

Ich frage mich allerdings, ob es noch weitere Lösungspaare gibt.

06.02.2014, 14:02

free.dom

Auf diesen Beitrag antworten »

Etwas spät die Antwort, aber nein, es gibt neben den 4 Paaren keine weiteren Lösungen mehr.

Danke dir Helferlein für die gute Hilfe bis zum Ende!

Neue Frage »

Antworten »

Gleichung mit 2 unbekannten - Modulo

Verwandte Themen