Factorial in Modular Arithmetic

693 Views Asked by At

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?

1

There are 1 best solutions below

1
On

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.