# Wilson’s theorem for prime powers

For every natural number $n$, let $\left(n\underline{!}\right)_{p}$ denote the product of numbers $1\leq m\leq n$ with $gcd(m,p)=1$.

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

 $\left(p^{s}\underline{!}\right)_{p}\equiv\left(\begin{array}[]{ll}1&\mbox{for % }p=2,s\geq 3\\ -1&\mbox{otherwise}\end{array}\right.\pmod{p^{s}}.$

Proof: We pair up all factors of the product $\left(p^{s}\underline{!}\right)_{p}$ into those numbers $m$ where $m\not\equiv m^{-1}\pmod{p^{s}}$ and those where this is not the case. So $\left(p^{s}\underline{!}\right)_{p}$ 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|p^{s}$, $p^{s}|(m^{2}-1)$ implies $p^{s}|(m+1)$ either or $p^{s}|(m-1)$. This leads to

 $\left(p^{s}\underline{!}\right)_{p}\equiv-1\pmod{p^{s}}$

for odd prime $p$ and any $s\in\mathbb{N}$.

Now let $p=2$ and $s\geq 2$. Then

 $\left(1+t.2^{s-1}\right)^{2}\equiv 1\pmod{2^{s}},t=\lx@stackrel{{\scriptstyle-% }}{{+}}1.$

Since

 $\left(2^{s-1}+1\right)\left(2^{s-1}-1\right)\equiv-1\pmod{2^{s}},$

we have

 $\left(p^{s}\underline{!}\right)_{p}\equiv(-1).(-1)=1\pmod{p^{s}}$

For $p=2,s\geq 3$, but $-1$ for $s=1,2.\square$

Title Wilson’s theorem for prime powers WilsonsTheoremForPrimePowers 2013-03-22 13:22:14 2013-03-22 13:22:14 Thomas Heye (1234) Thomas Heye (1234) 8 Thomas Heye (1234) Theorem msc 11A07 msc 11A41