Number Theory: Division with remainder of factorials

[miren324]

I'm struggling with how to even begin with this problem.

Find the remainder of the division of 75!*130! by 211.

211 is prime, so I know the remainder is not 0. I'm not sure where to start though.

Thanks!

 

[Citan Uzuki]

Note that you can interpret 75! as (-1)^75*(-1)*(-2)*...*(-75). Working mod 211, you thus see that -75!*130! is the product of all but 5 nonzero elements of \mathbb{Z}/211\mathbb{Z}. Now, find the product of all nonzero elements, and divide by the 5 that are missing.

 

[miren324]

Just to make sure I'm clear, since 75!=((-1)^75)(-1)(-2)...(-75), then 75!130!=(-1)(-1)(-2)...(-75)(1)(2)...(130). Now, 75!130! is the product of all (but 5) nonzero elements of Z/211Z because in mod 211 -1 is 210, -2 is 209, and -75 is 136, so all we are missing in our product are 131, 132, 133, 134, and 135.

Now, please explain your last sentence, because it seems like you're saying find 211! and divide by 131*132*133*134*135, which is a very large number and too difficult to calculate by hand, unless I'm missing some trick for factorials.

 

[Dick]

Just to make sure I'm clear, since 75!=((-1)^75)(-1)(-2)...(-75), then 75!130!=(-1)(-1)(-2)...(-75)(1)(2)...(130). Now, 75!130! is the product of all (but 5) nonzero elements of Z/211Z because in mod 211 -1 is 210, -2 is 209, and -75 is 136, so all we are missing in our product are 131, 132, 133, 134, and 135.

Now, please explain your last sentence, because it seems like you're saying find 211! and divide by 131*132*133*134*135, which is a very large number and too difficult to calculate by hand, unless I'm missing some trick for factorials.

What's 210! mod 211? You don't have to calculate it. There is a theorem. Remember?

 

[miren324]

So, by Wilson's Theorem I have 210! \equiv -1 (mod 211). Now I divide by 131*132*133*134*135\equiv 208 (mod 211). Now divide 210 by 208 (mod 211).

210/208 = x (mod 211)
210 = 208x (mod 211)
210 = 208x + 211y

211 = 210(1)+3 so 3=211-208(1)
208 = 3(69) + 1 so 1 = 208-3(69)
3 = 1(3) so gcd(208, 211)=1 [which we knew already because 211 is prime].

Now using Euclidean algorithm backwards:
1 = 208 - 3(69) = 208 - 69(211 - 208) = 70(208) - 69(211)

Need to solve 210=208x+211y so multiply by 210 and I have
210 = 208(14700) + 211(-14490)

Thus x = 14700 so 210/208 \equiv 14700 (mod 211) \equiv 141 (mod 211).

Is this right? I did a lot of steps in there that I haven't used since the beginning of this semester, or possibly since last semester, so I'm not sure I remembered everything correctly.

 

[Dick]

So, by Wilson's Theorem I have 210! \equiv -1 (mod 211). Now I divide by 131*132*133*134*135\equiv 208 (mod 211). Now divide 210 by 208 (mod 211).

210/208 = x (mod 211)
210 = 208x (mod 211)
210 = 208x + 211y

211 = 210(1)+3 so 3=211-208(1)
208 = 3(69) + 1 so 1 = 208-3(69)
3 = 1(3) so gcd(208, 211)=1 [which we knew already because 211 is prime].

Now using Euclidean algorithm backwards:
1 = 208 - 3(69) = 208 - 69(211 - 208) = 70(208) - 69(211)

Need to solve 210=208x+211y so multiply by 210 and I have
210 = 208(14700) + 211(-14490)

Thus x = 14700 so 210/208 \equiv 14700 (mod 211) \equiv 141 (mod 211).

Is this right? I did a lot of steps in there that I haven't used since the beginning of this semester, or possibly since last semester, so I'm not sure I remembered everything correctly.

That's really good. Except you got the negative of the correct answer. When you said 75!130!=(-1)(-1)(-2)...(-75)(1)(2)...(130) that was great. But you are forgetting that first (-1).