Calculate 2000! (mod 2003)

Question

Calculate 2000! (mod 2003)

This can easily be solved by programming but is there a way to solve it, possibly with knowledge about finite fields? (2003 is a prime number, so mod(2003) is a finite field) .

As much details as possible please, I want to actually understand.

Answer 1

$\mathbb{Z}_{2003}$ is a finite field. The equation $x^2 = 1$ has exactly two roots in that field: $x_1 = 1$ and $x_2 = -1 = 2002$. Thus, every $n \in \mathbb{Z}_{2003}^* \setminus \{ 1, 2002 \}$ has $n^{-1} \neq n$. Hence

$$\prod_{n=2}^{2001} n = 1,$$

because we can split the product into $1000$ pairs of form $(n, n^{-1})$ and the product of each pair cancels out. Therefore $2000! = (2001)^{-1} \pmod{2003}.$

Answer 2

Wilson's theorem is your friend here.

$$(p-1)! \equiv -1 \mod p$$ for prime $p$.

Then notice $$-1 \equiv (2003-1)! = 2002 \cdot 2001 \cdot 2000! \equiv (-1) (-2) \cdot 2000! \mod 2003.$$

Answer 3

I solved it like this.

$2000! \equiv x \pmod {2003} \Rightarrow 2002\cdot 2001\cdot 2000! \equiv 2002\cdot 2001\cdot x \pmod {2003}$

Now, by Wilson's Theorem, and since $2003$ is prime, we know that $$2002! \equiv -1 \pmod {2003}$$

So, $$2002 \cdot 2001 \cdot x \equiv -1 \equiv 2002 \pmod {2003}$$ In other words, $$2001\cdot x \equiv 1 \pmod {2003}$$ Inverting $2001$ using the Euclidean algorithm, you get $x = 1001$ as the smallest solution.

Answer 4

For any odd prime $p$ we have $\left(p-1\right)!\equiv p-1\,\left(\text{mod}\,p\right)$ and $\left(p-2\right)\left(p-3\right)\equiv 2\,\left(\text{mod}\,p\right)$ so $\left(p-1\right)!\equiv \frac{p-1}{2}\,\left(\text{mod}\,p\right)$. The case $p=2003$ gives $\frac{p-1}{2}=1001$.