Vielfachsummendarstellung=>ggt < Algebra < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Beweise oder widerlege:
ax+by=1 => ggt(a,b)=1 mit x,y [mm] \in \IZ [/mm] |
Hallo,
ich hab mir n paar beispiele überlegt um zu gucken ob ein einfaches gegenbeispiel existiert. hab leider keins gefunden :-( was dann wohl heißt, dass die aussage richtig ist und man sie beweisen muss.
ich dachte man könnte über die primfaktorzerlegungvon a und b agumentieren, dass beide keine gemeinsamen primfaktoren haben und somit der ggt(a,b)=1 sein muss. aber irgendwie hört sich das sehr schwammig an.
hat vielleicht jemand nen tipp, wie man da noch anders ran gehen kann?
wäre auf jeden fall dankbar für ne gute idee.
schöne grüße,
grafzahl123
|
|
| |
|
moin,
Um die Aussage schön zu zeigen solltest du folgendes zeigen oder (aus der Vorlesung zB) wissen - jeweils für alle $a,b,x,y,z [mm] \in \IZ$ [/mm] und [mm] $\mid$ [/mm] als Zeichen für "teilt":
1. $ggT(a,b) [mm] \mid [/mm] a$ sowie $ggT(a,b) [mm] \mid [/mm] b$
2. Aus $x [mm] \mid [/mm] y$ folgt $x [mm] \mid [/mm] y*z$
3. Aus $x [mm] \mid [/mm] y$ und $x [mm] \mid [/mm] z$ folgt $x [mm] \mid [/mm] (y+z)$
Wenn du die drei Aussagen hast so kannst du etwas sehr feines für deinen $ggT$ folgern, wodurch er 1 sein muss.
lg
Schadow
|
|
|
| |
|
danke erstmal für deine antwort!
ich hab das mal versucht:
1|a und 1|b
=> 1|a*x und 1|b*y , mit x,y [mm] \in \IZ
[/mm]
=> 1|a*x+b*y
aber damit hab ich ja noch nicht gezeigt, dass der ggt(a,b)=1 sein muss, oder? oder hab ich deinen tipp falsch interpretiert?
|
|
|
| |
|
Hallo grafzahl,
> ich hab das mal versucht:
> 1|a und 1|b
Das ist trivial. Daraus wird nichts zu folgern sein.
> => 1|a*x und 1|b*y , mit x,y [mm]\in \IZ[/mm]
> => 1|a*x+b*y
>
> aber damit hab ich ja noch nicht gezeigt, dass der
> ggt(a,b)=1 sein muss, oder? oder hab ich deinen tipp falsch
> interpretiert?
So siehts aus.
Was Du da gerade beweisen willst/sollst, ist das [mm] [http://de.wikipedia.org/wiki/Lemma_von_B%C3%A9zout] [/mm] Lemma von Bézout [/url]. Bei dem Link steht auch ein Beweis. Versuch den mal nachzuvollziehen und dann für [mm] \ggT{(a,b)}=1 [/mm] zu vereinfachen. Dann kommst Du bestimmt auch darauf, wozu der Tipp gut war.
Grüße
reverend
|
|
|
| |
|
danke für den tipp!
okay, dann auf ein neues 
wir haben d:=ax+by mit x,y aus Z, dann folgt daraus, dass gilt ggt(a,b)|a und ggt(a,b)|b und ggt(a,b)|d. da d=1 folgt daraus, dass ggt(a,b)|1 gilt. also ist ggt(a,b)=1
vielleicht so?
|
|
|
| |
|
Hallo nochmal,
> okay, dann auf ein neues
> wir haben d:=ax+by mit x,y aus Z, dann folgt daraus, dass
> gilt ggt(a,b)|a und ggt(a,b)|b und ggt(a,b)|d. da d=1 folgt
> daraus, dass ggt(a,b)|1 gilt. also ist ggt(a,b)=1
>
> vielleicht so?
Alles richtig. Das blau Markierte kannst Du sogar noch weglassen.
Eine übrigens selten beachtete Tatsache ist, dass aus d=1 auch folgt: [mm] \ggT{(x,y)}=1. [/mm] Diese Beobachtung ist manchmal (zugegeben selten) auch nützlich.
Unter Beibehaltung Deiner Beweisstruktur würde ich übrigens [mm] g:=\ggT{(a,b)} [/mm] definieren mit [mm] a=g*\alpha [/mm] und [mm] b=g*\beta. [/mm] Dann ist [mm] d=ax+by=g\alpha{x}+g\beta{y}=g(\alpha{x}+\beta{y}). [/mm] Also gilt $g|d$. Aus $d=1$ folgt daher $g=1$.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 23:42 Fr 16.11.2012 | | Autor: | abakus |
> Beweise oder widerlege:
> ax+by=1 => ggt(a,b)=1 mit x,y [mm]\in \IZ[/mm]
Hallo,
indirekt geht das schnell.
Annahme: ggT(a,b)=k mit k>1
Daraus folgt
a=m*k und b=n*k (mit teilerfremden m,n [mm]\in \IZ[/mm]).
Dann ist ax+by=k(mx+ny) durch k teilbar und kann somit nicht 1 sein.
Gruß Abakus
EDIT: Ich sehe gerade, dass das so ziemlich der bereits vorgestellten Variante entspricht.
> Hallo,
> ich hab mir n paar beispiele überlegt um zu gucken ob ein
> einfaches gegenbeispiel existiert. hab leider keins
> gefunden :-( was dann wohl heißt, dass die aussage richtig
> ist und man sie beweisen muss.
> ich dachte man könnte über die primfaktorzerlegungvon a
> und b agumentieren, dass beide keine gemeinsamen
> primfaktoren haben und somit der ggt(a,b)=1 sein muss. aber
> irgendwie hört sich das sehr schwammig an.
>
> hat vielleicht jemand nen tipp, wie man da noch anders ran
> gehen kann?
> wäre auf jeden fall dankbar für ne gute idee.
>
> schöne grüße,
> grafzahl123
|
|
|
|
