I need to prove that the language of $0^n1^m$ is irregular if $n$ and $m$ are coprime. (Or to disprove that)
My attempt at this was to use the pumping lemma, and I've gotten $0^{n+(k-1)i}1^m$ after pumping, where $0<i\leq n$. If I'm correct, I only need to prove that $$\forall n,m : gcd(n,m)=1 \ \ \forall i\in\mathbb Z: 0<i\leq n \ \ \exists k\in\mathbb Z : gcd(n+(k-1)i, m)\not=1$$ However, I do not follow how this can be proved.
Corrected.
Let $p$ be a prime greater than the pumping length, and start with the word $w=0^{p-1}1^p$. Then $w=xyz$, where $|xy|\le p-1$, $|y|\ge 1$, and $xy^kz$ is in the language for all $k\ge 0$. Clearly $x=0^a$ and $y=0^b$ for some $a\ge 0$ and $b\ge 1$, so that $xy^kz=0^{a+kb+p-1-a-b}1^p=0^{p-1+(k-1)b}1^p$. Now $1\le b<p$, and $p$ is prime, so $\{1,2,\ldots,p-1\}$ is a group under multiplication. If $\ell$ is the multiplicative inverse of $b$ in this group, let $k=\ell+1$; then $(k-1)b\equiv 1\pmod p$, so $p-1+(k-1)b\equiv 0\pmod p$, and $xy^kz$ is not in the language.
Alternatively, one can avoid the group theory by appealing to Bézout’s identity, which yields integers $m$ and $n$ such that $mb+np=1$. Then
$$(m+\ell p)b+(n-\ell b)p=-1$$
for each $\ell\in\Bbb Z$, so we can assume that $m\ge 0$ and take $k=m+1$. Then
$$xy^kz=0^{p-1+mb}1^p=0^{p-1+1-np}1^p=0^{(1-n)p}1^p\;,$$
which is not in the language. (Note that necessarily $n<0$, so that $1-n>0$.)