Prove that $L_1$ = $\{1^m :$ m is not a perfect square$\}$ is not regular using Pumping Lemma I'm trying to prove that the Language $L_1$ = $\{1^m :$ m is not a perfect square$\}$ is not regular. I proved before that L = $\{1^m :$ m is a perfect square$\}$ is not regular, I thought that I could proof $L_1$ in a similar way but I'm stuck right now, I tried several estimations but nothing seems to work.
What I got so far:
Assume L is regular, that is there exists an $n \in \mathbb{N}$ such that every $x \in L$ with $|x| \geq n$ can be decomposed such that the three conditions of the Pumping Lemma hold. Let x = $1^{n^2 +1}$ then clearly $|x| \geq n$, now $uv^0w$ should also be an element of the language but $uw = 1^{n^2 +1-|v|}$...
So how can I argue now that uw is a square?
A little hint would be awesome
Thanks
 A: An important property of regular languages is that the latter are closed under complementation.
In other words, the complement of a regular language is also regular.
As you have already proved that $\overline{L_1}$ (the complement of $L_1$) is not regular, you can base your argument on that to prove $L_1$ is not regular according to closure properties. 
A: Using the fact that regular languages are closed under complement as in yuxiang's answer is the simplest approach, but here is a direct approach, in case anybody is interested.
First, we establish that for all $m \geq 2$, $m!$ is not a perfect square. I will not repeat a proof here, but you can see here for some justification.
Let $L = \{1^m \mid m \text{ is not a perfect square}\}$. Suppose $L$ is regular. Then, by the pumping lemma, we have a pumping length $n$. First, suppose $n \geq 2$. Then, by the above result, $n!$ is not a perfect square, and hence $1^{n!} \in L$. Since $|1^{n!}| = n! \geq n$, there exists a decomposition $1^{n!} = uvw$ where $|uv| \leq n$, $|v| > 0$, and $uv^kw \in L$ for $k \geq 0$. In particular, since $0 < |v| \leq |uv| \leq n$, we have that $|v| \mid n!$, and it follows that $$\begin{align*} uv^{n!(n! - 1)/|v| + 1}w & = uvwv^{n!(n! - 1)/|v|} && \text{since } u,v,w \in 1^* \\ & = 1^{n!}(1^{|v|})^{n!(n! - 1)/|v|} && \text{since } uvw = 1^{n!} \text{ and } v = 1^{|v|} \\ & = 1^{n!}1^{n!(n! - 1)} \\ & = 1^{(n!)^2} \notin L.\end{align*}$$ However, the pumping lemma states that the left side of this chain of equalities is $\in L$, thus we have a contradiction.
To wrap things up, we should handle the case $n \leq 1$. In this case, we derive $v = 1$ (the terminal, not the number) from the inequality $0 < |v| \leq |uv| \leq n \leq 1$. Thus, we simply pump $v$ until $|uv^kw|$ is a perfect square, and we again have a contradiction.
