# Prime Numbers and Euclids Proof

Go back to  'Prime Numbers'

## What is a Prime Number?

prime number is any natural number greater than 1 which has no positive factors other than 1 and itself.

The first few prime numbers are 2, 3, 5, 7, 11, 13...

For example, 11 is a prime number because other than 1 and 11, no other natural number is a divisor of 11.

✍Note: 2 is the only even prime number.

Prime numbers play an extremely central role in Mathematics, as we will soon see. They satisfy many interesting properties, yet many results related to primes are still conjectures which have not been proven. Prime numbers have a certain mysterious aspect for mathematicians who study them, as the following statement by a mathematician shows:

Prime numbers grow like weeds among the natural numbers, seeming to obey no other law than that of chance, but they also exhibit stunning regularity and there are laws governing their behavior, and it is amazing that they obey these laws with almost military precision.

The first 49 prime numbers are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, and 227.

## Euclid's Proof:

A very important result that must be mentioned here is the following: the number of primes is infinite. This was first proven by Euclid more than 2300 years ago. And his proof is extremely simple and instructive, so we outline it here in steps:

1. Start by assuming any finite list of prime numbers. Let us denote the finite list of primes as follows (in ascending order, so that the last number is the largest): ${p_1},\,\,{p_2},\,\,{p_3}\,,...,\,{p_n}$

2. Consider the number $$N$$ given by: $N = {p_1} \times {p_2} \times {p_3} \times ... \times {p_n} + 1$

3. First, we note the obvious fact that $$N$$ is larger than $${p_n}$$ . Also, we note that none of the primes on our list will divide $$N$$ since there will always be a remainder of 1 leftover after division with any of these primes.

4. Now, if $$N$$ is a prime number, then we have found a prime number that is larger than the largest prime on our list.

5. If $$N$$ is not a prime number, then some prime number $$p$$ smaller than $$N$$ must divide $$N$$ (can you see why?). But this means that this prime number $$p$$ is not on our list of primes since none of the primes on that list divides $$N$$.

6. In both cases ($$N$$ being prime or non-prime), we have shown that there will definitely exist a prime number that is not on our original list. This reasoning applies to any finite list of primes. For any finite list of primes, there will exist a prime number, not on that list. Thus, we conclude that the number of primes is infinite. Neat, isn’t it?

## Identifying Prime Numbers:

• First, choose a number, for example, 119.

• Now, note that prime numbers between 1 and 10 are 2, 3, 5, 7. (Why between 1 and 10?). Because If $$N$$ is a prime number, then it must NOT be divisible by any prime number $$p$$ such that $$p \leqslant \sqrt N$$.

• Divide the chosen number 119 by each of these four numbers.

• If it's divisible by any of the four numbers, then it isn't a prime number; if it's not divisible by any of the four numbers, then it is prime.

• 119 is divisible by 7, so it is not a prime number.

✍Note: If $$N$$ is a composite, then it must be divisible by any prime number $$p$$ such that $$p \leqslant \sqrt N$$.

## Solved Example:

Example 1: Is 211 a prime number?

Solution: If 211 is a prime number, then it must not be divisible by a prime that is less than or equal to $$\sqrt {211}$$. $$\sqrt {211}$$ is between 14 and 15, so the largest prime number that is less than $$\sqrt {211}$$​ is 13. It is therefore sufficient to test 2, 3, 5, 7, 11, and 13 for divisibility.

211 is not divisible by any of those numbers, so it must be prime. Challenge: What is the largest 3-digit prime number?

⚡Tip: If a three-digit number is composite, then it must be divisible by a prime number that is less than or equal to $$\sqrt {1000}$$. $$\sqrt {1000}$$​ is between 31 and 32, so it is sufficient to test all the prime numbers up to 31 for divisibility.

Arithmetic Integers
Arithmetic Integers
grade 10 | Questions Set 1
Arithmetic Integers
grade 10 | Questions Set 2
Arithmetic Integers