Is the Set of all Primitive Words a Prime Language? A word $w$ is called primitive, if there is no word $v$ and $k &gt; 1$ so that $w = v^k$.
The set $Q$ of all primitive words over an alphabet $\Sigma$ is a well known language. WLOG we can choose $\Sigma = \{ a,b \}$.

A language $L$ is prime, if for every language $A$ and $B$ with $L = A \cdot B$ we have $A = \{\epsilon\}$ or $B = \{ \epsilon \}$.

Is Q prime?

With the help of a SAT solver I could show that we either have $\{a,b\} \subseteq A$ or $\{a,b\} \subseteq B$ as otherwise $\{ ababa, babab \} \subset Q$ cannot be factorized into $A$ and $B$, but have been stuck since then.
The answer is yes. Suppose we have a factorization $Q = A\cdot B$. 

One easy observation is that $A$ and $B$ must be disjoint (since for $w\in A\cap B$ we get $w^2\in Q$). In particular, only one of $A,B$ can contain $\epsilon$. We can assume wlog (since the other case is completely symmetric) that $\epsilon\in B$. Then since $a$ and $b$ cannot be factored into non-empty factors, we must have $a,b\in A$.

Next we get that $a^mb^n\in A$ (and, completely analogously, $b^ma^n\in A$) for all $m,n&gt;0$ by induction on $m$:

For $m=1$, since $ab^n\in Q$, we must have $ab^n = uv$ with $u\in A, v\in B$. Since $u\neq\epsilon$, $v$ must be $b^k$ for some $k\le n$. But if $k&gt;0$, then since $b\in A$ we get $b^{1+k}\in Q$, contradiction. So $v=\epsilon$, and $ab^n\in A$.   

For the inductive step, since $a^{m+1}b^n\in Q$ we have $a^{m+1}b^n = uv$ with $u\in A, v\in B$. Since again $u\neq\epsilon$, we have either $v = a^kb^n$ for some $0&lt;k&lt;m+1$, or $v=b^k$ for some $k&lt;n$. But in the former case, $v$ is already in $A$ by the induction hypothesis, so $v^2\in Q$, contradiction. In the latter case, we must have $k=0$ (i.e. $v=\epsilon$) since from $b\in A$ we get $b^{1+k}\in Q$. So $u=a^{m+1}b^n\in A$. 

Now consider the general case of primitive words with $r$ alternations between $a$ and $b$, i.e. $w$ is either $a^{m_1}b^{n_1}\ldots a^{m_s}b^{n_s}$, $b^{m_1}a^{n_1}\ldots b^{m_s}a^{n_s}$ (for $r=2s-1$), $a^{m_1}b^{n_1}\ldots a^{m_{s+1}}$, or $b^{m_1}a^{n_1}\ldots b^{m_{s+1}}$ (for $r=2s$); we can show that they are all in $A$ using induction on $r$. What we did so far covered the base cases $r=0$ and $r=1$.

For $r&gt;1$, we use another induction on $m_1$, which works very much the same way as the one for $r=1$ above: 

If $m_1=1$, then $w=uv$ with $u\in A, v\in B$, and since $u\neq\epsilon$, $v$ has fewer than $r$ alternations. So $v$ (or its root in case $v$ itself is not primitive) is in $A$ by the induction hypothesis on $r$ for a contradiction as above unless $v=\epsilon$. So $w=u\in A$. 

If $m_1&gt;1$, in any factorization $w=uv$ with $u\neq\epsilon$, $v$ either has fewer alternations (and its root is in $A$ unless $v=\epsilon$ by the induction hypothesis on $r$), or a shorter first block (and its root is in A unless $v=\epsilon$ by the induction hypothesis on $m_1$). In either case we get that we must have $v=\epsilon$, i.e. $w=u\in A$.



The case of $Q' := Q\cup\{\epsilon\}$ is rather more complicated. The obvious things to note are that in any decomposition $Q = A\cdot B$, both $A$ and $B$ must be subsets of $Q'$ with $A\cap B = \{\epsilon\}$. Also, $a,b$ must be contained in $A\cup B$.

With a bit of extra work, one can show that $a$ and $b$ must be in the same subset. Otherwise, assume wlog that $a\in A$ and $b\in B$. Let us say that $w\in Q'$ has a proper factorization if $w=uv$ with $u\in A\setminus\{\epsilon\}$ and $v\in B\setminus\{\epsilon\}$. We have two (symmetric) subcases depending on where $ba$ goes (it must be in $A$ or $B$ since it has no proper factorization). 


If $ba\in A$, then $aba$ has no proper factorization since $ba,a\notin B$. Since $aba\in A$ would imply $abab\in A\cdot B$, we get $aba\in B$. As a consequence, $bab$ is neither in $A$ (which would imply $bababa\in A\cdot B$) nor in $B$ (which would imply $abab\in A\cdot B$). Now consider the word $babab$. It has no proper factorization since $bab\notin A\cup B$ and $abab,baba$ are not primitive. If $babab\in A$, then since $aba\in B$ we get $(ba)^4\in A\cdot B$; if $babab\in B$, then since $a\in A$ we get $(ab)^3\in A\cdot B$. So there is no way to have $babab\in A\cdot B$, contradiction.
The case $ba\in B$ is completely symmetric. In a nutshell: $bab$ has no proper factorization and cannot be in $B$, so it must be in $A$; therefore $aba$ cannot be in $A$ or $B$; therefore $ababa$ has no proper factorization but also cannot be in either $A$ or $B$, contradiction.


I am currently not sure how to proceed beyond this point; it would be interesting to see if the above argument can be systematically generalized.