For every positive integer $n\ge 3$, let $\phi_n$ be the set of all positive integers less than and coprime to $n$. Consider the polynomial:
$$P_n(x)=\sum_{k\in\phi_n} {x^{k-1}}.$$

a. Prove that $P_n(x)=(x^{r_n}+1)Q_n(x)$ for some positive integer $r_n$ and polynomial $Q_n(x)\in\mathbb{Z}[x]$ (not necessary non-constant polynomial).
b. Find all $n$ such that $P_n(x)$ is irreducible over $\mathbb{Z}[x]$.
### Part (a)
1. **Case 1: \( n \) is odd**

   For \( n \) odd, consider the set \( \phi_n \). For each \( k \in \phi_n \), \( n-k \in \phi_n \) as well. This is because if \( k \) is coprime to \( n \), then \( n-k \) is also coprime to \( n \). 

   Notice that:
   \[
   (-1)^k + (-1)^{n-k} = 0
   \]
   This implies that:
   \[
   P_n(-1) = \sum_{k \in \phi_n} (-1)^{k-1} = 0
   \]
   Hence, \( x+1 \) divides \( P_n(x) \), and we can choose \( r_n = 1 \).

2. **Case 2: \( n \) is divisible by 4**

   If \( 4 \mid n \), then for each \( k \in \phi_n \), \( n-k \in \phi_n \) as well. Note that:
   \[
   i^k + i^{n-k} = 0
   \]
   where \( i \) is the imaginary unit (\( i^2 = -1 \)). This implies:
   \[
   P_n(i) = \sum_{k \in \phi_n} i^{k-1} = 0
   \]
   Hence, \( x^2 + 1 \) divides \( P_n(x) \), and we can choose \( r_n = 2 \).

3. **Case 3: \( n \equiv 2 \pmod{4} \)**

   Let \( p \) be an odd prime dividing \( n \). Let \( r = 2^k \) be the maximal power of 2 dividing \( p+1 \), and let \( s \) be the product of all primes dividing \( n \) except for 2 and \( p \). We need to show that \( x^r + 1 \) divides \( P_n(x) \).

   By Möbius Inversion:
   \[
   xP_n(x) = (x^n - 1) \sum_{d \mid n} \frac{\mu(d)}{x^d - 1} = (x^n - 1) \sum_{d \mid s} \mu(d) \left( \frac{1}{x^d - 1} - \frac{1}{x^{2d} - 1} - \frac{1}{x^{pd} - 1} + \frac{1}{x^{2pd} - 1} \right)
   \]
   Since \( 4 \nmid n \), all denominators are not divisible by \( x^r + 1 \). Also, \( x^r + 1 \) is irreducible over the rationals, so we may work with the quotients. It suffices to prove that \( x^r + 1 \) divides each summand. Since \( x^r + 1 \) divides \( x^{rd} + 1 \), it suffices to prove the claim for \( d = 1 \), i.e., we need to show that \( x^r + 1 \) divides:
   \[
   \frac{1}{x-1} - \frac{1}{x^2-1} - \frac{1}{x^p-1} + \frac{1}{x^{2p}-1}
   \]
   In the quotient field \( \mathbb{Q}[x]/(x^r + 1) \), we have \( x^{p+1} = -1 \). Hence:
   \[
   \frac{1}{x-1} - \frac{1}{x^2-1} - \frac{1}{x^p-1} + \frac{1}{x^{2p}-1} = \frac{x}{x^2-1} - \frac{x^p}{x^{2p}-1} = \frac{x}{x^2-1} - \frac{x^{p+2}}{x^{2p+2} - x^2} = \frac{x}{x^2-1} + \frac{x}{1-x^2} = 0
   \]
   This proves our claim.

### Part (b)
To find all \( n \) such that \( P_n(x) \) is irreducible over \( \mathbb{Z}[x] \), \( Q_n \) must be constant, and hence \( P_n \) must be of the form \( x^r + 1 \). In particular, \( \varphi(n) = P_n(1) = 2 \). It is well-known that this happens if and only if \( n \in \{3, 4, 6\} \).

The final answer is \( \boxed{ n \in \{3, 4, 6\} } \)