Results 1 to 5 of 5

Math Help - Remainder Problem

  1. #1
    Member
    Joined
    Nov 2008
    Posts
    152

    Remainder Problem

    What is the remainder when 40! is divided by 1763?

    I know this would be much easier if 1763 was prime, but it's not. So I don't see how Fermat's Little Theorem or Wilson's Theorem are applicable.

    I know it comes down to 40! = x (mod 1763), but I don't see how I can manipulate this to find it easily. I thought of making it 37! * 38 * 39 * 40 = x (mod 1763) because 37 is prime, but I don't know if this helps.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by Janu42 View Post
    What is the remainder when 40! is divided by 1763?

    I know this would be much easier if 1763 was prime, but it's not. So I don't see how Fermat's Little Theorem or Wilson's Theorem are applicable.

    I know it comes down to 40! = x (mod 1763), but I don't see how I can manipulate this to find it easily. I thought of making it 37! * 38 * 39 * 40 = x (mod 1763) because 37 is prime, but I don't know if this helps.
    Here's one way.

    Prime factorization of 1763 is 41 * 43.

    From Wilson's theorem, 40! is congruent to -1 (mod 41).

    We know 42! is congruent to -1 (mod 43). So 42*41*40! is congruent to -1 (mod 43) which is congruent to 42 (mod 43). You can multiply each side by 42^(-1) and get 41*40! is congruent to 1 (mod 43). Then multiply each side by 41^(-1) which you can compute.

    Then you can combine with CRT.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Nov 2008
    Posts
    152
    OK, so 40! = 41^(-1) (mod 43). But does that just mean it's 40! = 41 (mod 43)? Or is it something different?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by Janu42 View Post
    OK, so 40! = 41^(-1) (mod 43). But does that just mean it's 40! = 41 (mod 43)? Or is it something different?
    The multiplicative inverse of 41 mod 43 turns out to be 21.

    There is some discussion of modular inverses here.

    http://www.mathhelpforum.com/math-he...ic-148985.html
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Nov 2008
    Posts
    152
    Quote Originally Posted by undefined View Post
    The multiplicative inverse of 41 mod 43 turns out to be 21.

    There is some discussion of modular inverses here.

    http://www.mathhelpforum.com/math-he...ic-148985.html

    OK thanks, I was thinking that it was the inverse before but I wasn't sure if I just messed up the sign in my calculations or something and it should have ended up as 41.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Remainder Problem
    Posted in the Algebra Forum
    Replies: 3
    Last Post: March 8th 2011, 10:23 AM
  2. Remainder problem
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: August 17th 2009, 01:33 AM
  3. remainder problem
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: July 22nd 2009, 09:15 AM
  4. Remainder problem
    Posted in the Algebra Forum
    Replies: 2
    Last Post: January 20th 2009, 04:46 AM
  5. remainder problem
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: June 3rd 2008, 05:33 AM

Search Tags


/mathhelpforum @mathhelpforum