Is the language $\{0^n 1^m \mid n \text{ and } m \text{ are co-prime}\}$ context-free?
Ridiculous that I didn't see this earlier...

The proof that the language (call it $\mathcal{L}$) isn't context free is by contradiction. Assume $\mathcal{L}$ is context free, by the pumping lemma for CFGs there is a constant $N$ such that each string $\sigma \in \mathcal{L}$ such that $\lvert \sigma \rvert \ge N$ it can be written $\sigma = u v x y z$ with $v y \ne \epsilon$ such that for all $k \ge 0$ the string $u v^k x y^k z \in \mathcal{L}$. Take $m, n$ different primes (such that $\gcd(m, n) = 1$) and $m, n &gt; 2N$, and take $\sigma = 0^m 1^n$. The pumped string will be $0^{m + k a} 1^{n + k b}$ for some constants $a$, $b$, not both zero, and such that $a &lt; m$ and $b &lt; n$ (we have $a, b \le N &lt; m / 2, n / 2$ by the way $m$, $n$ were selected). The case of one of them zero was covered by OP, so consider $a, b \ne 0$. Now:

$$
\begin{align*}
m + k a &amp;\equiv 0 \pmod{n} \\
n + k b &amp;\equiv 0 \pmod{m}
\end{align*}
$$

This has a unique solution $k^*$ modulo $m n$ by the chinese remainder theorem
(we have $a &lt; n$, and as $n$ is prime, $\gcd(a, n) = 1$; similarly $b$ and $m$),
and thus we can write:
$$
\begin{align*}
m + k^* a &amp;\equiv 0 \pmod{mn} \\
n + k^* b &amp;\equiv 0 \pmod{mn}
\end{align*}
$$
i.e., $m n \mid \gcd(m + k^* a, n + k^* b)$. Contradiction.