# Finite automaton for all words whose length $n$ satisfies $\operatorname{gcd}(n,504) \geq 6$

I have been working on the following homework question, and I just can't seem to make any progress:

Construct a finite automaton having fewer than 36 states that recognizes the language $$\{s \in a^* : \operatorname{gcd}(|s|, 504) \geq 6\}$$, where $$|s|$$ is the length of $$s$$.

So far I have been trying to figure out a regular pattern in $$504$$ and have broken it down to the prime factorization $$504 = 2^3 \cdot 3^2 \cdot 7$$, which means that all divisors must be multiples of 2, 3, or 7. However I don't know how to create the finite automaton (NFA or DFA). Any help is appreciated!

The number $$504$$ has $$4\cdot3\cdot2=24$$ divisors: $$1, 2, 3, 4, 6, 7, 8, 9, 12, 14, 18, 21, 24, 28, 36, 42, 56, 63, 72, 84, 126, 168, 252, 504$$ Out of these, $$20$$ are at least $$6$$: $$6, 7, 8, 9, 12, 14, 18, 21, 24, 28, 36, 42, 56, 63, 72, 84, 126, 168, 252, 504$$ For an integer $$n$$, $$\operatorname{gcd}(n,504) \geq 6$$ iff $$n$$ is a multiple of one of these numbers. To check this, we don't really need to go over all $$20$$ possibilities. For example, if $$n$$ is divisible by $$12$$ then it is also divisible by $$6$$, so we can remove $$12$$ from the list. The list narrows down to only $$4$$ options: $$6,7,8,9$$ That is, $$\operatorname{gcd}(n,504) \geq 6 \Leftrightarrow 6 \mid n \text{ or } 7 \mid n \text{ or } 8 \mid n \text{ or } 9 \mid n$$ You can check the condition on the right using an NFA with $$6+7+8+9 = 30$$ states (or $$31$$ states if you do not allow multiple initial states).
• Note that \gcd is already predefined in LaTeX (and MathJax); you don’t have to write it with \operatorname. – Emil Jeřábek Feb 27 at 9:00