Is the language $ L = \{0^n 1^m \mid n \text{ and } m \text{ are co-prime}\}$ context-free ?
I guess that it's not context free because it seems too complicated for a PDA to decided whether 2 numbers are co-prime or not.
I tried using the pumping lemma to no avail.
Any help would be gladly appreciated.
Edit:
Here is one of my failed attempts with the pumping lemma:
Let $N$ be a constant. Take a prime $p$ such that $p > N!$ and then take the word $z = 0^p 1^{p+N!} \in L$. Let $ z = uvwxy $ be a decomposition of $z$ satisfying the conditions in the pumping lemma.
If $ vx $ contains only zeros then $ |vx| = k $ is an integer between $1$ and $N$. Define $m$ as $m = N!/k$. For $i = m+1$ the word $ uv^iwx^iy = 0^{p+N!}1^{p+N!} \not\in L $
However, I've failed to find such an integer $i$ for the other decomposition cases.