For every natural number $n$ , let $\pfac{n}$ denote the product of numbers $1 \le m \le n$ with $gcd(m,p) =1$ .

For prime $p$ and $s \in \mathbb{N}$

Proof: We pair up all factors of the product $\pfac{p^s}$ into those numbers $m$ where $m \not\equiv m^{-1} \pmod{p^s}$ and those where this is not the case. So $\pfac{p^s}$ is congruent (modulo $p^s$ ) to the product of those numbers $m$ where $m \equiv m{-1} \pmod{p^s} \leftrightarrow m^2 \equiv 1 \pmod{p^s}$ .

Let $p$ be an odd prime and $s \in \mathbb{N}$ . Since $2 \not\vert p^s$ , $p^s \vert (m^2 -1)$ implies $p^s \vert (m +1)$ either or $p^s \vert (m-1)$ . This leads to$$\pfac{p^s} \equiv -1 \pmod{p^s$$ for odd prime $p$ and any $s \in \mathbb{N}$ .

Now let $p=2$ and $s \ge 2$ . Then$$\left(1 +t.2^{s-1}\right)^2 \equiv 1 \pmod{2^s}, t =\stackrel{-}{+}1$$ Since$$\left(2^{s -1} +1\right)\left(2^{s-1} -1\right) \equiv -1 \pmod{2^s}$$ we have$$\pfac{p^s} \equiv (-1).(-1) =1 \pmod{p^s$$ For $p=2, s \ge 3$ , but $-1$ for $s=1,2. \square$