A prime is an integer that has exactly 2 positive divisors.
This excludes 1 which is not prime, and which the definition of prime as "number divisible by itself and one" allows. 1 is not prime.

This also means -1 is not prime, since -1 does not have exactly two positive divisors. And, -3 is prime.

A prime number is a whole number that is divisible only by one and itself. 3 can is divisible by 1 and 3, and is prime. 6 is divisible by 1, 2, 3, and 6, and is not prime. 1 is not counted as prime, making 2 the first prime number, and the only even prime number.

Below is a brief list of prime numbers and their applications, as noded on E2. /msg me with any additions*.

---

up^

• The Very Basics
• Factor
• Prime
• No largest prime number - proof
• Prime decomposition (Fundamental theorem of arithmetic)
• 1 is prime, and, 1 is not prime
• Finding the Primes
• All primes greater than 3 are of the form 6k-1 or 6k+1
• Eratosthenes' Sieve
• Generalized Riemann Hypothesis
• Pi Function (Pi)
• Proth's Theorem
• Sierpinski number
• Sierpinski conjecture
• Seventeen or Bust
• Pseudoprime
• Riemann Hypothesis
• Sieve theory
• Found!
• Ten largest known primes
• Types of Primes
• Gaussian prime
• Irregular prime
• Mersenne prime
• Palindromic Prime
• Repunit prime
• Titanic prime
• Twin primes
• Weiferich Primes
• Working With Primes
• Brun's constant
• Cyclic numbers
• Euler Phi function
• Fermat's little theorem
• Proof of Fermat's little theorem
• Goldbach's conjecture
• How many primes are there?
• Odd Goldbach Problem
• Pi Function (Pi)
• Prime decomposition (Fundamental theorem of arithmetic)
• Prime ideal
• Prime number theorem
• Prime-valued polynomial
• Sum of the reciprocals of the primes
• Proof that the sum of the reciprocals of the primes diverges
• Small gaps between primes
• The smallest number that looks prime but isn't
  
• Misc.
• Anti-prime
• co-anti-prime
• Relatively prime, or Coprime
• And Even More Misc.
• Illegal prime number
• Prime number language
• Prime-o-matic
• Proof that all odd numbers are prime

---

* A lot of the mathematics that use prime numbers is far above my head; I'm trying to organize this information in an useful way; I am taking suggestions from people more knowledgeable than myself as to how this might be done.

Prime numbers were first studied extensively by ancient Greek mathematicians. The Pythagorean school (500 BC to 300 BC) where interested in the numerological properties. By Euclid's time (300 BC), several important results about primes had been proved. Euclid went on to prove that there are an infinite number of prime numbers. This proof is the first known one using the method of reduction to absurd. Euclid also proved the Fundamental Theorem of Arithmetic: Every integer can be written as a product of primes in an essentially unique way. In 200 BC, Eratosthanes devised an algorithm for calculating primes called the Sieve of Eratosthanes.

There is a great gap in the history of prime numbers during the Dark Ages.

The next major development was made by Fermat in the 17th Century. Fermat proved a speculation of Albert Girard that every prime of the form 4n + 1 can be written in a unique way as the sum of two squares, and any number could be written as the sum of four squares. In his corespondance with Mersenne, Fermat conjectured that 2ⁿ + 1 was always prime if n was a power of 2. He had verified this for n = 1, 2, 4, 8, and 16 but was did not know 2³²+1 was prime or not. 100 years later Euler showed that 2³² + 1 was 4294967297 and is divisible by 641, hence not prime.

The next major step in prime number theory came from a monk named Mersenne. Mersenne studied many numbers of the form 2ⁿ - 1 and a class of numbers named Mersenne numbers were named after him. These numbers attracted attention because it was easy to show that unless n was prime the number must be composite. Not all of these numbers are prime, though for many years (and again today) they provided the largest prime numbers. For 200 years M₁₉ was the largest known prime until Euler proved that M₃₁ is prime. This established the record for another 100 years until M₁₂₇ is prime until the age of the computer. In 1952 the Mersenne numbers M₅₂₁, M₆₀₇, M₁₂₇₉, M₂₂₀₃ and M₂₂₈₁ were proved to be prime with the aid of a computer.

Euler's work extended that of Fermat's working with amicable numbers and stated what is known today as the Law of Quadratic Reciprocity. Euler also worked with sequences of primes and divergent series.
1/2 + 1/3 + 1/5 + 1/7 + 1/11 + ...
is a divergent series, though even the most powerful computers today can only sum it to about 4.

Gauss studied the density of prime numbers along the integers. In the first 100 integers there are 9 primes, while the next 100 only has 2. Gauss showed that on a large scale, the distribution is very regular. Gauss once told a friend that whenever he had a spare 15 minutes he would spend it counting numbers in a 'chiliad' (a rage of 1000 numbers). It was estimated that by the end of his life he had counted all the primes up to about 3 million.

Today the counting of prime numbers continues, the most well known is GIMPS, The Great Internet Mersenne Prime Search.

The reason for not allowing 1 as prime is to keep the fundamental theorem of arithmetic. If you could say 24=2*2*2*3=1*1*1*1*2*2*2*3 were both decompositions of 24 into prime factors, the decomposition would not be unique.

Pakaran is incorrect regarding "prime" complex numbers. The integer ring of the algebraic numbers is the ring of gaussian integers -- numbers of the form a+bi with a,b both integers. In that ring, as Noether's excellent gaussian integers writeup shows, an integer p that is prime as an integer is prime iff it is not of the form 4k+1. When p=4k+1, Noether shows it is possible to write p = a²+b² = (a+bi)(a-bi), so p is not prime. But since the norm squared (absolute value) of a±bi is p, and since the norm squared of any gaussian integer is integer and multiplicative, it follows that a±bi itself is a prime gaussian integer.

Thus we can classify all prime gaussian integers.

Um, small writeup here, but all prime numbers other than 2 and 3 are one more or one less than a multiple of 6.

So if you're looking for prime numbers, or testing to see if a number is prime, knowing this cuts out 2/3 of the numbers for you.

---

Good point, Gritchka. ok, to show how this is useful:
finding the prime factors of a number:
(in C, to make my life easier)

void PrintFactors(int number) {
   int a,b,limit;

   while ((number%2)==0) printf("2*",number/=2);
   while ((number%3)==0) printf("3*",number/=3);

   a = 6-1;
   b = 6+1;

   limit = isqrt(number); /* integer square root */

   while (a < limit) {

      while ((number%a)==0) printf("%d*",a,number/=a);
      while ((number%b)==0) printf("%d*",b,number/=b);

      a += 6;  b += 6;
   }

   printf("%d",number);
}

(forgive my cheating with extra params for printf)
This should take about 2/3 as long as something that checked every odd number, or 1/3 as long as something that checked every integer.

Or if you're trying to do the Sieve of Eratosthanes for some reason, you can save time and memory by not representing other numbers at all. Have a table of all numbers that are 6n+1 and another for 6n-1.

The following was in response to rabidcow's first two paragraphs only; it is not a criticism of the C program added afterwards.

Um, I don't think that is as helpful as it would like to be. How do you know something is a multiple of 6? It has to be (a) a multiple of 2; (b) a multiple of 3.

To check (a) look at the last digit; to check (b) add up all the digits (repeatedly if necessary) to see whether their sum is divisible by 3. Both simple operations.

But any number is precisely one of

1. a multiple of 6
2. 1 more than a multiple of 6
3. 2 more than a multiple of 6
4. 3 more than a multiple of 6
5. 4 more than a multiple of 6
6. 5 more than a multiple of 6

These can be checked with

1. either (a) or (b), but (a) is easier
2. neither
3. (a)
4. (b)
5. (a)
6. neither

Being 5 more than is the same as being 1 less than (modulo 6), so this leaves the two possibilities rabidcow mentioned. But in no case do you have to do the (relatively) hard work of checking both (a) and (b). The o(1) algorithm (a) eliminates half and the o(n) algorithm (b) eliminates a further one-sixth.

If it's still a candidate after this you have to do work, but its passing these tests has incidentally told you that it's a multiple of 6, plus or minus 1, a converse of the previous write-up's idea.

Here is the proof of two statements above. Just in case someone is interested.

It is easy to prove that the set of all prime numbers is infinite(more precisely - there is no greatest prime number). Here is how.

Let the set be finite and consist of {n1,n2,...nk} Where nk is the largest prime number.
Then the number n1*n2*n3.....nk+1 does not belong to the above set. Also it is not divisible by either n1 or n2 or n3 ... or nk. So either it is prime or it has a prime factor larger than nk. In either case, we have found a prime number greater than nk. This contradicts the assumption that nk was the largest prime number. So the assumption is false and there is no largest prime.

The second statement about all primes except for 2 and 3 being either 1 less or one more than 6. Here is why this is true.

Any positive natural number may be written in the form 6n+k. Where n is a natural number and k is one of {0,1,2,3,4,5}. A prime number cannot have k = 0 or k = 2 or k=4 because in all these cases, the number would be divisible by 2. It cannot have k = 3 because in this case it would be divisible by 3 as 6n+3 = 3*(2n+1). Thus it must be of the form 6n+1 or 6n+5=6(n+1)-1. So it must be one more or one less than a multiple of 6.

If you take any two prime numbers above 3 and square them, the difference between them is always divisible by 24.

This is an observation i made one night while trying to go to sleep. I later checked my theory with all of the prime numbers from 5 to 101 and it worked. I'm afraid i don't know enough math to write this as a proof. I was looking for some kind of connection between the primes, and squared them as a means of finding that connection. I soon noticed that the differences between the squared primes was always divisible by 8, and later, 3 as well (thus 24).

Definition: A number n in the natural numbers is composite iff there exists a number 1 < k < n in the naturals such that k|n. (The "|" symbol means "divides".)

From the definition of 'divides', for numbers a,b in the naturals, a|b iff there exists a number c in the integers such that a*c=b.

In other words, n is composite iff there exist naturals 1 < k < n and x such that k * x = n.

The inverse: A number n in the naturals is prime iff for all 1 < k < n and x in the naturals, k*x != n. (!= is "does not equal".)

Extension: 1 < k < n, so k=2,3,4,...,n-1. Consider 2 to be 'already' prime, so all numbers k = 2*g for g in the naturals are not prime. Also, consider 3 to be 'already' prime, so all k=3*h for h in the naturals are not prime. So, ignore k=2,3,4,6,8,9,10,..., i.e. let k=6*u±1 for u in the naturals; let n and x be of this form as well, so n=6*m±1 and x=6*v±1 for m, v in the naturals.

Now the number of tests required for primality are reduced by a factor of 3. To test if n is prime, look for any k,x for which k*x=n, or test the equations 6*m±1=(6*u±1)*(6*v±1) for any solutions. Keep in mind that 6*m+1 is a separate case from 6*m-1, but all of 6*u+1, 6*u-1, 6*v+1 and 6*v-1 must be tested.

Distributing the above multiplication yields

6*m±1=36*u*v±6*u±6*v±1

Some manipulation and mod operations reduce this to:

m=6*u*v±u±v

A little more work yields some insight as to some of the larger implications of this equation. One thing in particular is that, if there are *no* u and v in the naturals to satisfy the above equations, then 6*m+1 and 6*m-1 are prime.

---

Some prime curios:

1234567891 is prime. In fact, so is 12345678901234567891. Both of these may be checked with primo in a very short amount of time. Another interesting prime: (37)₁₄₄₁3. That's right: write '37' 1441 times in a row next to each other, then put a 3 on the end and you have a prime. I have seen some conflicting reports, but currently (2^24,036,583)-1 is the largest prime known to date that I can confirm. In terms of digits, this is roughly 7 million decimal digits.

The primes below 1000 are as follows:

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, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997

A proof of lisapple's unproven statement:

For every prime > 3 (by the above logic), there exists a number n such that said prime is equal to either b or c, where:

b = 6n+1, c = 6n-1.

Therefore:

b^2 = 36n^2+12n+1
c^2 = 36n^2-12n+1
The difference between any two primes >3, therefore, are equal to:

(b1)^2-(b2)^2 = 36n^2 - 36m^2 +12n - 12m = 12 (3n^2 - 3m^2 + n - m).
The value in the parentheses is even for all integer values of m and n.
Therefore, there exists a number L such that (a1)^2 - (a2)^2 = 24L.
And 24 divides 24L.

The other cases are solvable by similar logic.
Q.E.D.