# Irregularity of $\{b^ma^n: (m,n)=1\}$ using Nerode [closed]

Let $$L=\{b^ma^n \mid \text{m and n are coprime} \}$$. Using Nerode's theorem, prove that $$L$$ is irregular.

From Nerode's theorem I know that $$L$$ is regular if and only if the number of equivalence classes of $$R_L$$ (the relation defined in Nerode's theorem) is finite, so I need to prove that there are infinitely many equivalence classes.

The first thing that came to mind from $$L$$'s definition is using Dirichlet's theorem, hence I tried:

Let $$w_{m, i}=b^ma^i$$, ($$m,i$$ are coprime), and I prove that for $$j\ne i$$, ($$m, j$$ coprime), $$w_{m, i} \not R_L w_{m, j}$$ Let $$z=a^{m+ni}$$, ($$n$$ an integer promised by Dirichlet's theorem such that $$m+ni$$ and $$m$$ are coprimes), so $$w_{m, i}z = b^ma^{m+ni+i}= b^ma^{m+(n+1)i}\in L$$ and $$w_{m, j}z = b^ma^{m+ni+j}\not\in L$$ But this isn't necessarily true as $$m$$ and $$m+(n+1)i$$ might not be coprime and $$m$$ and $$m+ni+j$$ might be.

I know from previous exercises that I need to find $$w_i$$ and show that for a word $$z$$ $$w_iz\in L\text{ and }w_jz\not\in L \space\space (i\ne j)$$ and therefore there are infinitely many equivalence classed, but I find coprimality difficult to handle.

• – D.W.
May 10, 2022 at 4:16
• I’m voting to close this question because it was cross-posted.
– D.W.
May 10, 2022 at 4:16

Let $$P$$ be the set of all primes. Show that the words $$\{b^p : p \in P\}$$ belong to different equivalence classes.