The language $L=\{W\in\{0,1\}^{*} \mid W=0^{x}1^{y} \text{ where } x\geq0, y>0 \text{ are integers and } y\nmid x\}$ is not regular.
How would one prove this using Pumping Lemma?
I thought about it for quite a while but couldn't quite figure it out. Lots of number theory is necessary I'd imagine.
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 < 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 < v < 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$.
Suppose that $L$ is regular. Then so is the language $L' = \{0^x 1^y : x,y \ge 0 \wedge y \mid x\}$ obtained as the intersection between the complement of $L$ and $0^*1^*$.
Let $n$ be the pumping length of $L'$ and consider the word $w = 0^{n+1} 1^{n+1} \in L'$.
By the pumping lemma, there is some constant $c$ such that $1 \le c \le n$ and, for every non-negative integer $k$, $0^{n-c+1} 0^{kc} 1^{n+1} \in L'$. Pick $k = 0$ to obtain $0^{n-c+1} 1^n \in L'$, which is a contradiction since $(n+1) \not\mid (n-c+1)$.
