# NFA that accepts all numbers not divisible by 105

I have to create an NFA that accepts the following language L with no more than 15 states.

$$L = \{a^n \mid n \geq 1$$ and $$n \mod105 \neq 0 \}$$.

To me it seems that all multiples of 105 have the same properties:

• sum of digits is divisible by 3
• the last digit is 0 or 5

I would appreciate if someone could help me here.

• Múltiples of 15 have the properties you list. – Peter Taylor May 15 at 5:39

$$L$$ is the union of the following three languages.
• $$L_3=\{{a^n \mid n\ge1\text{ and }n \not=0 \mod 3}\}$$,
• $$L_5=\{{a^n \mid n\ge1\text{ and }n \not=0 \mod 5}\}$$,
• $$L_7=\{{a^n \mid n\ge1\text{ and }n \not=0 \mod 7}\}$$.
Exercise. (It may take some time to do this exercise.) Show that no NFA with less than 15 states accepts $$L$$ exactly.