Determine all pairs $P(x),Q(x)$ of complex polynomials with leading coefficient $1$ such that $P(x)$ divides $Q(x)^2+1$ and $Q(x)$ divides $P(x)^2+1$.

[i]Proposed by Rodrigo Angelo, Princeton University and Matheus Secco, PUC, Rio de Janeiro[/i]

1. **Initial Assumptions and Simplifications:**
   - Let \( P(x) \) and \( Q(x) \) be complex polynomials with leading coefficient 1.
   - Assume \( P(x) \) divides \( Q(x)^2 + 1 \) and \( Q(x) \) divides \( P(x)^2 + 1 \).
   - If \( P \) or \( Q \) is a constant polynomial, then both must be constant polynomials. All pairs of constant polynomials work.
   - Assume \( \deg(P) > 0 \) and \( \deg(Q) > 0 \).

2. **Degree Analysis:**
   - Let \( \deg(P) = n \) and \( \deg(Q) = m \).
   - Since \( P \) divides \( Q^2 + 1 \), \( \deg(P) \leq 2m \).
   - Since \( Q \) divides \( P^2 + 1 \), \( \deg(Q) \leq 2n \).
   - Assume \( \deg(P) = \deg(Q) = n \).

3. **Polynomial Equation:**
   - There exists a complex number \( c \) such that:
     \[
     Q^2 - cPQ + P^2 + 1 = 0 \quad \text{(Equation 1)}
     \]

4. **Finding Solutions:**
   - Fix \( P \) such that Equation 1 has a polynomial solution \( Q = Q_1 \).
   - The other solution is \( Q_2 = cP - Q_1 \).
   - Therefore, \( \Delta = (c^2 - 4)P^2 - 4 = (Q_1 - Q_2)^2 \) must be a square of a polynomial in \( \mathbb{C}[x] \), say \( \Delta = R^2 \).

5. **Analyzing \( R \):**
   - Suppose \( a = c^2 - 4 \neq 0 \).
   - Let \( r_1, \dots, r_t \) be the roots of \( R \) with multiplicities \( a_1, \dots, a_t \).
   - Since \( R^2 = aP^2 - 4 \) is a polynomial of degree \( 2n \), \( R \) has degree \( n \).
   - For all \( i = 1, \dots, t \), \( P(r_i) = \frac{4}{a} \neq 0 \).

6. **Differentiation:**
   - Differentiating \( R(x)^2 = aP(x)^2 - 4 \):
     \[
     R'(x)R(x) = aP'(x)P(x) \quad \text{(Equation 2)}
     \]
   - For all \( i = 1, \dots, t \), \( r_i \) is a root of \( R'R \) with multiplicity \( 2a_i - 1 \).
   - Since \( r_i \) is not a root of \( P \), \( r_i \) is a root of \( P' \) with multiplicity \( 2a_i - 1 \).

7. **Degree of \( P' \):**
   - The degree of \( P' \) is at least \( (2a_1 - 1) + \dots + (2a_t - 1) \).
   - Since \( 2a_i - 1 \geq a_i \), the degree of \( P' \) is at least \( a_1 + \dots + a_t = n \).
   - This implies \( P \) has degree at least \( n + 1 \), which is a contradiction.

8. **Conclusion:**
   - Therefore, \( a = c^2 - 4 = 0 \Rightarrow c = \pm 2 \).
   - By Equation 1, \( (P \pm Q)^2 = -1 \), leading to \( Q = \pm P \pm i \).
   - All pairs of the form \( (P, \pm P \pm i) \) are solutions.

The final answer is \( \boxed{ (P, \pm P \pm i) } \).