Solution:
We have $P_{1}(x) = P_{2}(x) = 1$, $P_{3}(x) = x + 1$, $P_{4}(x) = x^{2} + 1$ and $P_{6}(x) = x^{4} + 1$. Hence the integers $n = 1, 2, 3, 4, 6$ have the desired property. We shall prove that these are the only solutions of the problem.

It is enough to show that for $n \geq 3$ the polynomial $P_{n}(x)$ has a divisor of the form $1 + x^{r}$, $r \geq 1$, which is a proper divisor for $n = 5$ and $n \geq 7$.

If $n \geq 3$ is a prime, this follows by the decomposition
$$P_{n}(x) = (1 + x)\left(1 + x^{2} + x^{4} + \cdots + x^{n-3}\right)$$
Note also that $P_{4}(x) = x^{2} + 1$.

Now we shall use induction on $n$. Suppose that the statement is true for all $m \geq 3$ that are less than $n$. If $n \geq 6$ is a composite integer, then $n = m p$, where $p$ is prime and $m \geq 3$. Two cases are possible.

Case 1. $p$ divides $m$. Then we have that $A_{n} = \cup_{i=0}^{p-1} (A_{m} + i m)$ and hence $P_{n}(x) = P_{m}(x) \sum_{i=0}^{p-1} x^{i m}$. It remains to use that $P_{m}(x)$ has a divisor of the form $1 + x^{r}$.

Case 2. $p$ does not divide $m$. Using that
$$A_{n} = \left(\cup_{i=0}^{p-1} (A_{m} + i m)\right) \setminus (p A_{m})$$
and $x^{k p - 1} = x^{p - 1} (x^{p})^{k - 1}$, it follows that
$$P_{n}(x) = P_{m}(x) \sum_{i=0}^{p-1} x^{i m} - x^{p-1} P_{m}(x^{p})$$
By the induction assumption, $P_{m}(x)$ has a divisor of the form $1 + x^{r}$. Therefore $1 + x^{p r}$ divides $P_{m}(x^{p})$. We shall consider two subcases.

a) If $p \geq 3$, then $p$ is odd and $1 + x^{r}$ divides $1 + x^{p r}$. Hence $1 + x^{r}$ divides $P_{n}(x)$.

b) If $p = 2$, we may assume that $m$ is prime (otherwise, $m$ has an odd prime divisor and we may go either to a) or to the first case). Then
$$P_{n}(x) = (1 + x^{m+1})\left(1 + x^{2} + x^{4} + \cdots + x^{m-3}\right)$$
It remains to observe that $P_{n}(x) = 1 + x^{r}$ only for $n = 3, 4, 6$ which completes the solution.