# Prime Numbers

## What is Prime Number? - Prime Numbers and Determination of Prime Numbers

Prime numbers

Prime numbers are numbers that are divisible by itself and 1 only or the numbers whose only factors are the number itself and
1. Sometimes a question that arises after reading the definition of prime numbers is what factors are. A number is a factor of another number if it can divide it perfectly without any remainder. A few prime numbers, for example, are 2, 3, 5, 7, 11, 13, 17 etc.

The numbers that have more than two factors are called composite numbers. One is neither prime nor composite because it has only one unique factor, which is itself.

There is no largest prime number as for every prime number p there exists a prime number which is greater than p. Euclid’s proof that there are infinitely many prime numbers is the most famous and accepted proof. The largest known prime number has more than 23 million digits giving it one million more digits than the previous record holder.

Determination of prime numbers:

Since there is no largest prime number, finding a new prime number by using the most powerful of the supercomputers is also not possible. There are a few algorithms that are generated for the sole purpose of finding out if a given natural number is prime or not. One of the easiest of such algorithms has been explained below.

Let n be the number we need to find out about. We are not aware if n is a prime number or a composite number. The first step is to take the square root of the number n. The second step comprises of rounding this number to the next highest whole number and name it as m. After finding m, the following few steps are to be performed, in which we find the quotients q2, q3, … qm.
qm = n / m
q(m-1) = n / (m-1)
q(m-2) = n / (m-2)
q(m-3) = n / (m-3)
. . .
q3 = n / 3
q2 = n / 2

The number n is said to be prime only and only if none of the q’s derived are whole numbers.

The reason why prime numbers and finding which number is prime is so important that they are a big help in encrypting data. The main use for prime numbers now has become encryption. Any big hacker can decrypt data or find out that the numbers are prime or not, but among the unlimited number of prime numbers we have, it is almost impossible to decrypt the data that has been encrypted using prime numbers. The fact that we do not even know the largest prime number available makes prime numbers extremely special.

Prime numbers can be divided into two types:

• 1. Mersenne prime

• 2. Fermat prime

• A Mersenne prime number should be reducible to the form 2n – 1, where n will be the prime number and the number formed itself is also a prime number. Mersenne primes are not easy to form and the first few prime numbers that gave us Mersenne primes are n = 2, 3, 5, 7, 13, 17, 19, 31, 61, 89.

Fermat prime is a Fermat number that is also a prime number. The Fermat number Fn is of form 2m+1, where m = 2n where n is an integer.

A few facts about prime numbers are as mentioned below:

• • The number 2 is the only known even prime number. The remaining of the even numbers are divisible by 2, so they are not prime.

• • A number is divisible by 3 if the sum of its digits is divisible by 3.

• • All numbers greater than 5 that ends with a 0 or a 5 are not prime as they are divisible by 5.

• • 0 and 1 are not prime numbers.

• • 0 and 1 are the only numbers that are neither prime nor composite. Excluding them, every other number is either a prime number or a composite number.

• These few quick tricks will help the student identify if a number is prime or not quickly without any loss of precious time. The students can instead use this time to solve the much harder questions.

As a practice the students can try and find all the prime numbers till 1000, using the method mentioned above. The table for all prime numbers up to 1000 shall look like this:
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 227
229 233 239 241 251 257 263 269 271 277
281 283 293 307 311 313 317 331 337 347
349 353 359 367 373 379 383 389 397 401
409 419 421 431 433 439 443 449 457 461
463 467 479 487 491 499 503 509 521 523
541 547 557 563 569 571 577 587 593 599
601 607 613 617 619 631 641 643 647 653
659 661 673 677 683 691 701 709 719 727
733 739 743 751 757 761 769 773 787 797
809 811 821 823 827 829 839 853 857 859
863 877 881 883 887 907 911 919 929 937
941 947 953 967 971 977 983 991 997

Another method that was designed to find prime numbers is as follows. This method is called the Sieve of Eratosthenes. Eratosthenes was a Greek mathematician who designed this simple way to find prime numbers up to 100.

• • 1 is highlighted as it is neither prime nor a composite number.

• • The numbers divisible by 2 i.e. all the even numbers are highlighted. They will form a pattern in which every alternate vertical line is an even number.

• • Then the numbers divisible by 3 are highlighted excluding the number 3 as it is a prime number. This can be done easily by counting every third number. This as well will make a very interesting pattern.

• • Then we highlight the multiples of 5, these multiples are easy to find as they are the numbers ending with 5 or 0. Do not highlight the number 5 as it is a prime number.

• • Next, the multiples of 7 are highlighted. We are already done with the multiples of 2 and 3 so we do not consider the multiples of 6 as they have already been highlighted.

• • We skip looking for the multiples of 8, 9 and 10 as we have already highlighted them. We move on to find the multiples of 11. After finding the multiples of 11 we will be left with only the prime numbers as all the composite numbers have already been highlighted.

• This is a long yet easy way of finding the prime number up to 100. We will not need to find out prime numbers up to 100 in the examination so no need to think and worry about these methods for long. As long as the student is able to identify if the given number is prime or not it will be enough from an exam point of view.

Factoring of composite numbers is also a part of the concept of prime numbers that the students may find interesting to know.
Factoring is dividing a number into parts such that the numbers obtained shall multiply to give the original number. To factor into prime numbers means factoring a given number such that the numbers obtained are prime numbers:

• • Divide the given number by a prime number such as 2. The result should be divided by another prime number such that the remainder is 0.

• • Continue this process of dividing till the quotient that we receive is 1.

• Ex: Factor 36 into prime numbers.
Dividing 36 by 2,
36/2 = 18
Now keep dividing the result by prime number till we reach 1.
18/2 = 9
9/3 = 3
3/3 = 1.
Thus the prime factors for the number 36 are 2 x 2 x 3 x 3.

Below there are a few questions that may help the students check their understanding and knowledge about prime numbers.

• 1. How many integers between 2 and 20, even only, can be the sum of two different prime numbers?

• 2. Define a series of consecutive prime numbers to be a series of numbers, each prime, in which there are no other prime numbers between them. These are not necessarily consecutive numbers themselves. For example, the numbers 5, 7 and 11 are consecutive prime numbers, although they are not consecutive numbers.

• 3. The sum of four consecutive integers is 210. Which one of these four integers is prime?