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$
    – PyRulez
    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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.