Proof of irregularity of a language, L = {0^n : n is prime}

Question

So the above statement is a question from a course on Theory of Computation. I have already proven it using the pumping lemma, but am looking for proofs using the Myhill-Nerode theorem, or more specifically, it's corollary, which states that a language, $L$, has a finite number of equivalence classes under the relation $\cong_L$ (indistinguishability under L), if and only if it is regular.

My idea for this was to take two strings, say $x$ and $y$, and concatenate a string, $w$ to both of these. Then, if the two strings are, indeed indistinguishable under $L$, then $|x| + |w|$ and $|y| + |w|$ should either be simultaneously prime, or simultaneously composite for all choices of $w$ (i.e. if $|x| + |w| \text{ is prime } \Leftrightarrow |y| + |w| \text{ is prime }$ . My goal here is to prove that if this is true, then $|x| = |y|$, and as no two strings in the language have the same length, $x = y$. I think the key here is that both $|x|$ and $|y|$ are prime.

I am currently stuck proving simultaneous prime/composite nature of the above two values, and need some help. Maybe a number theoretic solution could apply here?

Answer 1

Given two prime numbers $p\leq q$, assume the two sets $$ M = \{m\mid m + p\text{ is prime}\}\\ N = \{n\mid n + q\text{ is prime}\} $$ are equal. In particular, because $q = p + (q-p)$ is prime, $q-p\in M$. So $q-p\in N$, impying that $q + (q-p) = 2q-p$ is prime. But $2q-p = p + 2(q-p)$ so $2(q-p)\in M$, which means $2(q-p)\in N$.

Continuing this argument ad infinitum, we see that $k(q-p)\in M, N$ for any natural number $k$. But $k = p$ yields $p + p(q-p) = p(1 + q - p)$ prime. And this cannot happen unless $1+q-p = 1$, which is to say $p = q$.

Answer 2

Your idea is correct, but the assumption "$|x|$ and $|y|$ are prime" is not required.

Let $P$ be the set of primes. For each natural number $k$, let $$ P - k = \{x \in \Bbb N \mid x + k \in P\} $$ Observe that for all $i, j \in \Bbb N$, one has $(P -i) - j = P -(i +j)$.

Suppose that $P -n = P - m$ for some $n < m$. Let $p$ be a prime such that $m \leqslant p$. Since $m = n + (m-n)$, one gets $P - n = P - m =(P - n) - (m-n)$ and by iteration $(P - n) = (P - n) - k(m-n)$ for all $k$. In particular, as $p!$ is a multiple of $m-n$ since $m-n \leqslant m \leqslant p$, one gets $$(P - n) = (P - n) - p!$$ Now $p-n \in P-n$, and thus $p-n \in (P - n) - p!$, whence $p + p! \in P$, a contradiction since $p + p!$ is not prime. Thus the sets $P-n$ are pairwise distinct.