4
$\begingroup$

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.

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

4 Answers 4

35
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ What you are left with is the need to compute $(-2)^{-1} \mod 2003$. Hint: $2003 = 2004 -1 = 2 \cdot 1002 - 1$. $\endgroup$
    – Joel
    Jul 15, 2015 at 18:13
  • 2
    $\begingroup$ Of course you have to prove that 2003 is a prime otherwise you can't be sure that the result is true. $\endgroup$
    – miracle173
    Jul 16, 2015 at 9:44
  • 1
    $\begingroup$ @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. $\endgroup$
    – Joel
    Jul 16, 2015 at 13:16
16
$\begingroup$

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

$\endgroup$
1
  • 3
    $\begingroup$ Nicely done. This is also how the proof for Wilson's theorem proceeds. $\endgroup$
    – Joel
    Jul 15, 2015 at 17:45
5
$\begingroup$

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

$\endgroup$
5
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .