3
$\begingroup$

What is the remainder when $41!$ is divided by $83$?

I have tried getting the remainders for each factor $$41 \equiv -42 \pmod{83}$$ and so on, and I get:

$$(41!)^2 \equiv -(82!) \pmod{83},$$ I then applied Wilson's theorem

\begin{align} (41!)^2 &\equiv 1 \pmod{83} \\ 41! &\equiv 1 \pmod{83} \end{align}

Can you see where I went wrong?

$\endgroup$
  • 3
    $\begingroup$ You know that $(41!)^2\equiv 1$. That does not mean that $41!\equiv 1$. $\endgroup$ – Arthur Oct 9 '17 at 13:56
  • $\begingroup$ ? If you already know (line 3) that $41! = -42 = 41 \pmod{83}$ then what is the problem. Note that $1$ has more than one square root. $\endgroup$ – Mark Fischler Oct 9 '17 at 13:57
  • $\begingroup$ @MarkFischler $41!\not\equiv -42\pmod{83}$. OP is correct that $(41!)^2\equiv 1\pmod{83}$. We have $(-42)^2\equiv 21\not\equiv 1\pmod{83}$. OP wrote $41\equiv -42\pmod{83}$. $\endgroup$ – user236182 Oct 9 '17 at 14:27
  • $\begingroup$ How we would know that 41! has a remainder or 1 instead of 82? is there a sistematic way $\endgroup$ – SuperMage1 Oct 10 '17 at 11:36
2
$\begingroup$

I believe you ended up getting the right answer, but your methods aren't entirely correct. When you said

$$(41!)^2 \equiv 1\bmod 83$$

$$41! \equiv 1\bmod 83,$$

you didn't take into account that both $1$ and $-1$ are square roots of $1\bmod 83$. See if you can fix that.

$\endgroup$
  • $\begingroup$ How would you know what remainder you would use in solving for the congruency?, like 2^41 mod 83, we would get the same roots. $\endgroup$ – SuperMage1 Oct 9 '17 at 14:13

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.