# Prime Numbers and Composite Numbers

There are two types of natural numbers, prime and composite, except 1.

# Prime numbers

The numbers which are divisible by 1 and itself only are known as prime numbers.
In other words, we can say that all the numbers which have only two factors are known as prime numbers.

Prime numbers can also be seen as the building blocks. We combine two or more than two prime numbers, same or distinct, to create numbers bigger than these prime numbers. For example, 3 × 2 = 6.

List of all the prime numbers less than 1000

Number of prime numbers for every 100 numbers

Largest prime number till date and the history of prime number The largest known prime number, today, is 7,816,230-digit prime number, 2

^{25964951}−1, found in early 2005. But how big have the “largest known primes” been historically and when can we see the first billion-digit prime number?

**Records before the advent of electronic computers**

Number |
Digits |
Year |
Prover |
Method |

2^{17}−1 |
6 | 1588 | Cataldi | Trial division |

2^{19}−1 |
6 | 1588 | Cataldi | Trial division |

2^{31}−1 |
10 | 1772 | Euler | Trial division |

(2^{59}−1)/179951 |
13 | 1867 | Landry | Trial division |

2^{127}−1 |
39 | 1876 | Lucas | Lucas sequences |

(2^{148}+1)/17 |
44 | 1951 | Ferrier | Proth’s theorem |

The prime number found by Lucas in 1876 was accepted as the largest prime number till 1951. In 1951, Ferrier used a mechanical desk calculator and techniques based on partial inverses of Fermat’s little theorem (see the pages on remainder theorem) to slightly better this record by finding a 44-digit prime.

In 1951, Ferrier found the prime

(2

^{148 }+ 1)/17 =20988936657440586486151264256610222593863921. However, this record was very short-lived. In the same year, the advent of electronic computers helped in finding a bigger prime number. Miller and Wheeler began the electronic computing age by finding several primes as well as the new 79-digit record: 2

^{127}−1.

During this period, everybody was working hard to find out the primes with the help of computers. Records were broken at a never-before pace. Sometimes, within a day.

When will we have a one-billion digit prime?

Using the regression line given above, we can expect

- 10,000,000-digit prime by 2007,
- a 100,000,000-digit prime by 2016, and
- a 1,000,000,000-digit prime by early 2027.

# Formula for prime numbers

Till now, all attempts made to arrive at a single formula to represent all prime numbers have proved to be fruitless. It is all because there is no symmetricity between the differences among the prime numbers. Sometimes, two consecutive prime numbers differ by 2, sometimes by 4, and sometimes even by 10,000 or more.However, there are some standard notations, which give us a limited number of prime numbers.

N

^{2}+ N + 41 → For all the values of N from –39 to +39, this expression gives us a prime number.

N

^{2}+ N + 17 is again a similar example.

# Properties of Prime Numbers

- All prime numbers end in 1, 3, 7, or 9, except for 2 and 5. (Numbers ending in 0, 2, 4, 6 or 8 can be divided by 2 and numbers ending in 5 can be divided by 5)
- If
*p*is a prime number and*p*divides a product*ab*of integers, then*p*divides*a*or*p*divides*b*. - If
*p*is prime and*a*is any integer, then*a*–^{p}*a*is divisible by*p.*This is knows as**Fermat’s Little theorem.** - If
*p*is a prime number other than 2 and 5, 1/p is always a recurring decimal, with a period of p–1 or a divisor of p−1. - An integer
*p*> 1 is prime if and only if the factorial (*p –*1)! + 1 is divisible by*p.*This is known as**Wilson’s theorem.***n*> 4 is composite if and only if (*n*− 1)! is divisible by*n*. - If
*n*is a positive integer greater than 1, then there is always a prime number*p*with*n*<*p*< 2*n*. - All the prime numbers P > 3 give a remainder 1 or 5 when divided by 6; that is, all the prime numbers > 3 will be of the format 6N ± 1. But vice versa is not always true.
- There is only one set of three prime numbers with a gap of 2 between two prime numbers and that set is 3, 5 and 7.

# Composite numbers

A number is composite if it is the product of two or more than two distinct or same prime numbers.
For example, → 4, 6, 8,…

4 = 2

^{2}6 = 2

^{1}× 3^{1}Lowest composite number is 4.