Intro to number theory congruence problem 1

[Proggy99]

Homework Statement

If n>4 is a composite number, show that n|(n-1)! Conclude that (n-1)! not congruent -1(mod n).

(This shows that Wilson's theorem can be used as a proof of primality. It is unfortunately not practical for large numbers)

Homework Equations

The Attempt at a Solution

I know in words why a composite (ab) number does not work, but am not really sure how to prove it. Can anyone give me a jumping off point for this problem please?

 

[HallsofIvy]

If n= ab, then clearly a< n and b< n so both are factors in (n-1)!.

 

[Proggy99]

If n= ab, then clearly a< n and b< n so both are factors in (n-1)!.

and if a|(n-1)! and b|(n-1)!, then ab|(n-1)! and since n=ab, then n|(n-1)!

Then since (n-1)! congruent 0(mod n), then (n-1)! not congruent -1(mod n)

Did I follow that through correctly?

It strikes me that if a=b, then this might break down my reasoning and the problem did not specify whether a=b or not or if it mattered. I will have to think on that a little.

 

[Proggy99]

found the answer to my a=b or n=a^2 question. Seems that there are three possibilities to consider...when a not = b, when a=b and a is prime, when a=b and a is not prime. When a not = b and when a=b and a is not prime are easier to prove. a=b and a is prime relies on the additional information that n>4 to prove. Thanks for the help on this problem!

 

[HallsofIvy]

I don't see why those have to be considered separately. If n= ab, why does it matter if a= b or not?

 

[Proggy99]

I don't see why those have to be considered separately. If n= ab, why does it matter if a= b or not?

well, my professor expects us to be pretty thorough when considering all the possibilities and explaining them away. For instance:

if n=9=3*3, then ab=3*3 and (n-1)! = 1*2*3*4*5*6*7*8
The reason it still works for 3*3 is because both 3 and 2*3 occur in the problem, and in fact when n=c^2, both c and 2*c will always occur in the problem. This is because
p=n(1/2) <= (n-1)/2 for n>4, thus 2p<= n-1

I would imagine that my professor would have marked me down for not taking that into consideration, as he has done on other problems in the past. I am curious on whether you would consider it necessary to include the additional explanation or if you consider it part of the shorter explanation? Thanks again for the help HoI.