TOPICS
Search

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)=product_(t in T(m))(x-t).
(1)

Then a theorem of Lagrange states that

 f_p(x)=x^(phi(p))-1 (mod p)
(2)

for p an odd prime (Hardy and Wright 1979, p. 98). Actually, this relationship holds for some composite values as well. Value for which it holds are n=1, 3, 4, 5, 6, 7, 10, 11, 13, 17, 19, 23, 29, ... (OEIS A158008).

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)=(x^(p-1)-1)^(phi(m)/(p-1)) (mod p^a)
(3)

and, in particular,

 f_(p^a)(x)=(x^(p-1)-1)^(p^(a-1)) (mod p^a).
(4)

Now, if m>2 is even and 2^a is the highest power of 2 that divides m, then

 f_m(x)=(x^2-1)^(phi(m)/2) (mod 2^a)
(5)

and, in particular,

 f_(2^a)(x)=(x^2-1)^(2^(a-2)) (mod 2^a).
(6)

See also

Congruence, Leudesdorf Theorem

Explore with Wolfram|Alpha

References

Bauer. Nouvelles annales 2, 256-264, 1902.Hardy, G. H. and Wright, E. M. J. London Math. Soc. 9, 38-41 and 240, 1934.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.Sloane, N. J. A. Sequence A158008 in "The On-Line Encyclopedia of Integer Sequences."

Referenced on Wolfram|Alpha

Bauer's Identical Congruence

Cite this as:

Weisstein, Eric W. "Bauer's Identical Congruence." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/BauersIdenticalCongruence.html

Subject classifications