Thread: Congruence Proof

Show that if n is a composite integer not equal to 4, then (n-1)! is congruent to 0 (mod n).

Please help... Thanks.

n = a*b,
Suppose n > a > b > 1
Then (n-1)! = (n - 1)(n - 2)... (a) ... (b) .... (2)(1), which is clearly divisible by n = a*b.

what about the case n = a^2? (for example, 9, or 25, or 49, etc.)? i believe that here is where you must use the fact that n > 4.

Originally Posted by Deveno

what about the case n = a^2? (for example, 9, or 25, or 49, etc.)? i believe that here is where you must use the fact that n > 4.

You're welcome to investigate that case... I was just getting the ball rolling!
p.s. That (n = a^2) is not why n > 4.

if n = a^2, and n > 4, then a > 2. so n = a^2 > 2a > a > 2 , in which case n-1 ≥ 2a > a > 1, so both a and 2a are factors of (n-1)! since a^2 divides 2a^2, a^2 clearly divides (n-1)!

for n = 4 (a = 2), 2a is "too big" to divide 3!, 4 does not divide 6.

for n = 9 (a = 3), 3 and 6 (a and 2a) are the only factors of 8! = (2)(3)(4)(5)(6)(7)(8) divisible by 3, a is "just small enough".