Results 1 to 5 of 5

Math Help - Congruence Proof

  1. #1
    Super Member
    Joined
    Feb 2008
    Posts
    535

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member TheChaz's Avatar
    Joined
    Nov 2010
    From
    Northwest Arkansas
    Posts
    600
    Thanks
    2

    Re: 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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,311
    Thanks
    691

    Re: 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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member TheChaz's Avatar
    Joined
    Nov 2010
    From
    Northwest Arkansas
    Posts
    600
    Thanks
    2

    Re: Congruence Proof

    Quote Originally Posted by Deveno View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,311
    Thanks
    691

    Re: 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".
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Congruence Proof
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: January 20th 2010, 12:30 PM
  2. Congruence Proof
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: March 19th 2009, 11:37 PM
  3. Proof of a congruence
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: March 19th 2009, 06:08 AM
  4. Congruence Proof
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: September 29th 2008, 11:02 AM
  5. Proof congruence
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: November 19th 2007, 09:13 AM

Search Tags


/mathhelpforum @mathhelpforum