Prove that language $L=\{a^ib^j:\gcd(i,j)=1\}$ is irregular Prove that language $L=\{a^ib^j:\gcd(i,j)=1\}$ is irregular.
I have tried for a long time, but I haven't managed to solved it. Someone help me ?
 A: This is easy to solve using the Myhill–Nerode criterion. let $p_1,p_2,\ldots$ be an infinite set of primes, and consider the words $w_i = a^{p_i}$. I claim that they are pairwise inequivalent with respect to $L$. Indeed, if $i \neq j$ then $a^{p_i} b^{p_i} \notin L$ while $a^{p_j} b^{p_i} \in L$, and so $w_i,w_j$ are inequivalent. Since we found infinitely many pairwise inequivalent words, we can conclude that the language is irregular.

You can also use the pumping lemma, though the only reason to do so is the unfortunate ideé fixe encountered in automata theory courses in North America. Pick some prime $p$ larger than the pumping length, and consider the word $a^{p-1} b^p \in L$. According to the pumping lemma there is some $1 \leq k \leq p-1$ such that $a^{p-1 + kn} b^p \in L$ for all $n \geq -1$. Since $p$ is prime, $(k,p) = 1$ and so there exist integers $s,t$ such that $sk + tp = 1$. Choose $r$ so that $s+rp \geq 0$, and take $n = s+rp$. According to the pumping lemma, the word $a^{p-1 + k(s+rp)} b^p$ should be in $L$. But
$$ p-1 + k(s+rp) \equiv -1 + 1 + 0 \equiv 0 \pmod{p}, $$
so that $(p-1+k(s+rp),p) = p$, and we reach a contradiction.
Having seen the pumping lemma proof, don't you agree that the Myhill–Nerode criterion is easier to use? Why the dogmatic stress on the pumping lemma?
A: There is a simpler way.  The complementary language intersected with $a^*b^*$ is $\{a^nb^m| gcd(n,m) > 1\}$.  Now one can use the pumping lemma: if $p$ is the pumping length choose a prime $q > p$ and select the string $a^qb^q$.  The pumped string has to consist of $a$'s and has to have length $k >0$.  Now if we pump down we get the string $a^{q-k}b^q$ and clearly $gcd(q-k,q) = 1$ so this language is not regular and neither is the original.
A: Use the pumping lemma,let $p$ be a prime number and $p>n_0+2$,consider this string $s=0^p1^{(p-1)!}\in L$, for any decomposition $s=xyz$ with $0<|y|\leq n_0$, $xz=0^{p-|y|}1^{(p-1)!}\notin L$,so $L$ is irregular.
