The set of decimal representations of numbers divisible by 17 is regular

Proposition. Let L=L₁₇ be the set of decimal representations of numbers divisible by 17 (the alphabet is {0,1,...,9}). Then L is a regular language.

Proof. We construct a FSA (with 17 states) recognising L. For simplicity of construction, we shall also recognise numbers with leading zeroes (and the empty string) as being divisible by 17; fixing this is left as an exercise for the reader. Our states shall be {r₀, ..., r₁₆}; after reading a word w, we shall be in state r_j, where j = w modulo 17. Clearly, for this to work, the initial state and the sole accepting state must be r₀.

Consider a word w with j = w modulo 17. If a is one of the digits {0, 1, ..., 9}, then the string wa will represent the number 10*w+a; dividing by 17, we see that the remainder is (10*w+a) modulo 17 = (10*j+a) modulo 17. We can compute this once and for all (for instance, when w is divisible by 17 with remainder 3, tacking on a 1 at the end brings us to remainder 3*10+1 modulo 17 = 14; you might need to look at 20=17+3 and 201=17*11+14 to be convinced). In other words, for every 0≤j<17 and 0≤a<10, we need a transition from r_j to r__{10*j+a mod 17}.

It is now easy to see that the resulting automaton, with 17 states and 170 transitions, recognises L. It is interesting to note the close parallel to the Myhill / Nerode Theorem; a simple modification of the above argument yields that 17 states are required in any automaton recognising L.