IMO 2004 — Complete Shortlist Question 29

Given an integer $n \gt 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 \gt 1$, find the remainder of $P_n$ on division by $n$.