2
$\begingroup$

I am having trouble in finding the remainder of $(1\cdot2\cdots102)^3\mod 105$

It is not possible to apply Wilson's Theorem here because 105 is composite. Can anybody help me?

$\endgroup$
5
$\begingroup$

$105 = 3 \cdot 5 \cdot 7, 102!$ is divisible all of $3,5$ and $7,$ therefore $102!^3$ is divisible $105$

$\endgroup$
4
$\begingroup$

Hint: Yes, $105$ is composite. So while you can't use Wilson's theorem, it actually makes the problem a lot easier, rather than more difficult. Think about exactly why Wilson's theorem fails for composite numbers: What is $(n-1)!\pmod n$ in those cases?

$\endgroup$
  • $\begingroup$ I thought of it but I don't know how to follow $\endgroup$ – Luis Gimeno Sotelo May 20 at 14:58
  • 2
    $\begingroup$ @LuisGimenoSotelo Another hint: $105 = 3\cdot 5\cdot 7$. Now take a close look at your product. What numbers are included there? $\endgroup$ – Arthur May 20 at 14:59
  • $\begingroup$ It is ((n-3)!) ^3. But I have tried some examples of composite numbers and I have found no pattern. Is there a pattern? $\endgroup$ – Luis Gimeno Sotelo May 20 at 15:07
  • $\begingroup$ @LuisGimenoSotelo Don't write it as $(n-3)!^3$, write it as $1\cdot 1\cdot 1\cdot 2\cdot 2\cdot 2\cdot 3\cdots$ (don't write all of it, just imagine that you are). Compare what you get there to $105 = 3\cdot 5\cdot 7$ and see if you can spot anything. Apart from that, I have given you two substantial hints, and Reinstein has given you the actual answer. I don't know what more to do for you. $\endgroup$ – Arthur May 20 at 15:10
  • $\begingroup$ It was very easy when you find that 102! is congruent to 0 (mod 3), to 0 (mod 5) and to 0 (mod 7) and because these numbers are prime to each other, 102! is congruent to 0 (mod 3*5*7). Thank you very much! $\endgroup$ – Luis Gimeno Sotelo May 20 at 15:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.