Abrazolica

This is a short explanation and some examples of how to use a finite automaton to test if a number is divisible by another number. The corresponding regular expressions are also given. We will use binary numbers since it makes things simpler with only two possible transitions out of each state.

Assume the bits are scanned left to right the way they are normally written. This means the most significant bit (msb) is scanned first and the least significant bit (lsb) is scanned last. Let \(n\) be the value of the binary number at some point in the scanning process and let its remainder upon division by \(d\) be \(r\). This means \(n\) can be written as \(n=md+r\) for some integer \(m\). The remainder can have values \(r=\{0,1,\ldots,d-1\}\). These remainder values will correspond to the states of the automaton. If \(b\) is the value of the next scanned bit (lsb) then the new value of the binary number will be \(2n+b\) and the new remainder will be \((2r+b) \bmod d\). The automaton then transitions to the new remainder state. We start in the \(r=0\) state and if we end up there then the number is divisible by \(d\).

Automata for divisibility by 2, 3, 4, 5, 6, and 7 are shown below. The start state is always the one labeled 0 and this is also the only accepting state. Regular expressions for the automata are also given. Note that the regular expressions for divisibility by 2 and by 4 could be written in a slightly simpler form, but there's not much to be gained by doing so, and you lose the simple connection with and interpretation of the corresponding automaton. Note also that the automata for divisibility by 4 and 6 can be reduced by one state and both versions are shown.

Divisibility by 2

Regular expression:
(b+aa*b)*
a=1
b=0
grep syntax: (0|11*0)*

Divisibility by 3

Regular expression:
(b+a(ba*b)*a)*
a=1
b=0
grep syntax: (0|1(01*0)*1)*

Divisibility by 4

Regular expression:
(b+aA(aA)*b)*
A=b+aa*b
a=1
b=0
grep syntax: (0|(10|111*0)(10|111*0)*0)*

Divisibility by 4, Reduced

Regular expression:
(b+a(a+ba)*bb)*
a=1
b=0
grep syntax: (0|1(1|01)*00)*

Divisibility by 5

Regular expression:
(b+a((ab)*(b+aa)(ba*ba)*ba*bb)*(ab)*(b+aa)(ba*ba)*a)*
a=1
b=0
grep syntax: (0|1((10)*(0|11)(01*01)*01*00)*(10)*(0|11)(01*01)*1)*

Divisibility by 6

Regular expression:
(b+aB(aB)*b)*
B=a+bA(bA)*a
A=b+aa*b
a=1
b=0
grep syntax: (0|(11|1(00|011*0)(00|011*0)*1)(11|1(00|011*0)(00|011*0)*1)*0)*

Divisibility by 6, Reduced

Regular expression:
See if you can figure it out.

Divisibility by 7

Regular expression:
See if you can figure it out.