Kapitel 5Fortgeschritten27 Min.
Kleinste positive Linearkombination
Kleinste Teiler, Reste und Bézout · Abschnitt 18 von 64
Strategie
Kleinste positive Linearkombination
Wähle nicht irgendeine kleine Zahl, sondern das Minimum einer unter Differenzen stabilen Kandidatenmenge. Division mit Rest erzeugt dann den verbotenen kleineren Kandidaten.
Achtung
Positivität und Ganzzahligkeit prüfen
Teilen oder Restbildung ist nur dann ein gültiger Extremalschritt, wenn der neue Kandidat weiterhin in der ursprünglich gewählten Menge liegt.