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?

closed as off-topic by T. Bongers, Shailesh, Leucippus, John B, user26857 Mar 13 '16 at 0:30

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – T. Bongers, Shailesh, Leucippus, John B, user26857
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 4
    You only need to test primes up to 43 (including 43) to prove that it is prime. (why?) – Justin Benfield Mar 12 '16 at 16:23
  • 1
    Maybe note that you can only check the primes less than $\sqrt{2003}$... – VanDerWarden Mar 12 '16 at 16:24
  • if the number is not divisible by the first 6 prime numbers it can be concluded it is prime – user5954246 Mar 12 '16 at 17:22
  • and this condition we use in making programs – user5954246 Mar 12 '16 at 17:24
  • @JustinBenfield, you need to test the primes $\leq 43$ because the maximum prime that is less than $\left\lceil \sqrt{2003} \right\rceil$ is 43. – Obinna Nwakwue Mar 15 '16 at 15:12

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

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

  • 1
    There are efficient ways to compute $2^{2002}$ mod $2003$, but how do you propose to compute $2002!$ mod $2003$ in a way that isn't more tedious than trial division up to $43$? – Erick Wong Mar 17 '16 at 18:30
  • But how is $2002! \equiv 2002$ (because $2002 \equiv 2002 \pmod {2003}$, according to WolframAlpha)? – Obinna Nwakwue Mar 29 '16 at 0:01
  • @ObinnaNwakwue I typed 2002! mod 2003 and it said $2002$, just as I expected, because $2003$ is in fact prime. Compare to the small primes: $4! \equiv 4 \pmod 5$, $6! \equiv 6 \pmod 7$, $10! \equiv 10 \pmod{11}$, etc. – Mr. Brooks Mar 30 '16 at 20:55
  • But, we're trying to prove $2003$ prime. – Obinna Nwakwue Mar 30 '16 at 21:59
  • @ObinnaNwakwue You wrote "according to WolframAlpha," so that's why I put it to WolframAlpha. Luke didn't mention WolframAlpha, so I didn't mention it in my answer. – Mr. Brooks Mar 31 '16 at 21:06

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

  • Wait, $p=143$ isn't a prime number, so how does the theorem apply? – Erick Wong Mar 17 '16 at 18:31
  • @ErickWong Yes I see now. I'll replace the theorem by the more general one involving finding a primitive element. – Count Iblis Mar 17 '16 at 19:47

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