Let $L$ be the language $\{a^ib^j\mid \text{$i,j$ relatively
        prime}\}$.  According to Myhill-Nerode it can be proved that $L$ is
        not regular by demonstrating that $L$ has infinite index. This
        means that we have to find an infinite number of strings $x_i$ such
        that for $i\neq j$: $x_i \not\sim_L x_j$, or, equivalently,
        $x_iu\in L \Leftrightarrow x_ju\not\in L$, for some string $u$.

        Suppose $x_iu \in L$, then $x_iu = a^pb^q$, with $p,q$ relatively
        prime.  If we take $x_i=a^p$ and $u=b^q$, it suffices to find an
        $x_j=a^r$ such that $q$ and $r$ are \emph{not} relatively prime. A
        solution is $r=q$. So for all relative primes $p,q$: $a^pb^q \in L
        \Leftrightarrow a^qb^q \not\in L$, meaning that $a^p \not\sim_L
        a^q$. There are infinitely many pairwise relative primes (in
        particular, all primes are pairwise relatively prime) and therefore
        $L$ has infinite index.