Results 1 to 5 of 5

Math Help - Congruence of factorials when the mod isn't 10 or 15

  1. #1
    MHF Contributor
    Joined
    Mar 2010
    From
    Florida
    Posts
    3,093
    Thanks
    5

    Congruence of factorials when the mod isn't 10 or 15

    1!+2!+\dots +1000!\equiv x \ \mbox{(mod 11)}

    When k\geq 11, k!\equiv 0 \ \mbox{(mod 11)}

    Since we are adding up to 11!, can this be done without \sum_{i=1}^{10}k! individual?

    1!+2!+\dots +10!\equiv x \ \mbox{(mod 11)}
    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 dwsmith View Post
    1!+2!+\dots +1000!\equiv x \ \mbox{(mod 11)}

    When k\geq 11, k!\equiv 0 \ \mbox{(mod 11)}

    Since we are adding up to 11!, can this be done without \sum_{i=1}^{10}k! individual?

    1!+2!+\dots +10!\equiv x \ \mbox{(mod 11)}
    Well you can reduce mod 11 each time you multiply. So

    1 \equiv 1 mod 11
    2 * 1 \equiv 2 mod 11
    3 * 2 \equiv 6 mod 11
    4 * 6 \equiv 24 \equiv 2 mod 11
    5 * 2 \equiv 10 mod 11
    6 * 10 \equiv 60 \equiv 5 mod 11
    7 * 5 ... etc.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Mar 2010
    From
    Florida
    Posts
    3,093
    Thanks
    5
    Quote Originally Posted by undefined View Post
    Well you can reduce mod 11 each time you multiply. So

    1 \equiv 1 mod 11
    2 * 1 \equiv 2 mod 11
    3 * 2 \equiv 6 mod 11
    4 * 6 \equiv 24 \equiv 2 mod 11
    5 * 2 \equiv 10 mod 11
    6 * 10 \equiv 60 \equiv 5 mod 11
    7 * 5 ... etc.
    So there is no shortcut method of doing this type then? I just have to either add them or do them one at a time and then add the residuals, then.
    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 dwsmith View Post
    So there is no shortcut method of doing this type then? I just have to either add them or do them one at a time and then add the residuals, then.
    Have a computer do it for you? I don't know of any shortcut or formula beyond what I shared, although one might exist.

    PARI/GP is a great CAS for number theory.

    Code:
    sum(i=1,10,i!%11)%11
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member roninpro's Avatar
    Joined
    Nov 2009
    Posts
    485
    You might be able to use Wilson's Theorem:

    (n-1)!\equiv -1\pmod{n} if and only if n is prime.

    In this case, you have (11-1)!=10!\equiv -1\pmod{11}. You can use this fact to get 9! by multiplying by 10^{-1} on both sides. You can get 8! by multiplying by 9^{-1} after that, and etc...

    This method may not really save much time though - you still need to compute modular inverses and peel off terms in the factorial, one by one. Is it really so bad to compute the factorials by hand?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. factorials
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: April 5th 2011, 01:40 AM
  2. Factorials
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: November 2nd 2009, 12:35 PM
  3. factorials
    Posted in the Trigonometry Forum
    Replies: 2
    Last Post: May 6th 2007, 01:02 PM
  4. factorials
    Posted in the Algebra Forum
    Replies: 4
    Last Post: April 26th 2007, 01:16 PM
  5. factorials
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: June 24th 2006, 07:32 PM

/mathhelpforum @mathhelpforum