Prime number

From Wikipedia, the free encyclopedia
Jump to: navigation, search
Here is another way to think of prime numbers. The number 12 is not prime, because a rectangle can be made, with sides of lengths 4 and 3. This rectangle has an area of 12, because all 12 blocks are used. This cannot be done with 11. No matter how the rectangle is arranged, there will always be blocks left over. 11 must therefore be a prime number.

A prime number is a natural, whole number that has exactly two distinct whole numbers that divide it with no remainder. These divisors are the number itself and 1.

For example, 7 is a prime number, because the only numbers that divide it evenly are 1 and 7. 91 is not prime because 1, 7, 13, and 91 all divide it. 1 is not a prime number, since there is only one number that divides it with no leftover.

All natural numbers that are not prime are called composite numbers.

There is no biggest prime number, as there are infinitely many prime numbers. The way they are placed among all whole numbers is not understood very well, although mathematicians have some understanding of it. See the Prime number theorem.

How to find small prime numbers[change | edit source]

There is a simple method to find a list of prime numbers. It was created by Eratosthenes, and has the name Sieve of Eratosthenes, because it catches some numbers that are not prime (like a sieve) and the rest of them that can get through are prime:

  • On a sheet of paper, write all the whole numbers from 2 up to the number being tested. Do not write down the number 1, because it is not a prime number. 1 is not prime because it can be divided only by itself, and not by two different numbers.
  • At the start, all numbers are not crossed out.

The method is always the same:

  1. Start with 2.
  2. 2 is the first number on the sheet (one is not prime), so it must be prime.
  3. Cross out all multiples of the last prime number that was found. All numbers crossed out are composites (not prime), and do not need to be checked any further.
    The first time (2), cross out numbers 4, 6, 8, and so on. The second time (3), cross out numbers 6, 9, 12, and so on.
  4. Go back to the start of the list. The first number that is not crossed out is a prime number.
  5. Go on checking until there are no more numbers on the list. The numbers not crossed out are the prime numbers.

As an example, if this is done up to the number 10, the numbers 2, 3, 5 and 7 are prime numbers, and 4, 6, 8, 9 and 10 are composite numbers.

This method or algorithm takes too long to find very large prime numbers. But it is less complicated than methods used for very large primes, like Fermat's primality test (a primality test is to test whether a number is prime or not) or the Miller-Rabin primality test.

What prime numbers are used for[change | edit source]

Prime numbers are very important in mathematics and computer science. Some real-world uses are given below. Very big prime numbers are hard to find, so most of the time, numbers that are probably prime are used.[source?]

  • Most people have a bank card, where they can get money from their account, using an ATM. This card is protected by a secret access code. Since the code needs to be kept secret, it cannot be stored in cleartext on the card. Encryption is used to store the code in a secret way. This encryption uses multiplications, divisions, and finding remainders of large prime numbers. An algorithm called RSA is often used in practice. It uses the Chinese remainder theorem.
  • If someone has a digital signature for their email, encryption is used. This makes sure that no one can fake an email from them. Before signing, a hash value of the message is created. This is then combined with a digital signature to produce a signed message. Methods used are more or less the same as in the first case above.
  • Finding the largest prime known so far has become a sport of sorts. Testing if a number is prime can be difficult if the number is large. The largest primes known at any time are usually Mersenne primes because the fastest known test for primality is the Lucas-Lehmer test, which relies on the special form of Mersenne numbers. A group that searches for Mersenne primes is here[1].