Bauer's Identical Congruence

Let $t(m)$ denote the set of the $\phi(m)$ numbers less than and Relatively Prime to $m$, where $\phi(n)$ is the Totient Function. Define

$$f_m(x)\equiv \prod_{t(m)} (x-t).$$ (1)

A theorem of Lagrange states that

$$f_m(x)\equiv x^{\phi(m)}-1\ \left({{\rm mod\ } {m}}\right).$$ (2)

This can be generalized as follows. Let $p$ be an Odd Prime Divisor of $m$ and $p^a$ the highest Power which divides $m$, then

$$f_m(x)\equiv (x^{p-1}-1)^{\phi(m)/(p-1)}\ \left({{\rm mod\ } {p^a}}\right)$$ (3)

and, in particular,

$$f_{p^a}(x)\equiv (x^{p-1}-1)^{p^{a-1}}\ \left({{\rm mod\ } {p^a}}\right).$$ (4)

Furthermore, if $m>2$ is Even and $2^a$ is the highest Power of 2 that divides $m$, then

$$f_m(x)\equiv (x^2-1)^{\phi(m)/2}\ \left({{\rm mod\ } {2^a}}\right)$$ (5)

and, in particular,

$$f_{2^a}(x)\equiv (x^2-1)^{2^{a-2}}\ \left({{\rm mod\ } {2^a}}\right).$$ (6)

See also Leudesdorf Theorem

References

Hardy, G. H. and Wright, E. M. ``Bauer's Identical Congruence.'' §8.5 in An Introduction to the Theory of Numbers, 5th ed. Oxford, England: Clarendon Press, pp. 98-100, 1979.