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 ?

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?
