1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Intro to number theory congruence problem 1

  1. Aug 17, 2008 #1
    1. The problem statement, all variables and given/known data
    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)

    2. Relevant equations

    3. 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?
  2. jcsd
  3. Aug 17, 2008 #2


    User Avatar
    Staff Emeritus
    Science Advisor

    If n= ab, then clearly a< n and b< n so both are factors in (n-1)!.
  4. Aug 17, 2008 #3
    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.
  5. Aug 17, 2008 #4
    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!
  6. Aug 18, 2008 #5


    User Avatar
    Staff Emeritus
    Science Advisor

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

    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.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?

Similar Discussions: Intro to number theory congruence problem 1