# Prove the language $a^n b^m$ where $m$ is a multiple of $n$ is not regular

Consider the problem

Show $$L = \{ a^{n}b^{m}\mid m \text{ es múltiplo de } n \}$$ is not regular.

I attempted the following.

Assume $$L$$ is regular. Then there is a natural number $$p \geq 1$$ such that any $$w \in L$$ of length greater or equal to $$p$$ can be written as $$w = xyz$$ , with $$|xy| \leq p$$ and $$|y| \geq 1$$, and such that $$xy^{j}z$$ is in $$L$$ for all $$j \in \mathbb{N}$$.

In particular, consider $$w = a^{p}n^{pq}$$ with $$q \in \mathbb{Z}$$. Then $$w = xyz$$. Because $$|xy| \leq p$$, we have $$xy$$, and hence $$y$$ as well, consists only of a repetition of $$a$$s. Let $$k$$ the number of $$a$$s in $$y$$ and $$k'$$ the number of $$a$$s in $$x$$, so that $$k + k' = |xy|$$.

Here is where I have trouble. I am not finding a way to raise $$y$$ to a certain power $$j$$ and show that the resulting number of $$a$$s, which is $$k' +k(j-1)$$, does not divide $$pq$$. Any ideas on how to follow? If this was not the correct approach, what would be a solution?

• You can simply fix a value for $q$. Commented Aug 4, 2023 at 1:10
• $a^nb^n$ is a (well-known) non-regular example and $n$ is a multiple of $n$.
– user16034
Commented Aug 4, 2023 at 8:16