how to prove that the following is not a regular language? the language we want to disprove is :
$$ L = \{ 0^i1^j| gcd(i,j)=1 \} $$
my attempt :
i used the pumping lemma this way:
consider the set of strings of the form $0^p1^q$ such that $n <=p$ and $p\in primes$ and $q\in primes$
note $n$ is the number that lemma states it exists .
now using pumping lemma we get :
$xy = 0^m$  where $m<= p$
$ y = 0^k $  so $x= 0^{m-k}$  so $z = 0^{p-m}1^q$
now lemma says all string of the form $xy^iz\in language$
now the sum of all $0$'s for all theses strings is : $p+(i-1)k$
now we choose from our set the string which has $q = k+1$
and we set $i = p+1$
now we have $gcd(p(k+1),k+1) = k+1$
so we have disproved the statement.
is the proof right ? is choosing a set of counter examples and then choosing one among them correct?
 A: For the record, there is a very simple proof using the Myhill–Nerode criterion. Let $p_i$ be an enumeration of all primes. Since $0^{p_i} 1^{p_i} \notin L$ while $0^{p_j} 1^{p_i} \in L$ (for $j \neq i$), we see that the words $0^{p_i}$ are pairwise inequivalent with respect to $L$, and so $L$ is not regular.
If you really need to use the pumping lemma, let $n$ be the pumping length, and pick a prime $p \geq n+2$. Consider the word $0^p 1^{(p-1)!} \in L$. The pumping lemma states that you can write $0^p 1^{(p-1)!} = xyz$, with $|xy| \leq n$ and $|y| \geq 1$, such that $xy^i z \in L$ for all $i \geq 0$. In our case, we must have $y = 0^k$, where $1 \leq k \leq n \leq p-2$, and so $xz = 0^{p-k} 1^{(p-1)!}$. Since $k \leq p-2$, we have $2 \leq p-k \leq p-1$, and so $\mathrm{gcd}(p-k,(p-1)!) = p-k > 1$, implying $xz \notin L$. This contradiction shows that $L$ is not regular.
A: The decomposition into $xyz$ is dependent on what input string $0^p1^q$ you choose, therefore, $k$ is a function of $p$ and $q$, so you cannot just set $q = k+1$ afterwards.
I would choose $0^p1^{(p-1)!}$ for some $p$ prime at least two greater than the pumping length, since then $xy^0z = xz = 0^k1^{(p-1)!}$ for $k<p$.  This is possibly not the most slick proof. 
