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$
  • 4
    $\begingroup$ Extra credit in a course $\endgroup$ – joe Jul 15 '15 at 17:32
  • $\begingroup$ Maple answers $ 1001$ by direct calculation. $\endgroup$ – user64494 Jul 15 '15 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 '15 at 5:59
33
$\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$
  • $\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 '15 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 '15 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 '15 at 13:16
15
$\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$
  • 3
    $\begingroup$ Nicely done. This is also how the proof for Wilson's theorem proceeds. $\endgroup$ – Joel Jul 15 '15 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.