Prime number

From the Simple English Wikipedia, the free encyclopedia that anyone can change

A prime number is a positive, whole number that is special in some ways. For a prime number, there are exactly two other whole numbers that divide it (with no remainder). These divisors are the number itself, and 1. No other numbers will divide it exactly.

For example, 7 is a prime number, because the only numbers that divide it evenly are 1 and 7.

1 is not a prime number, since there is only one number that divides it with no leftover. 0 is not a prime number, since divide by zero cannot be done.

All other positive numbers are called composite numbers, because other whole numbers can be multiplied to produce these numbers.

[change] How to find (small) prime numbers

There is a simple method to find a list of prime numbers. It was created by Eratosthenes, and has the name Sieve of Eratosthenes:

• 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 or the Miller-Rabin primality test.

[change] What prime numbers are used for

Prime numbers are very important in mathematics and computer science. Some real-world uses are given below.

• Most people have a bank card, where they can get money from they 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 clear-text 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.

• 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 a number can be done quite simply. The largest primes known at any time are usually Mersenne primes.