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

Please help... Thanks.

Printable View

- October 19th 2011, 10:20 PMjzelltCongruence 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. - October 19th 2011, 10:33 PMTheChazRe: Congruence Proof
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. - October 19th 2011, 10:41 PMDevenoRe: Congruence Proof
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.

- October 19th 2011, 10:45 PMTheChazRe: Congruence Proof
- October 19th 2011, 10:59 PMDevenoRe: Congruence Proof
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".