Prove that language L = {a^p ; p is prime} isn't regular using Myhill-Nerode theorem.

Let's show that, given two primes $p, q$, we have $a^p \not \sim_L a^q$, that is, they lie in two different equivalence classes.

Assume by contradiction that $a^p \sim_L a^q$, and wlog $q > p$. Since $a^p a^{q-p} = a^q \in L$, then $a^q a^{q-p} = a^{2q-p} \in L$ as well, otherwise $a^{q-p}$ would be a distinguishing relation for $a^p$ and $a^q$. Iterating the argument, since $a^p a^{2q-2p} = a^{2q-p} \in L$, then $a^q a^{2q-2p} = a^{3q-2p} \in L$, and by induction $a^{p+i(q-p)} \in L$ for every $i$.

But for $i=p$ we have that $p + p(q-p)$ is a multiple of $p$, so it cannot be a prime, a contradiction.