Zahlentheorie < Sonstiges < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 11:27 Sa 23.04.2005 | | Autor: | Ursus |
Hi Leute!
Ich hab mal wieder ein Problem bei dieser Zahlentheorie Aufgabe:
Es seien a,b [mm] \in \IN [/mm] mit (a,b)=1. Zeige: Jede natürliche Zahl n > ab kann dargestellt werden in der Form ax + by = n mit x,y [mm] \in \IN. [/mm]
Also mein Lösungsansatz:
mit dem Euklidischen Algorithmus könnte man ja folgendes berechnen:
ax + by = 1 wobei x [mm] \in \IZ [/mm] und y [mm] \in \IN [/mm] (o.B.d.A.)
Dann addiere ab =>
ax + by + ab = 1 + ab n:=1+ab
a(x+b) + by = n
Die Lösungen dieser Gleichung sollen ja nur aus [mm] \IN [/mm] sein. Also muss ich irgendwie zeigen, dass jetzt (x+b) [mm] \in \IN. [/mm]
Aber alle meiner Versuche scheiterten dies zu zeigen.
Kann mir bitte jemand einen Tipp geben,wie man das zeigen kann??
Ich habe diese Frage auf keinen anderen Seiten, Foren gepostet.
Vielen, vielen Dank im Voraus!!
mfg URSUS
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 14:32 Sa 23.04.2005 | | Autor: | Stefan |
Hallo Ursus!
Erst einmal ist dein Beweis falsch, da du die Behauptung ja für alle $n>ab$ zeigen sollst und daher nicht einfach $n:=ab+1$ setzen darfst.
Die Grundidee anfangs war aber richtig:
Es gibt [mm] $\tilde{x},\tilde{y} \in \IZ$ [/mm] mit
[mm] $a\tilde{x}+ [/mm] b [mm] \tilde{y} [/mm] =1$.
Die Multiplikation mit $n>ab$ auf beiden Seiten liefert:
[mm] $a\tilde{x}n [/mm] + b [mm] \tilde{y}n [/mm] = n$.
Sind nun bereits [mm] $\tilde{x}>0$ [/mm] und [mm] $\tilde{y}>0$, [/mm] so ist nichts zu zeigen, denn dann setzen wir [mm] $x:=\tilde{x}n \in \IN$ [/mm] und [mm] $y:=\tilde{y}n \in \IN$.
[/mm]
Der Fall [mm] $\tilde{x}<0$ [/mm] und [mm] $\tilde{y}<0$ [/mm] kann nicht auftreten, denn dann wäre
[mm] $a\tilde{x}n [/mm] + [mm] b\tilde{y}n [/mm] < 0 <n$.
Es genügt also, oBdA den Fall [mm] $\tilde{x}>0$ [/mm] und [mm] $\tilde{y}<0$ [/mm] zu betrachten.
Man beachte, dass aus
[mm] $a\tilde{x}n [/mm] + b [mm] \tilde{y}n [/mm] = n$
für alle $k [mm] \in \IZ$ [/mm] folgt:
[mm] $a(\tilde{x}n [/mm] - kb) + [mm] b(\tilde{y}n [/mm] + ka) = n$.
Setzen wir also für [mm] $k\in\IZ$
[/mm]
[mm] $x_k [/mm] := [mm] \tilde{x}n [/mm] - kb$
und
[mm] $y_k:=\tilde{y}n [/mm] + ka$,
so genügt es zu zeigen:
Es gibt ein [mm] $k\in \IN$ [/mm] mit
[mm] $x_k>0$ [/mm] und [mm] $y_k>0$.
[/mm]
So, und jetzt kommt unsere Voraussetzung $n>ab$ ins Spiel.
Wir haben nämlich:
[mm] $a\tilde{x}n [/mm] + b [mm] \tilde{y}n [/mm] = n >ab$,
also:
[mm] $\underbrace{\frac{\tilde{x}n}{b}}_{>0} [/mm] + [mm] \underbrace{\frac{\tilde{y}n}{a}}_{<0} [/mm] = [mm] \frac{\tilde{x}n}{b} [/mm] - [mm] \underbrace{\frac{-\tilde{y}n}{a}}_{>0}>1$.
[/mm]
Dies bedeutet aber:
Es gibt ein $k [mm] \in \IN$ [/mm] mit
[mm] $\frac{-\tilde{y}n}{a} [/mm] < k < [mm] \frac{\tilde{x}n}{b}$.
[/mm]
Und jetzt meine Frage an dich, damit du auch selber noch aktiv dabei bleibst: Warum sind wir jetzt fertig und haben alles gezeigt? 
Liebe Grüße
Stefan
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 18:48 So 24.04.2005 | | Autor: | Ursus |
Hallo Stefan!
Vielen Dank erstmals für deine Hilfe.
Ich hab das bei meinem Beweis anfangs so gemeint und zwar hätte ich für n:=1+ab gezeigt, und hätte dann ax+by=1 mit 2,3 oder 4,... multipliziert und somit wäre ich beim anschließenden addieren mit ab auf alle n> ab gekommen. Aber das habe ich leider beim Artikel vergessen, na egal deine Lösung ist sowieso viel eleganter!!
Dein Beweis ist fertig, da wir ein k [mm] \in \IN [/mm] gefunden haben, sodass die Gleichung ax+by=n mit x,y [mm] \in \IN [/mm] sind. Glaube ich halt?
Thx! LG URSUS
|
|
|
|
