Given an integer ${n>1}$, denote by $P_{n}$ the product of all positive integers $x$ less than $n$ and such that $n$ divides ${x^2-1}$. For each ${n>1}$, find the remainder of $P_{n}$ on division by $n$.

[i]Proposed by John Murray, Ireland[/i]
Given an integer \( n > 1 \), denote by \( P_n \) the product of all positive integers \( x \) less than \( n \) such that \( n \) divides \( x^2 - 1 \). We need to find the remainder of \( P_n \) on division by \( n \).

1. **Identify the set \( S_n \):**
   \[
   S_n = \{ x \in \mathbb{N} \mid x < n \text{ and } n \mid (x^2 - 1) \}
   \]
   Since \( n \mid (x^2 - 1) \), we have \( x^2 \equiv 1 \pmod{n} \). This implies \( (x-1)(x+1) \equiv 0 \pmod{n} \). Therefore, \( x \equiv 1 \pmod{n} \) or \( x \equiv -1 \pmod{n} \).

2. **Symmetry in \( S_n \):**
   Observe that if \( x \in S_n \), then \( n - x \in S_n \) as well. This is because:
   \[
   (n - x)^2 \equiv x^2 \equiv 1 \pmod{n}
   \]
   Hence, \( S_n \) is symmetric around \( n/2 \).

3. **Product of elements in \( S_n \):**
   Let \( S_n \) have \( 2m \) elements. The product \( P_n \) can be written as:
   \[
   P_n = \prod_{x \in S_n} x
   \]
   Since \( x \) and \( n - x \) are both in \( S_n \), we can pair them:
   \[
   P_n = \prod_{i=1}^{m} x_i (n - x_i)
   \]
   Each pair \( x_i (n - x_i) \equiv -x_i^2 \pmod{n} \). Therefore:
   \[
   P_n \equiv (-1)^m \prod_{i=1}^{m} x_i^2 \pmod{n}
   \]

4. **Case analysis based on \( n \):**
   - **Case 1: \( n \) is odd.**
     Let \( n = \prod_{i=1}^{r} p_i^{\alpha_i} \) where \( p_i \) are odd primes. By the Chinese Remainder Theorem (CRT), we can choose \( x_0 \) and \( x_1 \) such that:
     \[
     x_0 \equiv 1 \pmod{p_1^{\alpha_1}}, \quad x_0 \equiv -1 \pmod{p_2^{\alpha_2}}, \quad x_0 \equiv -1 \pmod{p_3^{\alpha_3}}, \ldots
     \]
     \[
     x_1 \equiv -1 \pmod{p_1^{\alpha_1}}, \quad x_1 \equiv 1 \pmod{p_2^{\alpha_2}}, \quad x_1 \equiv 1 \pmod{p_3^{\alpha_3}}, \ldots
     \]
     Then \( x_0 x_1 \equiv -1 \pmod{n} \). Since there are \( 2^r \) total residue sets, there would be \( 2^{r-1} \) pairs. Hence:
     \[
     P_n \equiv (-1)^{2^{r-1}} \pmod{n}
     \]
     For \( r \ge 2 \), \( (-1)^{2^{r-1}} = 1 \). For \( r = 1 \), \( (-1)^{2^{0}} = -1 \).

   - **Case 2: \( n \) has a prime factor other than 2.**
     Write \( n = 2^k \prod_{i=1}^{r} p_i^{\alpha_i} \). Similar to the previous case, pairing residue classes gives \( 2^{r+1} \) pairs.

   - **Case 3: \( n = 2^k \).**
     Here, \( P_n = 1 \) if \( k \ge 3 \) and \( P_n = -1 \) if \( k = 1 \) or \( k = 2 \).

Combining the above possibilities, we get the result.

The final answer is \( \boxed{P_n \equiv -1 \pmod{n} \text{ if } n \text{ has a primitive root and 1 otherwise.}} \)