0
$\begingroup$

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?

$\endgroup$
7
  • 4
    $\begingroup$ You only need to test primes up to 43 (including 43) to prove that it is prime. (why?) $\endgroup$ – Justin Benfield Mar 12 '16 at 16:23
  • 1
    $\begingroup$ Maybe note that you can only check the primes less than $\sqrt{2003}$... $\endgroup$ – VanDerWarden Mar 12 '16 at 16:24
  • $\begingroup$ if the number is not divisible by the first 6 prime numbers it can be concluded it is prime $\endgroup$ – user5954246 Mar 12 '16 at 17:22
  • $\begingroup$ and this condition we use in making programs $\endgroup$ – user5954246 Mar 12 '16 at 17:24
  • $\begingroup$ @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. $\endgroup$ – Obinna Nwakwue Mar 15 '16 at 15:12
7
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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

$\endgroup$
5
  • 1
    $\begingroup$ 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$? $\endgroup$ – Erick Wong Mar 17 '16 at 18:30
  • $\begingroup$ But how is $2002! \equiv 2002$ (because $2002 \equiv 2002 \pmod {2003}$, according to WolframAlpha)? $\endgroup$ – Obinna Nwakwue Mar 29 '16 at 0:01
  • $\begingroup$ @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. $\endgroup$ – Mr. Brooks Mar 30 '16 at 20:55
  • $\begingroup$ But, we're trying to prove $2003$ prime. $\endgroup$ – Obinna Nwakwue Mar 30 '16 at 21:59
  • $\begingroup$ @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. $\endgroup$ – Mr. Brooks Mar 31 '16 at 21:06
3
$\begingroup$

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

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

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