# Pumping Lemma for $L=\left\{0^i 1^{j} \mid \gcd(i,j) = 1\right\}$

Let $L=\left\{0^i 1^{j} \mid \gcd(i,j) = 1\right\}$ I want to prove that this is not a regular language, but I am having trouble finding a string I can pump resulting in the string not being in the language. Ideally, rather than a full solution, I'd like suggestions for a string that I could use in this proof. I've played with the idea of setting $j = 2$ and $i = 2n+1$, but I don't think that would work.

• Does the exercise explicitly ask you to do it using the Pumping Lemma? Because I personally think that it is almost always more convenient to use the characterization of regular languages using Myhill-Nerode equivalence classes (if you are familiar with those). – PhoemueX Nov 2 '15 at 17:36
• It explicitly asks for the pumping lemma. It is one of the "!!" challenge problems in $\textit{An Introduction to Automata Theory, Languages, and Computation}$ and we haven't talked about Myhill-Nerode equivalences classes there, nor have I worked with them before – tzamboiv Nov 3 '15 at 2:53

Let $p$ be a prime number greater than the pumping length, and try $0^{p-1}1^p$. Show that when you pump up, you get something of the form $0^{p-1+kr}1^p$ for some $r$ such that $1\le r<p$, and show that there is a $k\ge 1$ such that $kr-1$ is a multiple of $p$, i.e., such that $kr\equiv 1\pmod p$.
• Could you elaborate a little more on the last step, about how to show that $kr-1$ is a multiple of $p$? – tzamboiv Nov 2 '15 at 8:25