Pumping lemma: the set of strings of 0s and 1s such that when interpreted as an integer, that integer is prime In the section of my textbook covering the pumping lemma, there are practice questions asking us to prove a given language is not regular. 

I have not been able to solve this one: 


  The set of strings of 0s and 1s, beginning with a 1, and interpreted
  as an integer, that integer is prime.


My attempt:

Assume to the contrary that the language is regular. Let $p$ be the pumping length given by the pumping lemma. Let $s = 101$. The pumping lemma guarantees s can be broken into 3 substrings, x, y, z such that $|xy| \leq p$ and $y \neq \epsilon$....

Obviously this is where it breaks down, because I haven't given a string that is of at least length $p$ (ie $s = 10^p1$).
I believe what you are missing is Fermat's Little Theorem: If $p$ is a prime and $p$ does not divide $a$, then $a^{p-1}\equiv 1 \mod p$. 

I'll give an example application in base 10. Let's assume that 2039 is the prime to which the pumping lemma is applied and the decomposition is 2 03 9. That is the pumping lemma would imply that all strings of the form $2(03)^n9$ denote prime numbers. At least it is true for $n\in\{0,1,2\}$. But without further calculation I know that it fails for $n=28$: The number $N=2030303030303030303030303030303030303030303030303030303039$ is divisible by $29$, which is the number at $n=0$. To see this, observe that 
$N = 20\cdot 100^{28} + \sum\limits_{0\leq i&lt; 28}30\cdot 100^i + 9
= 20\cdot 100^{28} + 30\cdot\frac{100^{28}-1}{100-1} + 9$ and apply Fermat's theorem. 
Here, we also use that $29$ does not divide $100-1$. 

I hope from this you are able to solve the exercise.