Raja Oktovin wrote: Let $ A = \{n: 1 \le n \le 2009^{2009},n \in \mathbb{N} \}$ and let $ S = \{n: n \in A,\gcd \left(n,2009^{2009}\right) = 1\}$. Let $ P$ be the product of all elements of $ S$. Prove that \[ P \equiv 1 \pmod{2009^{2009}}.\] Nanang Susyanto, Jogjakarta Easy We have: if $ x\in S$ then $ 2009^{2009} - x \in S$ So: $ P\equiv ( - 1)^{\frac {|S|}{2}}$ We easy prove that $ |S| = \phi (2009^{2009}) = 4k$ So problem had proven.

this problem can be found here : PEN D12

Generalised Wilson's theorem states that: $\prod_{1\le x\le n, \gcd(x,n)=1} x\equiv 1\pmod{n}$ for $n\ne 4, p^{\alpha}, 2p^{\alpha}$ for odd prime $p$. Since $2009$ is composite, the result follows.