Results 1 to 4 of 4

Math Help - nonegative residu

  1. #1
    Junior Member
    Joined
    Sep 2008
    Posts
    62

    nonegative residu

    Find the least nonnegative residue of 2(100!) modulo 103

    This is what I have so far but dont know where to go form here:

    2(100!)x≡1 mod 103
    2(100!)x≡104 mod 103
    100!x≡52 mod 103
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    Hello,
    Quote Originally Posted by rmpatel5 View Post
    Find the least nonnegative residue of 2(100!) modulo 103

    This is what I have so far but dont know where to go form here:

    2(100!)x≡1 mod 103
    2(100!)x≡104 mod 103
    100!x≡52 mod 103
    I don't understand what x≡ is o.O

    Okay, by Wilson's theorem, you know that (102)! \equiv -1 (\bmod 103)

    (102)!=(100)! \cdot 101 \cdot 102=2(100)! \cdot (101 \times 51)

    101 \times 51=(103-2) \times 51=103 \times 51 -2 \times 51 \equiv -102 (\bmod 103) \equiv 1 (\bmod 103)

    Hence (102)!=2(100)! \cdot (101 \times 51) \begin{array}{ll} \equiv 2(100)! (\bmod 103) \\ \equiv -1 (\bmod 103) \end{array}

    -1 mod 103 = 102 mod 103. this is the least nonnegative residue.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Sep 2008
    Posts
    62
    Quote Originally Posted by Moo View Post
    Hello,

    I don't understand what x≡ is o.O

    Okay, by Wilson's theorem, you know that (102)! \equiv -1 (\bmod 103)

    (102)!=(100)! \cdot 101 \cdot 102=2(100)! \cdot (101 \times 51)

    101 \times 51=(103-2) \times 51=103 \times 51 -2 \times 51 \equiv -102 (\bmod 103) \equiv 1 (\bmod 103)

    Hence (102)!=2(100)! \cdot (101 \times 51) \begin{array}{ll} \equiv 2(100)! (\bmod 103) \\ \equiv -1 (\bmod 103) \end{array}

    -1 mod 103 = 102 mod 103. this is the least nonnegative residue.
    I understand what you did by Wilson's theorem and then breaking down the factorial of 102 to 2(100!)101*51. But after that i am lost to what your doing. I dont know why your doing anything.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    Quote Originally Posted by rmpatel5 View Post
    I understand what you did by Wilson's theorem and then breaking down the factorial of 102 to 2(100!)101*51. But after that i am lost to what your doing. I dont know why your doing anything.
    Yeah I know, it's a real mess...

    Keep in mind that we want to find x in {\color{red}2(100)!} \equiv x (\bmod 103)

    We know that (102)! \equiv -1 (\bmod 103), that is to say (102)! \equiv 102 (\bmod 103) \quad (1)

    But (102)!={\color{red}2(100)!} \times (51 \times 101)

    So \boxed{(102)! \equiv 2(100)! \times (51 \times 101) (\bmod 103)}


    So if I can reduce 51 \times 101 (\bmod 103), it would be nice !
    101 is 103-2, so writing it this way will make appear 103.
    51 \times 101=51 \times (103-2)=103 \times 51 - 2 \times 51 \equiv 0-2 \times 51 (\bmod 103)

    -2 \times 51=-102 \equiv 1 (\bmod 103)

    Hence, if we go back to the boxed expression, we'll get :

    (102)! \equiv 2(100)! \times (51 \times 101) (\bmod 103) \equiv 2(100)! \times 1 (\bmod 103)

    But we know that (102)! \equiv 102 (\bmod 103) (1)

    Therefore 2(100)! \equiv 102 (\bmod 103)

    \boxed{x=102}
    Last edited by Moo; October 7th 2008 at 12:35 PM.
    Follow Math Help Forum on Facebook and Google+

Search Tags


/mathhelpforum @mathhelpforum