find remainders

clueles

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.

mathwonk

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?

clueles

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?

shmoe

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?

Data

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]