| |
| Autor |
  Gleichungssystem modulo |
|
Haeslein
Ehemals Aktiv 
Dabei seit: 12.01.2006
Mitteilungen: 246
 |  Themenstart: 2007-12-12
|
Hallo,
ich habe hier ein Gleichungssystem, dessen Lösung ich bestimmen soll. Es lautet:
I. 10x == 8 mod 36
II. x^2 == 1 mod 15
Mir ist zwar klar, wie ich mögliche Lösungen der beiden Gleichungen bestimmen kann, also dass z. B. x = 4 eine Lösung der zweiten Gleichung ist. Allerdings weiß ich nicht, wie ich systematisch alle Lösungen der beiden Gleichungen finden kann und wie ich das dann in eine Lösung bringe.
Wäre für eine Hilfestellung dankbar.
LG,
Haeslein
|
 Profil
|
SchuBi
Senior 
Dabei seit: 13.03.2003
Mitteilungen: 19409
Wohnort: NRW
 |  Beitrag No.1, eingetragen 2007-12-12
|
Hallo, Haeslein!
Die 2. Gleichung hat drei mögliche Lösungen mod 15, nämlich 1, 4, 11 und 14.
Damit erhältst du drei vier Gleichungssysteme, die du lösen mußt.
\ll(1)10x==8 mod 36 und x==1 mod 15
\ll(2)10x==8 mod 36 und x==4 mod 15
\ll(3)10x==8 mod 36 und x==11 mod 15
\ll(4)10x==8 mod 36 und x==14 mod 15
[ Nachricht wurde editiert von SchuBi am 12.12.2007 11:18:38 ]
[ Nachricht wurde editiert von SchuBi am 13.12.2007 08:21:17 ]
|
Profil
|
Haeslein
Ehemals Aktiv
Dabei seit: 12.01.2006
Mitteilungen: 246
|  Beitrag No.2, vom Themenstarter, eingetragen 2007-12-12
|
Hallo SchuBi,
muss ich denn nicht zeigen, dass das die einzigen Lösungen sind? Ich hab das halt einfach mal ausprobiert und kam (bis jetzt auch nur auf die 3 Zahlen), aber wer garantiert mir, dass es nicht noch eine deutlich größere Zahl gibt, die meine zweite Gleichung erfüllt?
Gruß,
Haeslein
|
Profil
|
SchuBi
Senior
Dabei seit: 13.03.2003
Mitteilungen: 19409
Wohnort: NRW
|  Beitrag No.3, eingetragen 2007-12-12
|
Hallo, Haeslein!
Bei der Division durch 15 können nur die Reste 0, 1, ..., 14 entstehen.
16 = 1 mod 15
16^2 = 256 = 1 mod 15
|
Profil
|
Haeslein
Ehemals Aktiv
Dabei seit: 12.01.2006
Mitteilungen: 246
| Beitrag No.4, vom Themenstarter, eingetragen 2007-12-13
|
Hallo SchuBi!
Jetzt hast du mich irgendwie verwirrt...
Ich verstehe deinen Hinweis nicht: "Bei der Division durch 15 können nur die Reste 0, 1, ..., 14 entstehen." Also, mir ist schon klar, dass da nur diese Reste entstehen können, aber was bringt mir das?
Außerdem hattest du in deiner ersten Antwort geschrieben, dass nur 1, 4 und 11 die zweite Gleichung lösen. Aber was ist mit 14? 14² lässt doch mod 15 auch Rest 1. Warum ist das dann keine Lösung für die zweite Gleichung?
Wäre schön, wenn du mir nochmal antworten würdest.
LG,
Haeslein
|
Profil
|
SchuBi
Senior
Dabei seit: 13.03.2003
Mitteilungen: 19409
Wohnort: NRW
| Beitrag No.5, eingetragen 2007-12-13
|
Hallo, Haeslein!
Die 14 hatte ich leider übersehen 
Also mußt du dannn 4 Kongruenzen lösen.
|
Profil
|
fru
Senior 
Dabei seit: 03.01.2005
Mitteilungen: 21456
Wohnort: Wien
 | Beitrag No.6, eingetragen 2007-12-13
|
Hallo Haeslein, schau mal hier rein!
\
Da habe ich erst gestern beschrieben, wie man eine Kongruenz der Form
a*b==0 mod m*n
auf einfachere Kongruenzen zurückführen kann. Um Deine Kongruenz
x^2==1 mod 15
auf diese Form zu bringen, brauchst Du sie nur so umzuschreiben:
(x-1)*(x+1)==0 mod 3*5
Natürlich kann man stattdessen auch einfach alle 15 Reste durchprobieren. Wenn der Modul aber einmal etwas größer ist, dann stößt man mit dieser Methode bald auf praktische Grenzen.
Liebe Grüße, Franz
|
Profil
|
Haeslein
Ehemals Aktiv
Dabei seit: 12.01.2006
Mitteilungen: 246
| Beitrag No.7, vom Themenstarter, eingetragen 2007-12-13
|
Hallo nochmal,
ich glaube, das muss ich mir nochmal genauer anschauen...
Der Übungsgruppenleiter meinte heute, dass wir versuchen sollten, die "mod-Zahlen" auf Primzahlen und die zweite Gleichung auf eine bzw. mehrere lineare zurückzuführen. Das sollte ja dann das sein, was SchuBi machen wollte. Dann würde es einfacher gehen, hat er gesagt. :-(
Irgendwie stehe ich allerdings noch immer auf dem Schlauch.... Was meint ihr denn mit Reste durchprobieren?
LG,
Haeslein
|
Profil
|
fru
Senior
Dabei seit: 03.01.2005
Mitteilungen: 21456
Wohnort: Wien
| Beitrag No.8, eingetragen 2007-12-13
|
\quoteon(2007-12-13 13:35 - Haeslein)
Der Übungsgruppenleiter meinte heute, dass wir versuchen sollten, die "mod-Zahlen" auf Primzahlen und die zweite Gleichung auf eine bzw. mehrere lineare zurückzuführen.
\quoteoff
Hallo Haeslein, das ist doch genau das, was ich auch gemacht habe:
Ich habe den Modul 15 als Produkt der beiden Primzahlen 3 und 5 geschrieben, und fast der ganze im Beitrag No. 6 verlinkte Thread dreht sich darum, wie sich die quadratische Kongruenz auf mehrere lineare Kongruenzen zurückführen läßt.
Lies Dir also, wie Du ja angekündigt hast, diesen Thread sehr genau durch! Deine abschließende Frage zeigt mir aber, daß Du Dir darüber hinaus unbedingt auch die elementarsten Grundlagen des Rechnens mit Kongruenzen aneignen solltest. Dafür eignen sich (vor allem wegen des doch eher beträchtlichen Umfangs) Bücher und/oder Skripten weit besser als dieses Forum, dessen Sinn es nicht sein kann, einen ganzen Lehrgang abzuhalten.
Mit einzelnen Fragen, die Dir dabei dann vielleicht noch unklar bleiben werden, kannst Du Dich natürlich gerne wieder an uns wenden.
Ich will also aus den eben erwähnten Gründen nicht allzuweit ausholen:
\quoteon(2007-12-13 13:35 - Haeslein)
Was meint ihr denn mit Reste durchprobieren?
\quoteoff
Eine Polynomkongruenz zu lösen bedeutet:
Jene Restklassen anzugeben, deren Repräsentanten die Kongruenz in eine wahre Aussage überführen, wenn man sie für die Variable einsetzt.
Denn die Repräsentanten einer Restklasse erfüllen entweder alle die Kongruenz oder sie erfüllen sie alle nicht.
Obwohl es also i.A. unendlich viele ganze Lösungszahlen gibt, verteilen sich diese doch nur auf endlich viele Restklassen. Da der Betrag des Moduls m gleich der Anzahl aller überhaupt in Frage kommenden Restklassen ist, braucht man folglich nur m ganze Zahlen so auszuwählen, daß sie ein vollständiges Repräsentantensystem modulo m bilden (dafür eignen sich z.B. alle positiven ganzen Zahlen, welche nicht größer als der Modul sind) und zu testen, welche von ihnen die Kongruenz zu einer wahre Aussage machen, wenn man sie für die Variable einsetzt:
Bei Deiner zweiten Kongruenz ist der Modul 15, also hat SchuBi einfach alle ganzen Zahlen zwischen 0 und 14 (jeweils einschließlich) - oder vielleicht auch ein anderes vollständiges Restesystem - eingesetzt. Da jede andere ganze Zahl mit einer dieser 15 Zahlen in derselben Restklasse liegt, wissen wir damit von allen ganzen Zahlen, ob sie die Kongruenz lösen oder nicht.
Liebe Grüße, Franz
|
Profil
|
Andi1984
Ehemals Aktiv
Dabei seit: 30.05.2005
Mitteilungen: 589
Wohnort: Heusweiler
 |  Beitrag No.9, eingetragen 2007-12-15
|
Hallo zusammen,
ich hänge an der selben Aufgabe. Ich fand die Aufteilung von
x^2 == 1 mod 15 durch (x-1)(x+1) == 0 mod 3*5
eigentlich ganz gut. Jedoch bin ich mir nicht so sicher wie ich das nun weiter aufsplitten soll.
Aus dem verlinkten Beitrag erkenne ich, dass
(x-1) 15 teilen muss und (x+1) 15 teilen muss. Sehe ich das richtig?
Dann bliebe ja nur noch x=4, weil hier als einziges
3 und 5 15 teilt.
Bei den restlichen möglichen Lösungen (1, 11 und 14) ist das ja nicht der Fall.
Sehe ich das richtig?
Oder muss nur (x-1) ODER (x+1) 15 teilen?
LG Andreas
|
Profil
|
Andi1984
Ehemals Aktiv
Dabei seit: 30.05.2005
Mitteilungen: 589
Wohnort: Heusweiler
|  Beitrag No.10, eingetragen 2007-12-15
|
So,
also ich habe mir mal noch die zweite Gleichung angesehen und habe bzgl. der Moduloklasse 36 die Restklassen 8 und 26 als Lösungen gefunden.
Als Gesamtlösung beider Gleichungen hätte ich dann 26, da 26 bzgl. der Moduloklasse 15 der 11 entspricht und dies ja nach den obigen Beiträgen Lösung der 2. Gleichung ist.
Meiner Meinung nach ist also 26 die einzigste Lösung. Ist das korrekt oder hab ich was falsch gerechnet?
LG Andi
|
Profil
|
fru
Senior 
Dabei seit: 03.01.2005
Mitteilungen: 21456
Wohnort: Wien
| Beitrag No.11, eingetragen 2007-12-15
|
Hallo Andreas!
\quoteon(2007-12-15 15:04 - Andi1984)
Aus dem verlinkten Beitrag erkenne ich, dass
(x-1) 15 teilen muss und (x+1) 15 teilen muss. Sehe ich das richtig?
[...]
Oder muss nur (x-1) ODER (x+1) 15 teilen?
\quoteoff
\
Weder noch! Beachte einfach die Definition
a==b mod m :<=> m\|(a-b)
Was muß man hier für a, b und m einsetzen, damit es auf unsere Kongruenz anwendbar ist?
Liebe Grüße, Franz
|
Profil
|
fru
Senior
Dabei seit: 03.01.2005
Mitteilungen: 21456
Wohnort: Wien
| Beitrag No.12, eingetragen 2007-12-15
|
\quoteon(2007-12-15 15:16 - Andi1984)
... ich habe mir mal noch die zweite Gleichung angesehen und habe bzgl. der Moduloklasse 36 die Restklassen 8 und 26 als Lösungen gefunden.
\quoteoff
\
Ja, diese Lösung der Kongruenz 10x==8 mod 36 ist richtig.
Sie läßt sich aber durch x==8 mod 18 wesentlich einfacher darstellen!
|
Profil
|
Andi1984
Ehemals Aktiv
Dabei seit: 30.05.2005
Mitteilungen: 589
Wohnort: Heusweiler
| Beitrag No.13, eingetragen 2007-12-15
|
Hallo,
ok ich glaub jetzt hab ichs verstanden.
Hier müsste man a durch (x-1)(x+1) ersetzen und b durch 0 und m durch 15
Das passt dann auch für 4, 11, 1 und 14. Aber was ist jetzt die Lösung des kompletten GLS?
Ich würde sagen nur x=11 (bzgl. Modulo 15) bzw. x=26 (bzw. Modulo 36) was ja sozusagen dasselbe ist, weil 26 mod 15 = 11.
Ist das die einzige Lösung oder gibt es da noch mehr?
LG Andreas
|
Profil
|
fru
Senior
Dabei seit: 03.01.2005
Mitteilungen: 21456
Wohnort: Wien
| Beitrag No.14, eingetragen 2007-12-16
|
\quoteon(2007-12-15 19:54 - Andi1984)
... was ist jetzt die Lösung des kompletten GLS?
Ich würde sagen nur x=11 (bzgl. Modulo 15) bzw. x=26 (bzw. Modulo 36) was ja sozusagen dasselbe ist, weil 26 mod 15 = 11.
Ist das die einzige Lösung oder gibt es da noch mehr?
\quoteoff
\
Hallo Andi!
(1) Du gibst nicht eine, sondern zwei__ Lösungen an, denn x==11 mod 15 ist keineswegs "sozusagen dasselbe" wie x==26 mod 36. Z.B. ist die Zahl 11 in der Restklasse 11 modulo 15 enthalten, nicht aber in der Restklasse 26 modulo 36 \(weil 36 kein Teiler von 26-11=15 ist).
(2) Beide Lösungen sind falsch. Um das einzusehen, genügt es, einige Vertreter der von Dir angegebenen Restklassen zur Probe in die beiden gegebenen Kongruenzen einzusetzen: Dann wirst Du bald auf Gegenbeispiele stoßen.
(3) Es handelt sich hier offensichtlich um kein Ratespiel, sondern um eine Rechen__aufgabe. Poste also Deine zugehörigen Rechnungen \(evtl. einschließlich Deiner Überlegungen und\/oder Begründungen zu den einzelnen Rechenschritten), dann werden sich die Fehler, die Du dabei begangen hast, sicherlich leicht finden lassen. So__ kann ich nur dazu sagen sagen, daß Deine Lösungen falsch sind, aber nicht: wo Du Dich vertan hast!
Liebe Grüße, Franz
|
Profil
|
hoffnungslos
Ehemals Aktiv
Dabei seit: 01.11.2007
Mitteilungen: 23
| Beitrag No.15, eingetragen 2007-12-16
|
Hallo!
Ich sitze an der gleichen Aufgabe und bin mir nicht so sicher, ob das stimmt, was ich bis jetzt gemacht habe.
zur Gleichung x^2==1 mod 15
Ich habe folgende 4 Fälle raus:
1.) x-1==0 mod 3 \and\ x-1==0 mod 5
Lsg.: x==1 mod 15
2.) x+1==0 mod 3\and\ x+1==0 mod 5
Lsg.: x==14 mod 15
3.) x+1==0 mod 3 \and\ x-1==0 mod 5
Lsg.: x==11 mod 15
4.) x-1==O mod 3\and\ x+1==0 mod 5
Lsg.: x==4 mod 15
Jetzt hab ich noch ein Problem mit der ersten Gleichung, weil ich nicht weiß wie ich die lösen soll.
Durch Probieren krieg ich die Lösung x==8 mod 36
In dem anderen Beitrag war ja so ein ähnliches Problem, nur leider verstehe ich den folgenden Schritt nicht:
Wieso ist 3x==4 mod 7\and\ 3x==4 mod 5 das Gleiche wie x==6 mod 7\and\ x==3 mod 5 ?
Und was mache ich, wenn ich die Lösung für die 1. Gleichung raus hab? Ihr habt ja geschrieben, dass die Lösung x==8 mod 18 ist. Wie verknüpfe ich das mit der 2. Gleichung?
[ Nachricht wurde editiert von hoffnungslos am 16.12.2007 13:55:13 ]
|
Profil
|
fru
Senior
Dabei seit: 03.01.2005
Mitteilungen: 21456
Wohnort: Wien
| Beitrag No.16, eingetragen 2007-12-16
|
Hi hoffnungslos!
\quoteon(2007-12-16 12:54 - hoffnungslos)
\
Jetzt hab ich noch ein Problem mit der ersten Gleichung, weil ich nicht weiß wie ich die lösen soll.
\quoteoff
\
Das ist doch nur eine lineare Kongruenz:
10x==8 mod 36
<=>
36\|(10x-8)
<=>
18\|(5x-4)
<=>
18\|11*(5x-4)
<=>
18\|(54x+x-36-8)
<=>
18\|(x-8)
<=>
x==8 mod 18
\quoteon(2007-12-16 12:54 - hoffnungslos)
\
Wieso ist 3x==4 mod 7\and\ 3x==4 mod 5 das Gleiche wie x==6 mod 7\and\ x==3 mod 5 ?
\quoteoff
\
Auch das sind nur lineare Kongruenzen. Du brauchst eine Zahl, deren Dreifaches zu 1 kongruent ist, z.B.:
3x==4 mod 7
<=>
7\|(3x-4)
<=>
7\|5*(3x-4)
<=>
7\|(14x+x-14-6)
<=>
7\|(x-6)
<=>
x==6 mod 7
\quoteon(2007-12-16 12:54 - hoffnungslos)
Und was mache ich, wenn ich die Lösung für die 1. Gleichung raus hab? Ihr habt ja geschrieben, dass die Lösung x==8 mod 18 ist. Wie verknüpfe ich das mit der 2. Gleichung?
\quoteoff
\
Hier hast Du nun vier Systeme von je zwei linearen Kongruenzen zu lösen. Jede Lösung der zweiten Kongruenz \(die Du übrigens richtig gelöst hast) muß mit jeder Lösung \(es gibt ja nur eine) der ersten Kongruenz konjunktiv verknüpft werden, also:
(x==1 mod 15\and\ x==8 mod 18)\or\ (...)\or\ (...)\or\ (...)
Das Standardverfahren für die Lösung eines solchen Systems ist der Chinesische Restsatz. Da Du aber noch nicht einmal einfache lineare Kongruenzen lösen kannst, empfehle ich Dir eher folgendes Vorgehen:
Die Lösung der zweiten Kongruenz x==8 mod 18 ist gleichwertig mit
\exists\ a\el\IZ: x=18a+8
Das setzen wir nun in eine Lösung der ersten Kongruenz ein \(ich nehme mal Deine dritte Lösung x==11 mod 15, für die anderen drei Lösungen gehst Du analog vor):
18a+8==11 mod 15
<=>
15\|(18a-3)
<=>
5\|(6a-1)
<=>
5\|(a-1)
<=>
a==1 mod 5
<=>
\exists\ b\el\IZ: a=5b+1
Das setzen wir nun in x=18a+8 ein und erhalten
\exists\ b\el\IZ: x=18*(5b+1)+8
<=>
\exists\ b\el\IZ: x=90b+26
<=>
90\|(x-26)
<=>
x==26 mod 90
Liebe Grüße, Franz
|
Profil
|
hoffnungslos
Ehemals Aktiv
Dabei seit: 01.11.2007
Mitteilungen: 23
| Beitrag No.17, eingetragen 2007-12-16
|
Vielen Dank für deine Mühe. Du hast mir schon sehr viel weitergeholfen.
Ich hab jetzt noch ein kleines Problem.
Für x== 8 mod 15 und x== 14 mod 15 krieg ich die Lsg. x==44mod 90 raus.
Aber bei den beiden anderen Gleichungen weiß ich nciht wie man 15 teilt 3a -4 bzw. 15 teilt 3a +7 weiter auflösen soll.
|
Profil
|
fru
Senior
Dabei seit: 03.01.2005
Mitteilungen: 21456
Wohnort: Wien
| Beitrag No.18, eingetragen 2007-12-16
|
Ja, Deine zweite Lösung ist korrekt.
Ob es eine dritte und/oder vierte Lösung gibt, hängt nun davon ab, ob es ganze Zahlen a und/oder b gibt, sodaß 3a-4 bzw. 3b+7 durch 15 teilbar ist.
Das solltest Du eigentlich schon selbst herausfinden können. Als kleinen Tip gebe ich Dir noch:
Wenn eine Zahl durch 15 teilbar ist, so ist sie auch durch 3 teilbar  .
|
Profil
|
hoffnungslos
Ehemals Aktiv
Dabei seit: 01.11.2007
Mitteilungen: 23
| Beitrag No.19, eingetragen 2007-12-17
|
Okay.
Vielen Dank für deine Hilfe.
|
Profil
|
Haeslein hat die Antworten auf ihre/seine Frage gesehen.
Haeslein hat selbst das Ok-Häkchen gesetzt. |
|
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2023 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die
Nutzungsbedingungen,
die Distanzierung,
die Datenschutzerklärung und das Impressum.
[Seitenanfang]
|
Home / Seite ohne Frame
Wie unterstütze ich den Matheplaneten mit Geld?
