Calculate 2000! (mod 2003)

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.

• Extra credit in a course – joe Jul 15 '15 at 17:32
• Maple answers $1001$ by direct calculation. – user64494 Jul 15 '15 at 18:38
• Just multiply the numbers 1 to 2000 and then take it mod 2003. If you run out of fingers, use your toes. – PyRulez Jul 16 '15 at 5:59

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.$$

• What you are left with is the need to compute $(-2)^{-1} \mod 2003$. Hint: $2003 = 2004 -1 = 2 \cdot 1002 - 1$. – Joel Jul 15 '15 at 18:13
• Of course you have to prove that 2003 is a prime otherwise you can't be sure that the result is true. – miracle173 Jul 16 '15 at 9:44
• @miracle173 Indeed it is important to verify the primeness of $2003$. It is sufficient to check all the primes up to $43$, since $\sqrt{2003} \approx 44.7$. This can be performed with a calculator. Also, the OP mentioned that they already know that $2003$ is prime. – Joel Jul 16 '15 at 13:16

$\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}.$

• Nicely done. This is also how the proof for Wilson's theorem proceeds. – Joel Jul 15 '15 at 17:45

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$.

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.