Prime number

From Simple English Wikipedia, the free encyclopedia

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 leftover). 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.

[edit] How to find (small) prime numbers

There is a method to check if a number N is a prime number or not. The following method was devised 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.
• At the start, all numbers are not crossed out.

The method is always the same:

1. Start (with 2).

2. Two is the first number on the sheet (one is not prime), so it must be prime.

Now repeat the following step:

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. Go back to the start of the list, the first number that is not crossed out is a prime number.

The method ends like this:

4. Go on checking, until there are no more numbers on the list. The numbers not crossed out are the prime numbers. When the number is reached that is 1 higher than the square root of the number N that is checked, you can stop.

If this is done up to the number 10, you find that 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.

[edit] What prime numbers are used for

Prime numbers are very important in mathematics and computer science, so 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 modulo-calculus of large prime numbers.

• If you have a valid digital signature for your email, that is to digitally-sign emails, encryption is also used there. Before signing, a hash value of the message, like extracting the gist of it, is generated. This is then mangled together with your 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.