Die Balkenwaage - ein mechanisches Modell der Zerlegung in Primfaktoren

Die Zerlegung einer natürlichen Zahl in Teiler und Primteiler (Primfaktoren) ist ein seit der Antike bekanntes Problem. Bis heute ist kein schneller Algorithmus dafür öffentlich bekannt.
Dieses Problem, die Teiler einer natürlichen Zahl zu finden (egal ob prim oder nicht), läßt sich anhand einer Balkenwaage sehr schön veranschaulichen:





Obiges Bild zeigt eine 'ganzzahlige' Balkenwaage. Ihre Arme sind unterteilt durch Marken in ganzzahligen Abständen. Nur an diesen Marken können (1 oder mehr) Gewichte der Masse 1 hängen. Im Bild hängt an beiden Waagarmen an Marke 6 je ein Gewicht. Beide Arme sind deshalb im Gleichgewicht.

Es erhebt sich die Frage: kann man die Situation an einem Arm so verändern, daß die Waage trotzdem im Gleichgewicht bleibt? Dazu muß man folgendes Gesetz der Mechanik kennen:

Hebelwirkung = Hebelarm * Gewicht

Deshalb bleibt die Waage im Gleichgewicht, auch wenn wir an einem Arm statt der Situation "1 Gewicht an Position 6" die Situation "2 Gewichte an Position 3" oder "3 Gewichte an Position 2" oder "6 Gewichte an Position 1" herstellen.   Das veranschaulicht folgendes Bild:





Andere Möglichkeiten gibt es im obigen Beispiel nicht. Denn 6 hat nur die echten Teiler 2 und 3 (sowie die unechten Teiler 1 und 6). Hätten wir an einem Waagarm 1 Gewicht an Position 3, 5, 7 oder 11 aufgehängt, so wäre es auf unserer "ganzzahligen" Balkenwaage unmöglich, am anderen Arm mehrere Gewichte an anderer Position (außer Position 1) so aufzuhängen, daß die Waage trotzdem im Gleichgewicht bleibt. Denn 3, 5, 7, 11 sind Primzahlen, haben also keine echten Teiler.




Fazit: Das mathematische Problem, Teiler einer natürlichen Zahl N zu finden, ist analog zum mechanischen Problem, auf unserer "ganzzahligen" Balkenwaage an einem Arm 1 Gewicht an Position N aufzuhängen und am anderen Arm mehrere Gewichte an anderer Position, so daß die Waage im Gleichgewicht bleibt. Gibt es eine andere gleichwertige Situtation "X Gewichte an Position Y", so sind X und Y Teiler von N. Die Situation "N Gewichte an Position 1" repräsentiert die beiden unechten Teiler von N, nämlich 1 und N.

Mit derselben Methode kann man feststellen, ob die gefundenen Teiler prim sind (d.h. Primfaktoren von N): Gibt es zur Situation "1 Gewicht an Position X (bzw. Y)" am einen Waagarm keine andere gleichwertige Situation am anderen Waagarm (außer N Gewichte an Pos. 1), dann ist X (bzw. Y) prim.




Könnte man einen Kugelrechner (mechanische Rechenmaschine mit rollenden Kugeln) entwerfen, der obiges Problem mechanisch löst, wäre es leicht, diesen Mechanismus in einen mathematischen Algorithmus zu transformieren. Auch die Umkehrung wäre möglich, aber je nach Algorithmus vielleicht zu umständlich.

Zumindest für Laien ist es verwunderlich, daß zu diesem banal erscheinenden Problem bis heute kein einfacher schneller Lösungsalgorithmus bekannt ist. Fortlaufendes Probieren von Teilern (ggf. mit einigen kleinen Vereinfachungen) dauert sehr lange, und auch die anderen bekannten Algorithmen sind nicht schnell, aber oft kompliziert.

         Stand:  17. 1. 2017                            Autor:  Leonhard Heinzmann                                       Homepage