Prove that language $L=\{a^ib^j:\gcd(i,j)=1\}$ is irregular

Question

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 ?

Answer 1

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?

Answer 2

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.