# prove that given language is not regular.

So i need to prove that the language $$L=$${$${a^ib^j: gcd(i,j)=1}$$} is not regular.

For which i chose the string $$w=a^{m!}b^p$$ where $$p>m!$$ and is a prime number. clearly $$m!$$ and p are co-prime so $$w$$ is in $$L$$.
Let $$w=xyz$$ such that $$|xy|<=m$$ and $$|y|>=1$$. now the only choice for $$y$$ in this string is $$a^k :k<=m$$.
Now pumping it $$i$$ times we get the string $$a^{m!+(i-1)k}b^p$$. Choosing $$i=1+\frac{(p-1)m!}{k}$$. now $$i$$ is a natural number as $$k<=m$$ so we get the string $$a^{m!p}b^p$$ which is not in $$L$$.
Hence pumping lemma is not satisfied so $$L$$ is not regular.
Is my reasoning correct? Thanks in advance.

• Seems fine for me :) – tarit goswami Sep 28 '18 at 18:07