Prove that 2003 is prime.

Question

How do I prove that 2003 is a prime number? It's not very impressive going through factors and searching the internet only gives answers to smaller numbers. Can anyone help?

Answer 1

You can use the trial division test and divide $n$ by all the primes up to $\left\lceil \sqrt {2003} \right\rceil$ (which is equal to 45). Here is a set $P$ that defines all the primes up to 45: $$P = \{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43\}$$ Since 2003 doesn't evenly divide into any of these numbers, 2003 is prime. I know it will take 14 trials, but it is more efficent than using 2001 trials (you shouldn't do 1 and 2003 because they divide evenly into 2003).

Answer 2

It's not foolproof, but you can do $2^{2002} \equiv 1 \pmod{2003}$ (this is Fermat's little theorem), but $2003$ could be a pseudoprime. So then you could see that $2002! \equiv 2002 \pmod{2003}$. This is Wilson's theorem, since it's an if-and-only-if theorem, you're done.

The use of congruences helps keep these numbers reasonably small, you don't actually have to compute the full value of $2^{2002}$ or $2002!$.

Answer 3

According to Euler's totient theorem, we have for integer $a$ and $n$ such that $a$ and $n$ are relatively prime:

$$a^{\phi(n)} = 1 \mod n$$

where $\phi(n)$ is the number of integers less than $n$ that are relatively prime to $n$. The order of $a$ is the smallest integer $d$ such that $a^d = 1 \mod n$, and Euler's totient theorem implies that the order of $a$ must always be a divisor of $\phi(n)$ (if not dividing the equation $a^{\phi(n)}=1 \mod n$ repeatedly by $a^d = 1\mod n$ will yield a number $u<d$ such that $a^u = 1\mod n$, contradicting that $d$ is the order of $a$ ).

Now, a number $n$ is prime if and only if $\phi(n) = n-1$. Obviously if $n$ is prime, all the $n-1$ integers smaller than $n$ will be relatively prime to it, and conversely, if all the $n-1$ integers smaller than n are relatively prime to $n$, then $n$ cannot have nontrivial factors.

To prove that $\phi(n) = n-1$, it is not sufficient to demonstrate that for some number $a$ you have $a^{n-1} = 1\mod n$, because it may then be the case that $\phi(n) < n-1$ but such that $n-1$ is a multiple of the order of $a$. To exclude such cases of so-called "pseudoprimes", one can find a number $a$ such that its order is $n-1$. We know that if $a^{n-1} =1\mod n$, then $n-1$ will be a multiple of the order $d$ of $a$. If $d<n-1$, then for some prime divisor $q$ of $n-1$ you must have that $a^{\frac{n-1}{q}}=1\mod n$. So, all we need to do is find a number $a$ for which this doesn't happen.

For $n = 2003$, we have $n-1 = 2\times 7\times 11\times 13$, and we can easily compute by squaring repeatedly and multiplying that (everything mod 2003):

$$5^{\frac{2002}{2}} = -1$$

$$5^{\frac{2002}{7}} = 874$$

$$5^{\frac{2002}{11}} = 886$$

$$5^{\frac{2002}{13}} = 633$$