Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Find remainders

  1. Mar 13, 2005 #1
    I have 2 questions.

    1)what is the remainder with 100! is divided by 103? explain your answer

    2)a = 238000 = 2^4 x 5^3 x 7 x 17 and b=299880 = 2^3 x 3^2 x 5 7^2 17. Is there an integer so that a divides b^n? if so what is the smallest possibility for n?

    the first one i have no idea how to even start it and the second one i know that the prime factorization helps to find out what n is.
  2. jcsd
  3. Mar 13, 2005 #2


    User Avatar
    Science Advisor
    Homework Helper

    I think I would start by asking what is the remainder when 102! is divided by 103. i.e. zero. Then lets see if that helps.

    Since 103 is prime, then mod 103, the numbers from 1 to 102 forma multiplicative group, i.e. each has an inverse such thnat its product with that guy is 1. now there are two numbers equal to their own inverse 1 and 102 = -1. so no other number equals its own inverse. thus when we multiplky all these numbers to gether, we get -1. so the remainder of 102! is -1 mod 103. but 102! equals (102)(101)(100!),

    so (102)(101)(100!) = -1 mod 103. does that help?
  4. Mar 13, 2005 #3
    can you explain it again

    i'm still confused about it. how do you get the -1. i'm sorry would you be able to explain it a different way?
  5. Mar 13, 2005 #4


    User Avatar
    Science Advisor
    Homework Helper

    1) have you seen Wilson's theorem? If so, mathwonk's post should look familiar

    2) How do the exponents in the prime factorization tell you when one number is divisible by another? Can you answer this- does a divide b? Can you tell this just from comparing exponents?
  6. Mar 13, 2005 #5
    The integers taken modulo any prime p form a field. 103 is prime, so [tex]\mathbb{Z}_{103}[/tex] is a field. Thus, [tex] \forall x \in \mathbb{Z}_{103}, \exists x^{-1} \in \mathbb{Z}_{103} \ \mbox{s.t.} \ xx^{-1} = x^{-1}x = 1[/tex]. Now, if [tex]x=1 \ \mbox{or} \ x=102 = -1, \ \mbox{then} \ x^{-1} = x \ \mbox{in} \ \mathbb{Z}_{103}[/tex]. Thus when you multiply all the elements in [tex]\mathbb{Z}_{103}[/tex] together, ie. take [tex]102! = \prod_{\mathbb{Z}_{103} \ni i=1}^{102} i[/tex], you just get [tex](102)(1) = (-1)(1) = -1[/tex], and so [tex] 102! \equiv -1 \equiv 102 \ (\mbox{mod} 103)[/tex]
    Last edited: Mar 13, 2005
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook