# Proving that no 2-state DFA decides the language A = {x ∈ {0, 1}* | bnum(x) is divisible by 3}

I am doing a problem where I need to prove that no 2-state DFA decides the language A = {x ∈ {0, 1}*| bnum(x) is divisible by 3}.

It's seems pretty obvious at first, because aren't there only 4 DFA's with two states that define it? Also, since x is divisible by 3, the DFA would need to have 3 states to define the remainder values.

So I feel like I have a good understanding of the problem, but how do I more formally prove the statement? Any help is appreciated.

Remainder values is indeed the clue! Obviously the strings $$1$$ and $$10$$ cannot end in a final state as they represent number 1 and 2 respectively. But can they end in the same state?