DFA, lower bound on number of states, language with primes and remainders
For a binary string $x$, let $N(x)$ be the value of the number when read LSB first. Then $N(xy) = N(x) + 2^{|x|} N(y)$.

Now consider any $P \subseteq \mathbb{Z}_p$. For any $x$, $N(xy) \bmod p \in P$ iff $N(x) + 2^{|x|} N(y) \bmod p \in P$. This condition depends only on $N(x) \bmod p$ and $2^{|x|} \bmod p$, i.e. on $N(x) \bmod p$ and $|x| \bmod \operatorname{ord}_p(2)$ (here $\operatorname{ord}_p(2)$ is the smallest exponent such that $2^o \equiv 1 \pmod{p}$).

As $x$ goes over all binary strings, $(N(x) \bmod{p}, |x| \bmod\operatorname{ord}_p(2))$ goes over all possible $p \cdot \operatorname{ord}_p(2)$ values. One way to see this is to take zero paddings of strings representing $0,\ldots,p-1$.

Let us now consider the particular $P$ stated in the question. Since $p \geq 5$, $2^2 \not\equiv 1 \pmod{p}$, and so to prove the claim, it suffices to show that the equivalence classes $\{(a,1),(a,2) : a \in \mathbb{Z}_p\}$ are all different.

Consider any two equivalence classes $(a_1,b_1),(a_2,b_2)$. If exactly one of $a_1,a_2$ is in $P$, then there is nothing to do. Suppose first that $a_1,a_2 \in \{1,\ldots,\frac{p-1}{2}\}$. If $b_1 = b_2$ then $a_1 \neq a_2$. Without loss of generality, $a_1 &lt; a_2$. Therefore we can find $n$ such that $a_1 + nb_1 = \frac{p-1}{2}$ while $a_2 + nb_2 \notin P$. If $b_1 = 1$ and $b_2 = 2$ then there is a range of $\frac{p-1}{2}$ consecutive values of $n$ such that $a_1 + nb_1$ goes over all of $1,\ldots,\frac{p-1}{2}$. For the same values of $n$, the expression $a_2 + nb_2$ goes over $\frac{p-1}{2}$ values in jumps of $2$; it is not hard to check that not all of them can belong to $P$.

We leave the case $a_1,a_2 \notin P$ to the reader.