Aufgabenstellung

Problem:

Für das exakte Rechnen mit rationalen Zahlen ist das Kürzen sehr wichtig, um ein unnötiges Anwachsen der Zahlen zu vermeiden. Dazu braucht man einen Algorithmus der für gegebene positive ganze Zahlen und den größten gemeinsamen Teiler und gleichzeitig Faktoren und berechnet, für die und jeweils das kleinste gemeinsame Vielfache der Zahlen und ergibt.

Algorithmus:

Durch Modifikation eines Algorithmus zum Berechnen des ggT ist ein Algorithmus zum gleichzeitigen Berechnen der Faktoren und zu konstruieren. Dazu sind nach Möglichkeit die arithmetischen Operationen für beliebig lange ganze Zahlen zu benutzen.

Aufgaben:

Schreiben Sie ein Programm zur Lösung dieses Problems. Der Algorithmus soll in einem Unterprogramm realisiert werden. Kommentieren Sie das Programm. Erläutern Sie, warum es korrekt ist.