Endliche Automaten, die binäre Zeichenfolgen akzeptieren, die durch n teilbar sind

Ich arbeite an einer Aufgabenstellung für eine Klasse und überlege mir, woran ich gerade arbeite. Gibt es eine Mindestanzahl von Zuständen, die ein endlicher Automat haben muss, um binäre Zeichenfolgen zu akzeptieren, die Zahlen darstellen, die durch eine ganze Zahl n teilbar sind? In einem früheren Problemsatz konnte ich einen DFA erstellen, der binäre Zeichenfolgen akzeptiert, die durch 3 mit 3 Zuständen teilbar sind. Ist dies ein Zufall, oder liegt dem allgemeinen Problem der Erkennung von durch n teilbaren Zeichenfolgen etwas zugrunde, das auf eine Mindestanzahl von Zuständen hindeutet?

Ich verspreche, dass dies keine Hausaufgabenfrage für mich beantworten wird! :)

$n$$R$

$n$$R$$n$$n$

Es gibt einen weiteren Artikel zum gleichen Thema: B. Alexeev, Minimal DFA zum Testen der Teilbarkeit, J. Comput. Syst. Sci. 69 (2004), 235–243.