matheraum.de
Raum für Mathematik
Offene Informations- und Nachhilfegemeinschaft

Für Schüler, Studenten, Lehrer, Mathematik-Interessierte.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Forenbaum
^ Forenbaum
Status Mathe
  Status Schulmathe
    Status Primarstufe
    Status Mathe Klassen 5-7
    Status Mathe Klassen 8-10
    Status Oberstufenmathe
    Status Mathe-Wettbewerbe
    Status Sonstiges
  Status Hochschulmathe
    Status Uni-Analysis
    Status Uni-Lin. Algebra
    Status Algebra+Zahlentheo.
    Status Diskrete Mathematik
    Status Fachdidaktik
    Status Finanz+Versicherung
    Status Logik+Mengenlehre
    Status Numerik
    Status Uni-Stochastik
    Status Topologie+Geometrie
    Status Uni-Sonstiges
  Status Mathe-Vorkurse
    Status Organisatorisches
    Status Schule
    Status Universität
  Status Mathe-Software
    Status Derive
    Status DynaGeo
    Status FunkyPlot
    Status GeoGebra
    Status LaTeX
    Status Maple
    Status MathCad
    Status Mathematica
    Status Matlab
    Status Maxima
    Status MuPad
    Status Taschenrechner

Gezeigt werden alle Foren bis zur Tiefe 2

Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Dt. Schulen im Ausland: Mathe-Seiten:Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenDiskrete MathematikEuklidischer Algorithmus
Foren für weitere Studienfächer findest Du auf www.vorhilfe.de z.B. Astronomie • Medizin • Elektrotechnik • Maschinenbau • Bauingenieurwesen • Jura • Psychologie • Geowissenschaften
Forum "Diskrete Mathematik" - Euklidischer Algorithmus
Euklidischer Algorithmus < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Diskrete Mathematik"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Euklidischer Algorithmus: Bestimme alle x,y für die gilt
Status: (Frage) beantwortet Status 
Datum: 14:14 So 30.07.2017
Autor: EmreCabber

Aufgabe
2a) a := 5133 und b := 5782: ggT(5133,5782)=?
2b) Bestimmen Sie alle x,y aus Z, für die gilt -5133x + 5782y = 1829
2c) Bestimmen Sie die kleinste positive ganze Zahl x aus Z, so dass gilt:
3x [mm] \equiv [/mm] 19 (mod 31) und 4x [mm] \equiv [/mm] 13 (mod 41):

[Dateianhang nicht öffentlich]


Aufgabe a habe ich durch den Euklidischen Algorithmus lösen können, nämlich ist der ggT = 59.

Nun war ich bei uns in der Universität in der Mathelerngruppe und auch die Mathematiker aus den höheren Semestern konnten mir Aufgabe 2c und 2b nicht erklären. Ich weiß, dass man a für b und c braucht.

Ich habe diese Frage auch in folgenden Foren auf anderen Internetseiten gestellt:

Ich werde die gleiche Frage auch auf http://www.onlinemathe.de/ und http://www.matheplanet.com stellen. Über eine Erklärung wie man zur Lösung kommt und auch wieso man es genau so macht wäre ich sehr dankbar!

Mit freundlichen Grüßen


bei 2c hänge ich am erweiterten euklidischen algorithmus:

Zur b eventuell kann hier jemand ansetzen?

de.wikipedia.org/wiki/Erweiterter_euklidischer_Algorithmus

So nun habe ich diesen mal angewendet aber komme bei t auf -9,9 und danach kommen nur noch so krumme Zahlen irgendwas muss da ja falsch sein. Ich habe auch irgendwo die Formel x-(g*y) gelesen eventuell kann hier jemand was mit anfangen?

a= 5133, b= 5782, q=0, s= s, t=t
a=5782, b= 5133, q=1, s= s, t=t
a=5133, b= 649, q=7, s=s, t=t
a=649, b=590, q=1; s=s, t=t
a=590, b=59, q=10, s=s, t=t
a=59, b=0, q=q, s=s, t=t

soweit in Ordnung. Nun nutze ich die Formel x= s*a + t*b und setze Rückwirkend ein.

Da in der letzten Zeile b=0 ist nehmen wir hier für t einen beliebigen Wert denn 0*irgendwas = 0. Und für s nehmen wir einfach 1.

-> 59= 59*1 + 0*0

a= 5133, b= 5782, q=0, s= s, t=t
a=5782, b= 5133, q=1, s= s, t=t
a=5133, b= 649, q=7, s=s, t=t
a=649, b=590, q=1; s=s, t=t
a=590, b=59, q=10, s=0, t=t
a=59, b=0, q=q, s=1, t=0

Für die vorletzte Zeile nehmen wir für s den Wert von t dadrunter usw.

-> 590= 0*590+ 59*t -> t=10

a= 5133, b= 5782, q=0, s= s, t=t
a=5782, b= 5133, q=1, s= s, t=t
a=5133, b= 649, q=7, s=s, t=t
a=649, b=590, q=1; s=10, t=t
a=590, b=59, q=10, s=0, t=10
a=59, b=0, q=q, s=1, t=0

Nun kommt mein Problem.

649=10*649+t*590
<->
649=6490+590t -> t= -9,9

-9,9 ist aber nicht eine ganze Zahl.. Und wenn ich dann mit -9,9 weitermache wird es schlimmer. Kann hier jemand helfen?

2c konnte ich lösen :)

Dateianhänge:
Anhang Nr. 1 (Typ: png) [nicht öffentlich]
        
Bezug
Euklidischer Algorithmus: Antwort
Status: (Antwort) fertig Status 
Datum: 18:12 So 30.07.2017
Autor: leduart

Hallo
du kannst doch den ggT also 59 als Linearkombination der 2 Zahlen schreiben? und 1829=31*59 hilft das?
zu c) suche das Inverse von 3 mod 31 und multipliziere damit, oder einfacher 3*10=-1 mod 31
das hilft um -x zu finden und daraus x.
es ist dasselbe, wie rechnen mit rationalen Zahlen wo [mm] x=19*3^{-1} [/mm] nur darf man nicht [mm] 3^{-1}=1/3 [/mm] schreiben, sondern sucht das Inverse, ebenso bei 4x , das Inverse zu 4
Gruß ledum

Bezug
                
Bezug
Euklidischer Algorithmus: Frage (reagiert)
Status: (Frage) reagiert/warte auf Reaktion Status 
Datum: 18:51 So 30.07.2017
Autor: EmreCabber

Die 2 c habe ich mittlerweile lösen können. Bei b hänge ich am erweiterten euklidischen algorithmus fest hier mein Stand der Dinge:

https://de.wikipedia.org/wiki/Erweiterter_euklidischer_Algorithmus

So nun habe ich diesen mal angewendet aber komme bei t auf -9,9 und danach kommen nur noch so krumme Zahlen irgendwas muss da ja falsch sein. Ich habe auch irgendwo die Formel x-(g*y) gelesen eventuell kann hier jemand was mit anfangen?

a= 5133, b= 5782, q=0, s= s, t=t
a=5782, b= 5133, q=1, s= s, t=t
a=5133, b= 649, q=7, s=s, t=t
a=649, b=590, q=1; s=s, t=t
a=590, b=59, q=10, s=s, t=t
a=59, b=0, q=q, s=s, t=t

soweit in Ordnung. Nun nutze ich die Formel x= s*a + t*b und setze Rückwirkend ein.

Da in der letzten Zeile b=0 ist nehmen wir hier für t einen beliebigen Wert denn 0*irgendwas = 0. Und für s nehmen wir einfach 1.

-> 59= 59*1 + 0*0

a= 5133, b= 5782, q=0, s= s, t=t
a=5782, b= 5133, q=1, s= s, t=t
a=5133, b= 649, q=7, s=s, t=t
a=649, b=590, q=1; s=s, t=t
a=590, b=59, q=10, s=0, t=t
a=59, b=0, q=q, s=1, t=0

Für die vorletzte Zeile nehmen wir für s den Wert von t dadrunter usw.

-> 590= 0*590+ 59*t -> t=10

a= 5133, b= 5782, q=0, s= s, t=t
a=5782, b= 5133, q=1, s= s, t=t
a=5133, b= 649, q=7, s=s, t=t
a=649, b=590, q=1; s=10, t=t
a=590, b=59, q=10, s=0, t=10
a=59, b=0, q=q, s=1, t=0

Nun kommt mein Problem.

649=10*649+t*590
<->
649=6490+590t -> t= -9,9

-9,9 ist aber nicht eine ganze Zahl.. Und wenn ich dann mit -9,9 weitermache wird es schlimmer. Kann hier jemand helfen?

Bezug
        
Bezug
Euklidischer Algorithmus: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 18:50 So 30.07.2017
Autor: EmreCabber

Aufgabe
Erweiterte euklidische Algorithmus

https://de.wikipedia.org/wiki/Erweiterter_euklidischer_Algorithmus

So nun habe ich diesen mal angewendet aber komme bei t auf -9,9 und danach kommen nur noch so krumme Zahlen irgendwas muss da ja falsch sein. Ich habe auch irgendwo die Formel x-(g*y) gelesen eventuell kann hier jemand was mit anfangen?

a= 5133, b= 5782, q=0, s= s, t=t
a=5782, b= 5133, q=1, s= s, t=t
a=5133, b= 649, q=7, s=s, t=t
a=649, b=590, q=1; s=s, t=t
a=590, b=59, q=10, s=s, t=t
a=59, b=0, q=q, s=s, t=t

soweit in Ordnung. Nun nutze ich die Formel x= s*a + t*b und setze Rückwirkend ein.

Da in der letzten Zeile b=0 ist nehmen wir hier für t einen beliebigen Wert denn 0*irgendwas = 0. Und für s nehmen wir einfach 1.

-> 59= 59*1 + 0*0

a= 5133, b= 5782, q=0, s= s, t=t
a=5782, b= 5133, q=1, s= s, t=t
a=5133, b= 649, q=7, s=s, t=t
a=649, b=590, q=1; s=s, t=t
a=590, b=59, q=10, s=0, t=t
a=59, b=0, q=q, s=1, t=0

Für die vorletzte Zeile nehmen wir für s den Wert von t dadrunter usw.

-> 590= 0*590+ 59*t -> t=10

a= 5133, b= 5782, q=0, s= s, t=t
a=5782, b= 5133, q=1, s= s, t=t
a=5133, b= 649, q=7, s=s, t=t
a=649, b=590, q=1; s=10, t=t
a=590, b=59, q=10, s=0, t=10
a=59, b=0, q=q, s=1, t=0

Nun kommt mein Problem.

649=10*649+t*590
<->
649=6490+590t -> t= -9,9

-9,9 ist aber nicht eine ganze Zahl.. Und wenn ich dann mit -9,9 weitermache wird es schlimmer. Kann hier jemand helfen?

Bezug
                
Bezug
Euklidischer Algorithmus: Antwort
Status: (Antwort) fertig Status 
Datum: 20:28 So 30.07.2017
Autor: angela.h.b.


> Erweiterte euklidische Algorithmus
>  
> https://de.wikipedia.org/wiki/Erweiterter_euklidischer_Algorithmus
>  
> So nun habe ich diesen mal angewendet aber komme bei t auf
> -9,9 und danach kommen nur noch so krumme Zahlen irgendwas
> muss da ja falsch sein. Ich habe auch irgendwo die Formel
> x-(g*y) gelesen eventuell kann hier jemand was mit
> anfangen?
>  
> a= 5133, b= 5782, q=0, s= s, t=t
>  a=5782, b= 5133, q=1, s= s, t=t
>  a=5133, b= 649, q=7, s=s, t=t
> a=649, b=590, q=1; s=s, t=t
>  a=590, b=59, q=10, s=s, t=t
>  a=59, b=0, q=q, s=s, t=t


Hallo,

[willkommenmr].

Durch Obiges steige ich schlecht durch, es wäre echt besser gewesen, hättest Du die Gleichungen hingeschrieben:

5133 = 0·5782 + 5133  ==> 5133 = 5133 - 0·5782   
5782 = 1·5133 + 649  ==> 649 = 5782 - 1·5133   
5133 = 7·649 + 590   ==> 590 = 5133 - 7·649   
649 = 1·590 + 59  ==> 59 = 649 - 1·590   
590 = 10·59

Du bekommst als ggt die 59.

Jetzt rückwärts:

59 = 649 - 1·590
   =649- 1*(5133-7*649)=8*649-1*5133
   =8*(5782 - 1·5133)-1*5133
   =8*5782-9*5133

Mir ist es bei Deiner Notation zu mühsam, den Fehler zu suchen - aber jetzt solltest Du sehen, wie es geht.

LG Angela



>  
> soweit in Ordnung. Nun nutze ich die Formel x= s*a + t*b
> und setze Rückwirkend ein.
>  
> Da in der letzten Zeile b=0 ist nehmen wir hier für t
> einen beliebigen Wert denn 0*irgendwas = 0. Und für s
> nehmen wir einfach 1.
>  
> -> 59= 59*1 + 0*0
>  
> a= 5133, b= 5782, q=0, s= s, t=t
>  a=5782, b= 5133, q=1, s= s, t=t
>  a=5133, b= 649, q=7, s=s, t=t
> a=649, b=590, q=1; s=s, t=t
>  a=590, b=59, q=10, s=0, t=t
>  a=59, b=0, q=q, s=1, t=0
>  
> Für die vorletzte Zeile nehmen wir für s den Wert von t
> dadrunter usw.
>  
> -> 590= 0*590+ 59*t -> t=10
>  
> a= 5133, b= 5782, q=0, s= s, t=t
>  a=5782, b= 5133, q=1, s= s, t=t
>  a=5133, b= 649, q=7, s=s, t=t
> a=649, b=590, q=1; s=10, t=t
>  a=590, b=59, q=10, s=0, t=10
>  a=59, b=0, q=q, s=1, t=0
>  
> Nun kommt mein Problem.
>  
> 649=10*649+t*590
> <->
>  649=6490+590t -> t= -9,9

>  
> -9,9 ist aber nicht eine ganze Zahl.. Und wenn ich dann mit
> -9,9 weitermache wird es schlimmer. Kann hier jemand
> helfen?


Bezug
                        
Bezug
Euklidischer Algorithmus: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 20:40 So 30.07.2017
Autor: EmreCabber

Ich habe mir echt Mühe gegeben das man das nachvollziehen kann aber für die Zukunft weiß ich Bescheid! Vielen Dank soweit!

Für die 2b)

Habe nun raus 9·(-87) + 8·98 =1

Meine Gleichung will ja −87×+98y=31 heißt ich rechne ⋅31

Bekomme ich

(9⋅31)⋅−87+(8⋅31)⋅98=31

Heißt eine Lösung ist x=279 und y=248.

Wie gebe ich nun mathematisch korrekt die ganze Lösungsmenge an? Ich habe jetzt ja nur eine und anscheinend gibt es mehrere laut Aufgabenstellung :-) Liegen alle in Z

Bezug
                                
Bezug
Euklidischer Algorithmus: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 21:25 So 30.07.2017
Autor: angela.h.b.


> Ich habe mir echt Mühe gegeben das man das nachvollziehen
> kann aber für die Zukunft weiß ich Bescheid! Vielen Dank
> soweit!
>  
> Für die 2b)
>  
> Habe nun raus 9·(-87) + 8·98 =1

Hallo,

zur geposteten 2b) paßt das nicht.
Bist Du mit Threads durcheinandergekommen?

LG Angela

>  
> Meine Gleichung will ja −87×+98y=31 heißt ich rechne
> ⋅31
>  
> Bekomme ich
>
> (9⋅31)⋅−87+(8⋅31)⋅98=31
>  
> Heißt eine Lösung ist x=279 und y=248.
>  
> Wie gebe ich nun mathematisch korrekt die ganze
> Lösungsmenge an? Ich habe jetzt ja nur eine und
> anscheinend gibt es mehrere laut Aufgabenstellung :-)
> Liegen alle in Z


Bezug
                                        
Bezug
Euklidischer Algorithmus: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 21:29 So 30.07.2017
Autor: EmreCabber

Hey, nein ist alles richtig. Wir haben den ggT aus a 59 mit der Gleichung geteilt und dann den euklidischen Alg. rückwärts eingesetzt. Wenn du die Zahlen einsetzt geht es auch auf. Nun fehlt nur noch die Bestimmmung ALLER :) lösungen. das ist ja nur eine spezielle gibt mehrere :) lg

Bezug
                                
Bezug
Euklidischer Algorithmus: Antwort
Status: (Antwort) fertig Status 
Datum: 06:37 Mo 31.07.2017
Autor: angela.h.b.


> Ich habe mir echt Mühe gegeben das man das nachvollziehen
> kann aber für die Zukunft weiß ich Bescheid! Vielen Dank
> soweit!
>  
> Für die 2b)
>  
> Habe nun raus 9·(-87) + 8·98 =1
>  
> Meine Gleichung will ja −87×+98y=31 heißt ich rechne
> ⋅31
>  
> Bekomme ich
>
> (9⋅31)⋅−87+(8⋅31)⋅98=31
>  
> Heißt eine Lösung ist x=279 und y=248.

Hallo,

Du hattest herausgefunden

59=8*5782-9*5133,

zu lösen war 1829=-5133x + 5782y.

1829=31*59,

also ist

1829=31*(8*5782-9*5133)=-279*5133+248*5782,

womit man eine Lösung gefunden hat: x=279, y=248.

Diese Lösung hast Du auch gefunden. Gut.

>  
> Wie gebe ich nun mathematisch korrekt die ganze
> Lösungsmenge an? Ich habe jetzt ja nur eine und
> anscheinend gibt es mehrere laut Aufgabenstellung :-)
> Liegen alle in Z

Ja. Wir haben bisher eine spezielle Lösung gefunden.
Um alle Lösungen zu finden, müssen wir die Lösungsmenge der homogenen Gleichung
0=-x*5133+y*5782 <==> 0=-x*87+y*98
in [mm] \IZ [/mm] bestimmen.

Jede Summe aus spezieller und homogener Lösung ist eine Lösung der zu bearbeitenden Gleichung.

LG Angela


Bezug
                                        
Bezug
Euklidischer Algorithmus: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 10:10 Mo 31.07.2017
Autor: EmreCabber

Liebe Angela vielen Dank für deine Erklärung. Jedoch stellt sich mir hier immer noch die Frage wie ich das aufschreibe? Wenn ich das so wie du sagst also die beiden Summen nehme geht das nicht auf oder ich mach hier was falsch? LG

Bezug
                                                
Bezug
Euklidischer Algorithmus: Antwort
Status: (Antwort) fertig Status 
Datum: 12:11 Mo 31.07.2017
Autor: leduart

Hallo
du bist in mehreren Foren unterwegs! sollen wir immer alle durchforsten, welche Antworten du schon hast?
http://www.onlinemathe.de/forum/Euklidischer-Algorithmus-Bestimme-alle-xy-fuer-d
http://matheplanet.com/matheplanet/nuke/html/viewtopic.php?topic=230274&post_id=1676813
Damit beschäftigst du zu viele Leute!
Gruß leduart

Bezug
                                                        
Bezug
Euklidischer Algorithmus: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 12:26 Mo 31.07.2017
Autor: EmreCabber

Ich habe doch gesagt welche Aufgabe mir nur noch fehlt und auch beim erstellen mit angegeben, wo ich die Fragen noch alle stelle sehe hier das Problem nicht. Da meine Klausur übermorgen ist und es etwas dringend ist, frage ich in mehreren Foren, welche ich nach den Regeln auch mit angegeben habe.

Mir fehlt nur noch die korrekte Angabe der Lösungsmenge..

Bezug
                                                                
Bezug
Euklidischer Algorithmus: Antwort
Status: (Antwort) fertig Status 
Datum: 17:21 Mo 31.07.2017
Autor: leduart

Hallo
für ne Klausurvirbereitung sollte man nicht fertige Lösungen suchen, sondern selbst mal was probieren.
und die eine oder andere Lösung von 0=-x*98+y*87  oder x*98=y*87   ist doch einfach z sehen?
Gruß ledum


Bezug
                                                
Bezug
Euklidischer Algorithmus: Antwort
Status: (Antwort) fertig Status 
Datum: 18:11 Mo 31.07.2017
Autor: angela.h.b.


> Liebe Angela vielen Dank für deine Erklärung. Jedoch
> stellt sich mir hier immer noch die Frage wie ich das
> aufschreibe? Wenn ich das so wie du sagst also die beiden
> Summen nehme geht das nicht auf oder ich mach hier was
> falsch? LG  

Hallo,

ich verstehe nicht, was Du meinst. Was "geht nicht auf"?

Du hast die spezielle Lösung x=279, y=248.

Lösungsmenge in [mm] \IZ [/mm] von 0=-x*87+y*98 ist

[mm] L_h=\{(98t,87t)| t\in\IZ\}, [/mm]

die Lösungsmenge der Ausgangsgleichung ist somit

[mm] L=\{(279+98t, 248+87t)|t\in\IZ\}. [/mm]

Für jedes [mm] t\in \IZ [/mm] bekommst Du eine Lösung.

LG Angela



Bezug
                                                        
Bezug
Euklidischer Algorithmus: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 19:39 Mo 31.07.2017
Autor: EmreCabber

Liebe Angela, nach deinem Vorschlag wäre die Lösungsmenge also

L={(279+87t,248+98t}

-5133x + 5782y = 1829

Setzten wir t=0,t=1,t=2 in die Lösungsmenge ein.

279+87t ... t=0 -> 279 , t=1 -> 366, t=2 -> 453
248+95t ... t=0 -> 248 , t=1 -> 346, t=2 -> 444

So setzen wir nun t nun in die Gleichung ein..

t=0 -5133*(279) + 5782*(248) = 1829 passt

t=1 -5133*(366) + 5782*(346) = 121894 passt nicht

t=2 ... = 241959

passt auch nicht. Das meine ich mit geht nicht auf oder mach ich was falsch? Intuitiv hätte ich dir zugestimmt. LG

Bezug
                                                                
Bezug
Euklidischer Algorithmus: Antwort
Status: (Antwort) fertig Status 
Datum: 22:52 Mo 31.07.2017
Autor: angela.h.b.


> Liebe Angela, nach deinem Vorschlag wäre die Lösungsmenge
> also
>  
> L={(279+87t,248+98t}
>  
> -5133x + 5782y = 1829
>  
> Setzten wir t=0,t=1,t=2 in die Lösungsmenge ein.
>  
> 279+87t ... t=0 -> 279 , t=1 -> 366, t=2 -> 453
>  248+95t ... t=0 -> 248 , t=1 -> 346, t=2 -> 444

>  
> So setzen wir nun t nun in die Gleichung ein..
>  
> t=0 -5133*(279) + 5782*(248) = 1829 passt
>  
> t=1 -5133*(366) + 5782*(346) = 121894 passt nicht
>  
> t=2 ... = 241959
>  
> passt auch nicht. Das meine ich mit geht nicht auf oder
> mach ich was falsch?

Hallo,

Du hast alles richtig verstanden.
Die homogene Gleichung muß heißen 0=-x*5133+y*5782 <==> 0=-x*87+y*98.

Die 87 und 98 waren zuvor vertauscht, ich habe es korrigiert.

LG Angela


> Intuitiv hätte ich dir zugestimmt. LG


Bezug
                                                                        
Bezug
Euklidischer Algorithmus: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 22:59 Mo 31.07.2017
Autor: EmreCabber

Ich danke dir. Darf ich dich noch Fragen wieso da jetzt 0= steht und nicht das was in der Aufgabe gefordert ist? Weiterhin hätte ich die zweite Gleichung also 87x98t= 1 gesetzt und auch nicht hier 0. Über eine kurze Erklärung wäre ich sehr dankbar!

Bezug
                                                                                
Bezug
Euklidischer Algorithmus: Antwort
Status: (Antwort) fertig Status 
Datum: 23:54 Mo 31.07.2017
Autor: leduart

Hallo
die Erklärung konntest du im post von Angela doch lesen:
“Jede Summe aus spezieller und homogener Lösung ist eine Lösung der zu bearbeitenden Gleichung. "
ax+by=c hat die Losung x1,y1
wenn du dazu eine Lösung von ax+by=0 addierst  also x2,y2
also neue Lösung x1+x2,y1+y2
dann überlege, warum das auch eine Lösung der ersten Gleichung ist
Gruß ledum


Bezug
                                                                                        
Bezug
Euklidischer Algorithmus: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 00:29 Di 01.08.2017
Autor: EmreCabber

Lieber leduart ich habe das von Angela gelesen aber nicht verstanden deswegen habe ich ja gefragt.

Weil die Gleichung mit Ergebnis 1829 ist ja inhomogen, weil das Ergebnis ja nicht 0 ist oder sehe ich das falsch? Wieso wurde aus einer inhomogenen Gleichung nun eine bzw. 2 homogene? Dein Ansatz bringt mich persönlich auch nicht weiter. LG

Bezug
                                                                                                
Bezug
Euklidischer Algorithmus: Antwort
Status: (Antwort) fertig Status 
Datum: 05:29 Di 01.08.2017
Autor: angela.h.b.


> Weil die Gleichung mit Ergebnis 1829 ist ja inhomogen, weil
> das Ergebnis ja nicht 0 ist oder sehe ich das falsch?
> Wieso
> wurde aus einer inhomogenen Gleichung nun eine bzw. 2
> homogene?

Hallo,

das habe ich so gemacht, weil es so funktioniert,
und daß es so funktioniert, lernt man in der Vorlesung bzw. beim Studium einschlägiger Literatur - und einigen mag die Idee auch ganz von alleine kommen.

> Dein Ansatz bringt mich persönlich auch nicht
> weiter. LG

Das ist schade.
Vielleicht hast Du Dich nicht ganz genau mit dem beschäftigt, was leduart sagt.
Meist reicht das Lesen nicht, man muß es mit Stift und Papier nachvollziehen.

Nochmal:
wir haben eine Gleichung der Gestalt ax+by=c,
und wir stellen uns vor, wir hätten irgendwie eine Lösung [mm] (x_s,y_s) [/mm] gefunden,
es sei also [mm] ax_s+by_s=c. [/mm]
Weiter stellen wir uns vor, wir hätten eine Lösung [mm] (x_h, y_h) [/mm] der zugehörigen homogenen Gleichung ax+by=0,
es sei also [mm] ax_h+by_h=0. [/mm]
leduart sagst, daß Du mal nachrechnen, sollst, daß [mm] (x_s+x_h, y_s+y_h) [/mm] ebenfalls eine Lösung der inhomogenen Gleichung ist, und daß Du das durch Einsetzen prüfen kannst.

Einsetzen: [mm] a(x_s+x_h)+b(y_s+y_h)=... [/mm] Rechne nach.

---
---

Kurz nochmal der Ablauf des Lösens der diophantischen linearen Gleichung
ax+by=c.
Offenbar ist dieser nicht ganz klar.

1.
ggT(a,b) bestimmen. Ich nenne ihn im Folgenden t. Ist c ein ganzzahliges Vielfaches des ggT, also c=dt, so hat die Gleichung eine Lösung.

2.
Mit dem erweiterten euklidischen Algorithmus Zahlen x',y'  bestimmen mit
ax'+by'=t.

3.
Folglich ist
a(dx')+b(dy')=dt=c,
und [mm] x_s=dx', y_s=dy' [/mm] eine Lösung der diophantischen Gleichung.

4.
Alle Lösungen der homogenen diophantischen Gleichung ax+by=0 bestimmen.
Dazu zunächst durch den ggT dividieren, man bekommt
[mm] \bruch{a}{t}x+\bruch{b}{t}y=0, [/mm]
die ganzen Zahlen [mm] \bruch{a}{t} [/mm] und [mm] \bruch{b}{t} [/mm] sind teilerfremd,
[mm] x_h=-\bruch{b}{t}, y_h=\bruch{a}{t} [/mm] ist eine Lösung der homogenen Gleichung,und alle ganzzahligen Vielfachen davon ebenfalls.

5.
Wie oben erklärt hat man mit [mm] x=x_s+k*x_h, y=y_s+k*y_h [/mm] mit [mm] k\in \IZ [/mm] die Gesamtheit der Lösungen gefunden.

LG Angela





Bezug
                                                                                
Bezug
Euklidischer Algorithmus: Antwort
Status: (Antwort) fertig Status 
Datum: 05:47 Di 01.08.2017
Autor: angela.h.b.


> Ich danke dir. Darf ich dich noch Fragen wieso da jetzt 0=
> steht

Wo jetzt genau?
Versuche bitte so zu schreiben, daß man ohne Studium des ganzen Threads weiß, worum es geht.
"=0" wird die Gleichung gesetzt, weil man die Menge der Lösungen der homogenen Gleichung benötigt,
wenn man die Lösungsmenge der inomogenen bestimmen möchte.

> und nicht das was in der Aufgabe gefordert ist?
> Weiterhin hätte ich die zweite Gleichung also 87x98t= 1
> gesetzt

>und auch nicht hier 0.

Wenn man die Lösungen der homogenen Gleichung sucht, kann man sie nicht =1 setzen.
Kommt halt darauf an, was man vor hat...


Vllt bist Du verwirrt, weil die Mitstreiter aus den anderen Foren die spezielle Lösung etwas anders finden als ich.

Wir hatten
59=-9*5133+8*5782

Ich:    
mit 31 multiplizieren liefert 59*31=-(9*31)*5133+(8*31)*5782 ,
eine spezielle Lsg ist [mm] x_s=9*31, y_s=8*31 [/mm]

Die anderen:
durch 59 dividieren liefert      1=-9*87+8*98,
mit 31 multiplizieren liefert 31=-(9*31)*87+(8*31)*98,
eine spezielle Lsg der Gleichung  59*31=-x*5133+y*5782
ist [mm] x_s=9*31, y_s=8*31. [/mm]



>Über eine kurze Erklärung

> wäre ich sehr dankbar!

Siehe meinen anderen Beitrag.
leduart hatte es auch schon erklärt.

LG Angela


Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Diskrete Mathematik"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.matheraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]