Irregularity of $\{0^x1^y : y \nmid x\}$
Assume that $L$ is regular. Suppose that the pumping constant is $q$, and let $p$ be a prime larger than $q$. Consider the word $w = 0^{p+1}1^p \in L$. According to the pumping lemma, we can write $w = xyz$, where $|xy| \leq q$, $y \neq \epsilon$, and $xy^tz \in L$ for all $t \geq 0$. Let $y = 0^i$, where $1 \leq i \leq q &lt; p$. Then
$$
xy^{t+1}z = 0^{p+1+ti} 1^p.
$$
Since $i \in \{1,\ldots,p-1\}$ and $p$ is prime, we know that $i$ has an inverse modulo $p$, that is, a number $j \in \{1,\ldots,p-1\}$ such that $ij - 1$ is a multiple of $p$, say $ij = ap + 1$ (we prove this below). If we take $t = (p-1)j$ then
$$
p+1+ti = p+1+(p-1)ij = p+1+(p-1)(ap+1) = p(a(p-1)+2)
$$
is a multiple of $p$, and so $xy^{t+1}z \notin L$, contradicting the pumping lemma.
The existence of $j$ can be proven in many ways. Here is one. Consider the integers $i,2i,3i,\ldots,(p-1)i$. Suppose that you divide them by $p$, obtaining remainders $r_1,r_2,\ldots,r_{p-1}$. Since $p$ is prime and $i \in \{1,\ldots,p-1\}$, all these remainders are non-zero. Furthermore, they must be different: if $r_u = r_v$ for $1 \leq u &lt; v &lt; p-1$ then $vi-ui = (v-u)i$ would be a multiple of $p$, contradicting the primeness of $p$. Therefore one of the remainders $r_j$ must equal $1$.