# Factorial in Modular Arithmetic

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?

• You know that $(41!)^2\equiv 1$. That does not mean that $41!\equiv 1$. – Arthur Oct 9 '17 at 13:56
• ? 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. – Mark Fischler Oct 9 '17 at 13:57
• @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}$. – user236182 Oct 9 '17 at 14:27
• How we would know that 41! has a remainder or 1 instead of 82? is there a sistematic way – SuperMage1 Oct 10 '17 at 11:36

## 1 Answer

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.

• 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. – SuperMage1 Oct 9 '17 at 14:13