Teilbarkeitstests mit endlichen Automaten

Dreierrest und Quersumme

Der bekannte Quersummentest für die Teilbarkeit durch 3 besagt, dass die Quersumme einer Zahl den gleichen Rest bei Teilung durch drei hat wie die Zahl selbst. Es reicht daher, die Quersumme zu berechnen, und davon den Rest zu bestimmen. Doch auch dies ist eigentlich zu viel Arbeit, man könnte ja nach jeder Addition bereits wieder den Rest bestimmen. Oder noch besser: man führt bereits die Addition in der Menge der Dreierreste durch. Dies kann man sehr leicht graphisch machen: auf einem Kreis mit den Resten 0, 1 und 2 bei Teilung durch 3 zählt man bei 0 beginnend die Ziffern der Zahl ab. Am Ende der Zahl landet man mit der Abzählung auf dem Rest der Zahl.

Dieser Prozess kann auch mit einem endlichen Automaten beschrieben werden: seine Zustände sind die Reste modulo 3, die Übergänge sind durch die Addition einer Ziffer in den Restklassen modulo 3 gegeben.


 

Reste und endliche Automaten

Will man diese Idee auf beliebige Reste verallgemeinern, muss man auch die Position der Ziffer berücksichtigen. Wieder konstruiert man einen endlichen Automaten, der als Zustände die Reste hat. Die Ziffern, die der Reihe nach von links nach rechts gelesen werden, können jetzt wieder durch modulare Addition hinzugefügt werden. Das hinzufügen einer neuen Ziffer bedeutet aber auch, dass der bisherige Rest mit 10 multipliziert werden muss. Bei den Dreierresten ist dies besonders einfach, weil 10 den Dreierrest 1 hat. Bei komplizierteren Resten ist dazu ein zusätzlicher Schritt nötig.

 

Im nebenstehend abgebildeten Diagramm wird der Rest der Zahl 43 bei Teilung durch sieben ermittelt. Die Addition der Ziffernwerte erfolgt durch Abzählen. Die Multiplikation mit der Basis (das "Springen") wird durch die ausgezogenen Pfeile im Inneren des Diagrams implementiert. Damit ist natürlich ein Zustandsdiagramm für einen endlichen Automaten definiert.

Offenbar kann man für jede Zahlsystembasis und für jeden Teiler einen endlichen Automaten definieren. Bekannte Teilbarkeitsregeln lassen sich aus den Zustandsdiagrammen direkt ablesen, wie in der Arbeit Automatische Teilbarkeitstests gezeigt wird. Weitere Zustandsdiagramme kann man hier finden: all.pdf