 |
|||
| HSG |
|
Lemma von Bachet (DIFF,CM1,S.30)
Für je zwei natürliche Zahlen a und b gibt es ganze Zahlen x und y mit ggT(a,b)=x*a+y*b.
Verbesserte Version des Algorithmus
Die Pfeile geben die Arbeitsrichtung an, dh. bei x und y fängt man unten mit 1 0 an. Die schrägen Pfeile lassen sich leider nicht so leicht darstellen. Wo gehören sie hin?
x' = y y' = x - q * y
Bedenken, dass x und y aus der Zeile tiefer, q aber aus der aktuellen Zeile stammt.
a = q * b + r x y
-----------------------------------------
1001 = 4 * 203 + 189 | 14 -69 ^
203 = 1 * 189 + 14 | -13 14 |
189 = 13 * 14 + 7 | 1 -13 |
14 = 2 * 7 + 0 | 0 1 |
7 0 v 1 0 |
(älteres) Beispiel
| xi | yi | |||||||||||||||||||||||
| 0 | 1 | |||||||||||||||||||||||
| 1001 | = | 4 | * | 203 | + | 189 | 1 | -4 | 189=1*1001-4*203 | |||||||||||||||
| 203 | = | 1 | * | 189 | + | 14 | 0 | - | 1 | * | 1 | = | -1 | 1 | - | 1 | * | -4 | = | 5 | 14=-1*1001+5*203 | |||
| 189 | = | 13 | * | 14 | + | 7 | 1 | - | 13 | * | (-1) | = | 14 | -4 | - | 13 | * | 5 | = | -69 | 7=14*1001-69*203 | |||
| 14 | = | 2 | * | 7 | + | 0 |
Der Algorithmus erweitert den gewöhnlichen Algorithmus von Euklid um die Berechnung der Koeffizienten xi und yi zur Darstellung des jeweiligen Restes.
Dabei gelten die rekursiven Gleichungen xi = xi-2-qi*xi-1 und yi = yi-2-qi*yi-1.
Die xi-1 bzw. xi-2 (yi-1 bzw. yi-2) findet man dabei in der gleichen Spalte 1 oder 2 Zeilen darüber, qi ist der ganzzahlige Quotient in der gleichen Zeile im Euklid-Schema. Wenn man will, so kann man - wie oben in der letzten Spalte geschehen - die Darstellung der Reste fortlaufend kontrollieren.
weiteres Beispiel
| 0 | 1 | |||||||||||||||||||||||
| 1970 | = | 1 | * | 1066 | + | 904 | 1 | -1 | 904=1*1970-1*1066 | |||||||||||||||
| 1066 | = | 1 | * | 904 | + | 162 | 0 | - | 1 | * | 1 | = | -1 | 1 | - | 1 | * | (-1) | = | 2 | 162=-1*1970+2*1066 | |||
| 904 | = | 5 | * | 162 | + | 94 | 1 | - | 5 | * | (-1) | = | 6 | -1 | - | 5 | * | 2 | = | -11 | 94=6*1970-11*1066 | |||
| 162 | = | 1 | * | 94 | + | 68 | -1 | - | 1 | * | 6 | = | -7 | 2 | - | 1 | * | (-11) | = | 13 | 68=-7*1970+13*1066 | |||
| 94 | = | 1 | * | 68 | + | 26 | 6 | - | 1 | * | (-7) | = | 13 | -11 | - | 1 | * | 13 | = | -24 | 26=13*1970-24*1066 | |||
| 68 | = | 2 | * | 26 | + | 16 | -7 | - | 2 | * | 13 | = | -33 | 13 | - | 2 | * | (-24) | = | 61 | 16=-33*1970+61*1066 | |||
| 26 | = | 1 | * | 16 | + | 10 | 13 | - | 1 | * | (-33) | = | 46 | -24 | - | 1 | * | 61 | = | -85 | 10=46*1970-85*1066 | |||
| 16 | = | 1 | * | 10 | + | 6 | -33 | - | 1 | * | 46 | = | -79 | 61 | - | 1 | * | (-85) | = | 146 | 6=-79*1970+146*1066 | |||
| 10 | = | 1 | * | 6 | + | 4 | 46 | - | 1 | * | (-79) | = | 125 | -85 | - | 1 | * | 146 | = | -231 | 4=125*1970-231*1066 | |||
| 6 | = | 1 | * | 4 | + | 2 | -79 | - | 1 | * | 125 | = | -204 | 146 | - | 1 | * | (-231) | = | 377 | 2=-204*1970+377*1066 | |||
| 4 | = | 2 | * | 2 | + | 0 |
Delphi-Programm
// DIFF CM1 Algorithmen der elementaren Zahlentheorie, S.32
procedure Bachet(a,b : integer; var g,x,y : integer);
var
bg,bu,cg,cu,xg,xu,yg,yu : integer;
begin
bg := a; cg := 0; xg := 1; yg := 0;
bu := b; cu := a div b; xu := 0; yu := 1;
while (bg <> 0) and (bu <> 0) do
begin
xg := xg-cu*xu; yg := yg-cu*yu; bg := bg mod bu;
if bg = 0
then
begin
g := bu; x := xu; y := yu;
end
else
begin
cg := bu div bg; xu := xu-cg*xg;
yu := yu-cg*yg; bu := bu mod bg;
end;
if bu = 0
then
begin
g := bg; x := xg; y := yg;
end
else
cu := bg div bu;
end;
end;