DFA, lower bound on number of states, language with primes and remainders

Question

This is an exercise from old exam on formal languages that I don't know how to solve:

Let $p \ge 5$ be a prime number and $L_p$ be a language of words over $\{0,1\}$ that read in binary from right (i.e. from least significant bit) give a number that gives remainder modulo $p$ from the set $\{1,2, \ldots, \frac{p-1}{2}\}$.

How to show that:

Every DFA recognizing $L_p$ has at least $2p$ states.

?

One fact that I know of and is somehow related (has DFA and primes in the statement) is:

Any DFA recognizing language $\{0^n : n \text{ is not divisible by } p\}$ has at least $p$ states.

This can be seen by observing that the language is infinite, hence any DFA must have a reachable cycle, from which some accepting state is reachable. And if that cycle had less than $p$ states, then because any number smaller than $p$ is coprime with $p$, we could loop sufficiently many times in that cycle and arrive at the aforementioned accepted state with a word $0^{kp}$ for some natural $k$ - a contradiction.

Maybe it's possible to use this fact, or alter this proof somehow to make it fit for the theorem with $L_p$?

--EDIT

I'm trying to solve it by Myhill-Nerode theorem, as Yuval Filmus suggested.
So, the goal is to find $2p$ words $w_1, \ldots, w_{2p}$ that will be pairwise distinguishable. I don't have a good intuition here but let's define $w_i$ to be $rev(bin(i))$ for $i = 1, \ldots, 2p$ ($bin(a)$ gives a binary representation of number $a$, and $rev(w)$ reverses the word $w$). Let's take any $i \neq j$ that both belong to $L_p$, or both don't. Now the task becomes a bit number-theoretic -- adding a common suffix $x$ to these words changes their values such that $val(w_ix) = val(w_i) + 2^{length(w_i)-1}val(x)$ (and similarly for $j$), where $val(\cdot)$ gives value of binary string reading from LSB (so e.g. $val(01) = 2$).
Now the question is: can we always find an appropriate $x$ that makes one of $w_ix, w_jx$ belong to $L_p$, and the other not? I don't know the answer to this question. Maybe I should use the fact, that $2$ is a multiplicative generator modulo $p$?

Answer 1

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 < 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.