Prove this langage isn't regular using the pumping lemma
As you know, the Pumping Lemma for regular languages states that if $L$ is a regular language, then there is an integer $p$ such that is $s$ is any string in $L$ with length $|s|\ge p$ then we can write $s=xyz$ with


$|y|&gt;0$,
$|xy|\le p$, and
$xy^iz\in L$ for all $i\ge 0$.


If we let $s=a^nb^m$ for distinct primes $n,m\ge p$ then certainly $s\in L$ since $\gcd(n,m)=1$. Now we know that in this case $y=a^k$ with $0&lt;k\le p$ and so if we pump $y$ we'll have $xy^{i+1}z=a^{n+ik}b^m$. Now we'll try to get a contradiction by showing that there is some $i$ for which $\gcd(n+ik,m)\ne 1$. We can get this if we can find an $i$ such that $m$ divides $n+ik$, since then we'll have $\gcd(n+ik,m)=m$.

In other words, we want an $i$ such that $n+ik\equiv 0\pmod m$. In modular arithmetic land we'll then have the following chain of equivalences:

$$\begin{align}
n+ik &amp;\equiv 0\pmod m\\
ik &amp;\equiv -n\pmod m\\
i &amp;\equiv -n(k^{-1})\pmod m
\end{align}$$ 
The last step follows from the fact that when the modulus is prime, any nonzero value has a multiplicative inverse.

Here's an example: Suppose $p=6$, then we could pick $n=11,m=7$ and pump the string $a^{11}b^7\in L$. If it happened that $k=4$ then we could use $i=-11\cdot 2$, where the $2$ came from the fact that $4\cdot 2\equiv 1\pmod 7$. In other words, we'd have 

$$
i=-11\cdot 2\equiv -22\equiv -1\equiv 6\pmod 7
$$
and then the pumped string would be $a^{11+6\cdot 4}b^7=a^{35}b^7$ and this is clearly not in $L$, since $\gcd(35,7)=7\ne 1$
$$
$$