Problem mit ganzzahliger Linearkombination

29/02/2008 - 02:45 von Jan Bruns | Report spam
Für fix vorgebene, ganze Zahlen a,b,c soll bei irgendwelchen,
ganzen ra,rb gelten:

a teilt (c+ra*b)
oder b teilt (c+rb*a)

Die beiden Teilaussagen scheinen àquivalent zu sein, da:

a teilt (c+v*b)
<=> u*a -v*b = c

Nun scheint aber (für wieder nur einfach irgendwelche ganzen u,v) auch
noch folgende Umformung àquivalent zu sein:

u*a -v*b = c
<=> ggT(a,b) teilt c

Aber ich verstehe leider überhaupt nicht, warum. Ich bin auch nicht sicher,
ob das tatsàchlich eine Äquivalezumformung ist, jedenfalls scheint es grob
zu passen.

Gruss

Jan Bruns
 

Lesen sie die antworten

#1 Martin Vaeth
29/02/2008 - 14:10 | Warnen spam
Jan Bruns schrieb:

u*a -v*b = c
<=> ggT(a,b) teilt c



Ja, ist richtig.

Aber ich verstehe leider überhaupt nicht, warum.



Der Beweis steht in praktisch jedem Lehrbuch ueber Zahlentheorie.
Wenn Du ihn selber finden willst: Schau Dir die Menge
{ u*a - v*b : u,v\in\Z }
an: Was kannst Du ueber Vielfache und Differenzen von Elementen
aus dieser Menge sagen? Welche Gestalt hat sie also, und was ist
ihr kleinstes positives Element?

Ähnliche fragen