Regularity of a language constructed from a know regular language
As you mention, if $n$ was fixed, then this is not too difficult to prove.
So, the idea would be to show that in fact, $n$ can be bounded a-priori, depending only on $A$, and not on $x$.
To this end, consider some word $x\in \Sigma^*$, and suppose $x^m\in A$ for some $m$.
Let $k$ be the number of states in some DFA $D$ for $A$ (e.g., minimal DFA). Suppose $m&gt;k$, then there exist $0\le i&lt;j\le m$ such that the run of $D$ on $x^i$ reaches the same state as on $x^j$. But this implies that $x^{m-{j-i}}$ is also accepted by $D$.
Thus, it's enough to consider $n\le k$. So you can rewrite your language as
$$\{x| \exists n\le k,\ x^n\in A\}$$
And this is regular.