Das Lemma von Bezout |
| 01.11.2005, 15:32 | The_Lion | Auf diesen Beitrag antworten » | ||
| Das Lemma von Bezout ich möchte folgende Aufgabe posten, bei der ich nicht so klarkomme. Seien a,b€ Z teilerfremde ganze Zahlen. Beweist, dass folgende Gleichung x*a² + y*b = a-1 eine Lösung (x,y) € ZxZ hat. Das Lemma von Bezout besagt: der ggT zweier ganzer Zahlen ist darstellbar als g= x*a +y*b mit x,y € Z. Ich habe daran gedacht, den erweiterten euklidischen Algorithmus anzuwenden, aber hier sind VARIABLEN x und y gesucht, d.h. keine Zahlen. Vielleicht ein kleiner Tipp ? Ich habs auch schon durch Umormung der Gleichung x*a² + y*b = a-1 versucht. Dabei ging ich so vor: x*a² + y*b = a-1 <=> x*a² - a +y*b = -1 <=> a(x*a - 1) + y*b = -1 <=> -a(x*a -1) -y*b = 1 => ggT(-a, b) = 1, (Lemma v. Bezout). aber das steht ja auch schon in der Aufgabenstellung, dass beide teilerfremd sind. Hier ist es zwar ein "-a", das tut aber nix zut Sache. der zweite Versuch: x*a² + y*b = a-1 => ggT(a²,b) = a-1 aber wie komme ich nun auf die Zahlen x und y ? Danke. |
||||
| 01.11.2005, 16:02 | 4c1d | Auf diesen Beitrag antworten » | ||
| RE: Das Lemma von Bezout Hallo, So wie ich das sehe, bist du an dieser Stelle
ohne es zu ahnen schon fast fertig. Du gehst ja davon aus, dass es x',y' aus Z gibt, sodass ax'+by'=1. Jetzt musst du nur noch zeigen, dass sich x' immer als -(xa-1) für ein x aus Z und y' immer als -y für ein y aus Z darstellen lässt |
||||
| 01.11.2005, 16:10 | AD | Auf diesen Beitrag antworten » | ||
| RE: Das Lemma von Bezout @The_Lion Du besuchst nicht zufällig dieselbe Vorlesung wie Manja ? 
|
||||
| 01.11.2005, 16:13 | The_Lion | Auf diesen Beitrag antworten » | ||
doch, tue ich Arthur Dent 
Ich kenne sie aber wohl nicht.Habe zwar die Suchunktion benutzt, aber Ihr Thema hat den Titel "LinA 1", nach dem ich natürlich im Normalfall nicht suche
|
||||
| 01.11.2005, 16:31 | The_Lion | Auf diesen Beitrag antworten » | ||
ok, wie zeige ich denn, dass x'= -(xa-1) und y' = -y ? Muss ich die erste Gleichung , also xa²+yb = a-1 einfach nochmal nach -(xa-1) umformen ? Und dasselbe dann so umformen, um rauszubekommen was y ist ? -a(xa-1) -yb = 1 <=> - xa-1 = 1/a + (yb/a) und -a(xa-1) -yb = 1 <=> -yb = a(xa-1) +1 <=> -y = ( a(xa-1)+1)/b Wäre das so korrekt, um die Existenz von x' = -a(xa-1) und y'= -y nachzuweisen ? EDIT: xa² +yb = a-1 <=> x= (a-1-yb)/a² xa² +yb = a-1 <=> yb = a-1 - xa² <=> -y = - (a - 1 - xa²)/b Und die Terme auf der rechten Seite dann in dem anderen Kram einsetzen ? |
||||
| 01.11.2005, 16:38 | AD | Auf diesen Beitrag antworten » | ||
Also ich würde so vorgehen, wie ich das im anderen Thread schon angedeutet hatte: Aus folgt , und daraus kannst du mit dem erweiterten euklidischen Algorithmus ganze Zahlen mit ermitteln. Und wie du von diesem auf eine Lösungspaar von kommst, das überlasse ich nun wirklich dir.
|
||||
| Anzeige | ||||
|
|
||||
| 01.11.2005, 16:42 | The_Lion | Auf diesen Beitrag antworten » | ||
Im anderen Thread schreibst du auch, dass aus ggT(a,b) = 1 ggT(a²,b) = 1 folgt. Ist diese Folgerung wirklich so trivial ? |
||||
| 01.11.2005, 16:47 | AD | Auf diesen Beitrag antworten » | ||
Ja, ist sie: Nimm einfach mal das Gegenteil an, d.h. . Dann gibt es eine Primzahl , die ein Teiler von ist ... |
||||
| 01.11.2005, 17:01 | 4c1d | Auf diesen Beitrag antworten » | ||
Nein, die Idee wäre gewesen, die Existenz von x bzw. y auf diesem Wege aus der Existenz von x',y' zu schließen - aber das geht anscheinend doch nicht so einfach wie ich zuerst dachte. |
||||
| 01.11.2005, 17:04 | The_Lion | Auf diesen Beitrag antworten » | ||
Arthur Dent, Wieso die "42" auf deinem Avatar ?
|
||||
| 01.11.2005, 17:08 | AD | Auf diesen Beitrag antworten » | ||
Die interessantere Frage ist wohl: Wieso "1 : 2^267709" in meinem Benutzertitel? Aber das wird jetzt off-topic.
Ich hoffe, ist jetzt klar. |
||||
| 01.11.2005, 17:27 | The_Lion | Auf diesen Beitrag antworten » | ||
ich werd nochmal drüber nachdenken. |
||||
| 01.11.2005, 19:40 | The_Lion | Auf diesen Beitrag antworten » | ||
ok, ggT(a²,b) ist jetzt klar. Ich versuche gerade den erweiterten euklidischen Algorithmus anzuwenden und habe die erste Zeile auch fertig. ich hab z.B. sowas: a² = a², b=b, q= -y/x , r=(a-1)/x , u = 1, v= y/x, index k = 0 (in dieser Zeile) So in Ordnung ? In der zweiten Zeile könnte ich da was anstellen, damit dort sofort rest Null rauskommt. Wäre das so in Ordnung ? NACHTRAG: Wenn ggT(a²,b) = 1, dann weiss ich laut Gleichung aus der Aufgabenstellung xa²+yb = a-1 , dass a= 2 sein muss, denn so kommt rechts 1 raus. Kann ich damit was anfangen ? eigentlich nicht oder, da ich ja b nicht kenne. |
||||
| 01.11.2005, 21:14 | AD | Auf diesen Beitrag antworten » | ||
Diese Schlussweise ist völlig abwegig! 
Da du dich hier völlig verrannt hast: Ich hatte oben von einer Lösung der Gleichung gesprochen. Nun setze mal und . |
||||
| 02.11.2005, 00:47 | The_Lion | Auf diesen Beitrag antworten » | ||
ok, ich hatte mich total vertan, danke. habs nun begriffen,
|
||||
| 02.11.2005, 19:24 | The_Lion | Auf diesen Beitrag antworten » | ||
, aber nochmal dazu. Wenn a^2 und b teilerfremd sind, dann ist ggT(a^2,b) =1 doch darstellbar in der Form a^2x+ yb = 1 mit x,y € Z , was auch immer diese x,y sein mögen. Warum folgt daraus nicht a = 2 ? |
||||
| 02.11.2005, 19:31 | AD | Auf diesen Beitrag antworten » | ||
Aus ggT(a^2,b) =1 folgt: Es gibt x,y € Z mit a^2x+ yb = 1 . Und du ziehst daraus die wahnwitzige Schlussfolgerung: Für alle x,y € Z gilt a^2x+ yb = 1 .
|
||||
| 02.11.2005, 22:30 | The_Lion | Auf diesen Beitrag antworten » | ||
ok danke. jetzt hab ichs endlich verstanden. |
||||
| 23.02.2006, 21:02 | fsswsb | Auf diesen Beitrag antworten » | ||
Geschrieben von The_Lion - Das Lemma von Bezout Hallo, ich möchte folgende Aufgabe posten, bei der ich nicht so klarkomme. Seien a,b€ Z teilerfremde ganze Zahlen. Beweist, dass folgende Gleichung x*a² + y*b = a-1 eine Lösung (x,y) € ZxZ hat. Das Lemma von Bezout besagt: der ggT zweier ganzer Zahlen ist darstellbar als g= x*a +y*b mit x,y € Z. Falls a,b teilerfremd sind auch a², b teilerfremd, also ggt(a², b)=1. Es gibt also nach dem Lemma von Bezout ganze Zahlen xx und yy mit xx*a² + yy*b = 1 Diese Gleichung multipliziere ich mit a-1 und erhalte [xx*(a-1)]* a² + [yy*(a-1)]*b = a-1 Mit x = [xx*(a-1)] und y = [yy*(a-1)] habe ich somit die gesuchten ganzen Zahlen gefunden, die eine Lösung der Gleichung ergeben. |
||||
| 25.02.2006, 15:10 | fsswsb | Auf diesen Beitrag antworten » | ||
Geschrieben von The_Lion - Im anderen Thread schreibst du auch, dass aus ggT(a,b) = 1 ggT(a²,b) = 1 folgt. Ist diese Folgerung wirklich so trivial ? Wahrscheinlich verwechselst Du mich. Aber egal, ich will die Frage mal beantworten: Du kannst die Zahlen a und b in Ihre Primfaktoren zerlegen. Da ggT(a,b) = 1 taucht keine Primzahl in der Zerlegung von a in der Zerlegung von b auf. Der ggT wäre sonst größer oder gleich dem gemeinsamen Faktor. Die Primzahlenzerlegung von a² enthält aber die gleichen Primzahlen nur mit dem doppelten Exponenten. Es gibt also auch hier keinen gemeinsamen Primfaktor. Diese Überlegung gilt allerdings nur für a,b ungleich null. Aus ggT(a,b) = 1 folgt jedoch, dass diese Bedingung erfüllt ist. Naja, war vielleicht doch nicht ganz trivial. |
||||
| 25.02.2006, 20:41 | fsswsb | Auf diesen Beitrag antworten » | ||
Nein, das Lemma besagt doch nur, dass es zwei spezielle ganze Zahlen - ich habe sie mal xx und yy genannt - gibt, so dass a^2 * xx + b * yy = ggT(a^2,b) = 1. Dies trifft natürlich nicht auf jedes Zahlenpaar (x,y) zu. Die Aufgabe besteht darin zu zeigen, dass es Zahlen x,y gibt für die a^2*x + b*y = a-1. Falls a ungleich 2 ist für diese Lösung a^2*x + b*y auch nicht 1 sondern a-1. Die Lösung lautet vielmehr x = xx*(a-1) und y = yy*(a-1). |
||||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
