ggT, teilerfremd < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
Hi,
ich bin in einem Skript auf eine Aussage ohne Beweis gestoßen, die anscheinend ein grundlegendes Ergebnis der diskreten Mathematik ist. Mir ist allerdings nicht klar warum das so gilt:
Für [mm] x,y \in \IN [/mm] mit [mm] ggT(x,y)=1 [/mm] existiert ein [mm] t_0 \in \IN [/mm] so dass für jedes [mm] t \ge t_0 [/mm] zwei Zahlen [mm] a,b \in \IN [/mm] existieren, so dass [mm] t = ax+by [/mm].
Weiß jemand wieso das das gilt?
Danke und Gruß
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 18:08 Fr 20.03.2009 | | Autor: | abakus |
> Hi,
>
> ich bin in einem Skript auf eine Aussage ohne Beweis
> gestoßen, die anscheinend ein grundlegendes Ergebnis der
> diskreten Mathematik ist. Mir ist allerdings nicht klar
> warum das so gilt:
>
> Für [mm]x,y \in \IN [/mm] mit [mm]ggT(x,y)=1[/mm] existiert ein [mm]t_0 \in \IN [/mm]
> so dass für jedes [mm]t \ge t_0[/mm] zwei Zahlen [mm]a,b \in \IN [/mm]
> existieren, so dass [mm]t = ax+by [/mm].
>
> Weiß jemand wieso das das gilt?
Ja.
Gruß Abakus
Spaß beiseite. Ohne die Einschränkung "natürliche Zahlen" kann man das [mm]t \ge t_0[/mm] weglassen, denn für teilerfremde ganze Zahlen x, y ist jede Zahl t darstellbar.
Nimm dir mal als Beispiel x=3, y=5.
Die Zahlen
1*3+1*5=8
1*3+2*5=13 und
1*3+3*5=18 lassen bei Teilung durch 3 die Reste 2, 1 bzw. 0.
Wenn ich jetzt zu 1*3+1*5=8 ein beliebige ganzzahlige Vielfache von 3 addiere, erhalte ich ALLE ganzen Zahlen der Form 3k+2.
Wenn ich zu 1*3+2*5=3 ein beliebige ganzzahlige Vielfache von 3 addiere, erhalte ich ALLE ganzen Zahlen der Form 3k+1.
Wenn ich zu 1*3+5*5=18 ein beliebige ganzzahlige Vielfache von 3 addiere, erhalte ich ALLE ganzen Zahlen der Form 3k.
So kann ich alle ganzen Zahlen in der Form a*3 + b*5 darstellen.
Wenn nun negative Summanden nicht zugelassen sind, gibt es am Anfang ein paar Lücken.
Möglich sind (falls die 1 als kleinste natürliche Zahl gilt)
3, 8, 13, 18, 23,...
5, 10, 15, 20,...
3+3=6, 11, 16, 21,
3+3+3=9, 14, 19, ...
Mit den Zahlen 8, 9 und 10 hat man erstmals 3 aufeinanderfolgende Zahlen, dann kann man durch Addition von 3 auch alle weiteren nat. Zahlen erzeugen. Ab [mm] t_0=8 [/mm] wären also in diesem Beispiel alle nat. Zahlen als Summe von Vielfachen von 3 und 5 darstellbar.
Gruß Abakus
>
> Danke und Gruß
>
>
>
> Ich habe diese Frage in keinem Forum auf anderen
> Internetseiten gestellt.
>
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 18:18 Fr 20.03.2009 | | Autor: | DyingSoul |
Ok, ist einleuchtend, danke dir!!
Gruß
|
|
|
|
