A natural number (i.e. 1, 2, 3, 4, 5, 6, etc.) is called a prime number (or a prime) if it has exactly two positive divisors, 1 and the number itself. Natural numbers greater than 1 that are not prime are called composite.
Among the numbers 1 to 6, the numbers 2, 3, and 5 are the prime numbers, while 1, 4, and 6 are not prime. 1 is excluded as a prime number.. 2 is a prime number, since the only natural numbers dividing it are 1 and 2. Next, 3 is prime, too: 1 and 3 do divide 3 without remainder, but 3 divided by 2 gives remainder 1. Thus, 3 is prime. However, 4 is composite, since 2 is another number (in addition to 1 and 4) dividing 4 without remainder:
4 = 2 · 2.
5 is again prime: none of the numbers 2, 3, or 4 divide 5. Next, 6 is divisible by 2 or 3, since
6 = 2 · 3. Hence, 6 is not prime. No even number greater than 2 is prime because by definition, any such number n has at least three distinct divisors, namely 1, 2, and n.
If n is a natural number, then 1 and n divide n without remainder. Therefore, the condition of being a prime can also be restated as: a number is prime if it is greater than one and if none of
- 2, 3, …, n − 1
divides n (without remainder). Yet another way to say the same is: a number n > 1 is prime if it cannot be written as a product of two integers a and b, both of which are larger than 1:
- n = a · b.
In other words, n is prime if n items cannot be divided up into smaller equal-size groups of more than one item.
The set of all primes is often denoted by P.
All the prime numbers less than 100 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. There are infintely many prime numbers.
Applications of prime numbers
For a long time, number theory in general, and the study of prime numbers in particular, was seen as the canonical example of pure mathematics, with no applications outside of the self-interest of studying the topic with the exception of use of prime numbered gear teeth to distribute wear evenly. When it was publicly announced that prime numbers could be used as the basis for the creation of Public key cryptography algorithms. Prime numbers are also used for hash tables and pseudorandom number generators.
Some rotor machines were designed with a different number of pins on each rotor, with the number of pins on any one rotor either prime, or coprime to the number of pins on any other rotor. This helped generate the full cycle of possible rotor positions before repeating any position.