Friday

September 4, 2015
Posted by **sara** on Wednesday, November 29, 2006 at 12:36pm.

Here is a site that I found searching Google with the key words, "

http://mathforum.org/dr.math/faq/faq.prime.num.html

I hope this helps. Thanks for asking.

Finding Primes

The Sieve of Eratosthenes

Lets find the primes between 1 and 100.

Write down the sequence of numbers from 1 to 100.

Cross out the 1.

Beginning with the 2, strike out every second number beyond the 2, i.e., 4, 6, 8, 10, etc.

Starting from the first remaining number, 3, cross out every third number beyond the 3, i.e., 3, 6, 9, 12, etc.

Starting from the first remaining number, 5, cross out every fifth number beyond the 5, i.e., 5, 10, 15, 20, etc.

Continue with the 7, crossing out every seventh number beyond the 7, i.e., 7, 14, 21, 28, etc.

Continue the process until you have reached N or 100.

The numbers remaining are the primes between 1 and 100, namely 2, 3, 5, 7, 11, 13,17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, and 97. By definition, all the others are composite numbers

* The Fundamental Theorem of Arithmetic states that every positive integer/number greater than 1 is either prime or composite and can be written uniquely as a product of primes, with the prime factors in the product written in order of nondecreasing size.

* A prime number is a positive number "p" that has but two positive divisors/factors, 1 and "p".

(The strict interpretation of this definition aids in supporting the statement that the number one is not a prime number as it literally has only one divisor/factor whereas a prime has two factors.)

Examples: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, etc., are all primes, being evenly divisible by only 1 and the number itself.

* A composite number is therefore any number that has 3 or more factors/divisors.

* The number 1 is not considered a prime number, being more traditionally referred to as the unit.

Aristotle regarded the one as not being a number but rather the elemental measure, or building block, of all numbers.

Euclid stated that a unit is that property of each and every thing in the universe that enables it to be called one, while a number can be considered a multitude of units.

Thymaridas called the unit the limiting quantity or limit of fewness.

Some ealy definitions of number were

......-- a collection of units

......-- a progression of multitude starting with the unit

......-- a determinate multitude

......-- limited multitude

......-- a multitude of units

......-- several ones

......-- a multitude measureable by one

Every number N contains N ones or units.

* A composite number is expressable as a unique product of prime numbers and their exponents, in only one way.

Examples: 210 = 2x3x5x7; 495 = 3^2x5x11.

* A prime factor of a number is a divisor/factor of the number which also happens to be a prime number. The factors of 36 are 1, 2, 3, 4, 6, 9, 12, 18 and 36 but only 2 and 3 are prime factors.

* The number 1 is the only number that is a factor of all other numbers.

* Any number that can be expressed as the product of two or more primes and their powers, i.e., ab, abc, ab^2c, ab^2c^3d^2, etc., where a, b, c and d are prime numbers, is composite.

* Any number greater than 1 that is not a prime number must be a composite number, and is the result of multiplying primes together.

Examples: 4, 6, 12, 24, 72, etc., are composite, each being divisible by lower prime numbers.

* Every number n > 1 is divisible by some prime.

* With the exception of the number 2, all prime numbers are odd numbers.

The number 2 is the only even prime, thereby making it the oddest prime.

* All prime numbers of two digits or more end in 1, 3, 7, or 9.

Caution: There are numbers that end in 1, 3, 7, or 9 that are not prime but, in order to be a prime, it must end in 1, 3, 7, or 9.

* Two integers are said to be relatively prime, or prime to each other, if their greatest common divisor is 1.

Examples: 7 and 12 are relatively prime as their g.c.d. is 1 or (7,12) = 1.

* A semi-prime number is one that has exactly two prime factors in addition to the factors of one and the number itself. For example, 14, 15, 21, 39, 142, 143, etc. are semi-prime numbers. By definition, such numbers are also classified as composite numbers.

* Primes differing by 2 are called twin primes.

Examples: 3-5, 5-7, 11-13, 17-19, 29-31, 41-43, 59-61, 71-73, 101-103, 1,000,000,009,649-1,000,000,009,651.

* The sums of all pairs of twin primes (except 3-5) are divisible by 12.

* There is only one set of triple primes - 3, 5, and 7.

* With the exception of 2, all primes are odd numbers.

* Every odd number is congruent to either 1 or 3 modulo(4) meaning that every odd number minus 1 or 3 is divisible by 4.

* Every prime number is congruent to one of 1, 2, 3 or 4 modulo(5).

* There are infinitely many primes of the form N^2 + 1. If of the form N^2 + 1, it does not mean it is automatically prime. Primes of the form N^2 + 1 are either prime or the product of two primes.

* Every prime of the form 4n + 1 can be written as the sum of two squares, 5, 13, 17, 29, 37, 41, 53, etc.

* No primes of the form 4n - 1 can be written as the sum of two squares, 3, 7, 11, 43, 47, 59, 67, etc.

* The number 17 is the only prime that is equal to the sum of the digits of its cube.

* A prime p is the sum of two squares if, and only if, p + 1 is not divisible by 4.

The Sieve of Sundaram

Given the infinite table of p rows and q columns.

.4....7....10...13...16...19...22...25....28....52...57...etc. constant 3 difference .7...12...17...22...27...32...37...42....47....52...57...etc constant 5 difference

10..17...24...31...38...45...52...59....66....73...80...etc. constant 7 difference

13..22...31...40...49...58...67...76....85....94..103..etc. constant 9 difference

16..27...38...49...60...71...82...93...104..115..126..etc. constant 11 difference

19..32...45...58...71...84...97..110..123..136..149..etc constant 13 difference

Required to determine if the number N is prime or composite.

Let k = (N - 1)/2

If the value of k is found in the table, N is composite.

If the value of k is not found in the table, N is prime.

The 1st number in the pth row is given by 3p + 1

The successive difference in each row is given by 2n + 1

The qth number in the pth row is there defined as (2q + 1)p + q

Therefore, if values of p and q can be found to make (2q + 1)p + q = k, N is not a prime.

* One way to determine whether a number N is prime is to divide it by all the primes less than sqrt(N). It would not be necessary to divide by primes greater than sqrt(N) as this would produce numbers that were already covered in the array of numbers less than srt(N). It would appear that this method is relatively simple, and so it is, for relatively small numbers. Large numbers however would require many tiresome calculations either by hand or with a calculator.

* Wilson's Theorem

Wilson's Theorem stated that for every prime number "p", [(p + 1)! + 1] is evenly divisible by "p". The converse was shown to also be true in that every integer "n" that evenly divides [(n + 1)! + 1] is prime. Combining these leads to the famous general theorem that a necessary and sufficient condition that an integer "n" be prime is that "n" evenly divide [(n + 1)! + 1].

Example: For N = 5, (5 - 1)! + 1 = 24 + 1 = 25 is divisible by 5. For N = 11, (11 - 1)! + 1 = 3,628,000 + 1 = 3,628,001 is divisible by 11. On the other hand, for N = 12, (12 - 1)! + 1 = 39,916,800 + 1 = 39,916,801 is not divisible by 12.

* Fermat's Theorem

Fermat's Little Theorem stated that if "a" is any whole number and "p" is a prime number relatively prime to "a", then "p" divides [a^(p-1) - 1]. A corollary to this is if "p" is any prime number and "a" is any whole number, then "p" divides [a^p - a]. With p = 7 and a = 12, the theorem tells us that 7 divides [12^6 - 1] = 2,985,983 which it does, yielding 426,569. Similarly, 7 divides [12^7 - 12] = 35,831,796 yielding 5,118,828. Trying p = 8 and a = 12, we get [12^7 - 1]/7 = 4,478,975.875, confirming that 8 is not prime.

As with Wilson's theorem, it was logically asked if the converse of Fermat's Theorem was also true, i.e., is every integer "n" that evenly divides [a^(p-1) - 1] or [2^n - 2] a prime? This was pursued by Chinese mathematicians in exploring if "n" divides [2^(n-1) - 1], is "n" prime? They initially concluded that "n" would be prime if it divided [2^(n-1) - 1] but were later proven wrong when it was discovered that while the number 341 did evenly divide [2^340 - 1], 341 was itself composite, being equal to 11 times 31. There are supposedly an infinite number of composite numbers, "n", both odd and even, that divide (2^n - 2). They are referred to as pseudoprimes. When it was discovered that there were composite numbers that divided all (a^n - a), they were called absolute pseudoprimes. The smallest of the absolute pseudoprimes is 561.

* The square root of any prime number is an irrational number.

* If a natural number N has a prime factorization where each prime appears an even number of times, the number N is a perfect square and sqrt(N) is a rational number.

* If a natural number N has a prime factorization where at least one prime appears an odd number of times, the square root of N is irrational.

* Goldbach's Conjecture - Every even number is the sum of two prime numbers. No proof exists.

* A prime "p" is either relatively prime to a number "n" or divides it.

* A product is divisible by a prime "p" only when "p" divides one of the factors.

* A product q1xq2x.....qr of prime factors qi is divisible by a prime "p "only when "p" is equal to one of the qi's.

* The number 5 is the only prime that is both the sum and difference of two primes.

* All primes other than 2 are of the form 4x + 1 or 4x - 1.

* All odd primes can be expressed as the difference of two squares in only one way.

Set the two factors of the prime p equal to (x + y) and (x - y) and solve for x and y. Then, x^2 - y^2 = p.

Example: Using the prime 37, (x + y) = 37 and (x - y) = 1. Adding, 2x = 39 or x = 19 making y = 18. Thus, 19^2 - 18^2 = 361 - 324 = 37.

* Primes of the form 4x + 1 can be expressed as the sum of two squares in one way only.

Therefore, any prime that exceeds a multiple of 4 by 1 is the hypotenuse of only one right triangle.

* Primes of the form 4x - 1 cannot be expressed as the sum of two squares in any way.

* Primes of the form Mp = 2^p - 1 are called Mersenne primes where the exponent "p" is itself a prime. Mersenne primes contribute to the derivation of perfect numbers. A perfect number is one that is equal to the sum of its aliquot divisors, i.e., all its divisors except the number itself. (It is also said that a number is perfect if the sum of all its divisors, including the number itself, is equal to twice the number.) Numbers of the form 2^(p-1)[2^p - 1] are perfect when (2^p - 1) is a prime. For example, the primes 2, 3, 5, 7, 13, etc., lead to the Mersenne primes of 3, 7, 31, 127, 8191, etc., and the corresponding perfect numbers of 6, 28, 496, 8128, 33,550,336, etc. There are no odd perfect numbers, or rather, none have been discovered to date.

* The 35th Mersenne Prime, was discovered in late 1996, being 2^1,398,269 - 1 and having 420,921 digits.

On January 27, 1998, the largest known prime was [2^(3,021,377) - 1] having 909,526 digits.

* When a product ac is divisible by a number b that is relatively prime to a, the factor c must be divisible by b.

* When a number is relatively prime to each of several numbers, it is relatively prime to their product.

* Pierre de Fermat once hypothesized that all numbers of the form F(n) = [2^(2^n)] + 1 were primes. This worked for n = 1, 2, 3, and 4 but Euler discovered in 1732 that [2^(2^5) + 1] = 4,294,967,297 = 6,700,416x641.

* Marin Mersenne hypothesized that Mersenne numbers of the form Mp = 2^p - 1, p a prime number, were prime for a select group of primes. In 1947, an electronic computer showed that some were composite and discovered others that were prime. When "p" is not a prime, the Mersenne numbers are composite. Those that were confirmed as primes and all derived since are now referred to as Mersenne Primes. There are relatively few Mersenne Primes. One discovered in 1997 had a p = 2,976,221 with 895,932 digits. The 35th Mersenne Prime was discovered in late 1996, being 2^1,398,269 - 1 and having 420,921 digits.

The largest prime discovered as of June 1, 1999 is 2^6,972,593 - 1. Mersenne Primes contribute to the derivation of Perfect Numbers.

* There are many formulas that yield primes but not all primes. The most misleading is x^2 - x + 41 which works

fine up to x = 39 but breaks down for x = 40 and beyond. Others are 2x^2 - 199, x^2 + x + 11, x^2 + x + 17, x^2 - 79x + 1601, 6x^2 + 6x + 31, x^3 + x^2 - 349, to name a few. There are none that derive all the primes.

* There are an infinite number of Primes

Proof:

From Euclid's Elements (Proposition 20, Book IX)

Assume that p1, p2, p3, ......pn is a finite set of prime numbers.

Create the product P = p1(p2)p3.......(pn) and add 1.

P + 1 forms a new number which is not divisible by any of the given set of primes and must therefore itself be a prime or it contains as a factor a prime differing from those already defined.

If P + 1 is prime, then it is clearly a new prime not of the original set of primes.

If P + 1 is not prime, it must be divisible by some prime q.

However, q cannot be identical to any of the given prime numbers, p1, p2, p3,......pn, as it would then divide both P and P + 1 and consequently, their difference = 1.

However, q must be at least 2 and cannot therefore divide evenly into 1.

Therefore, q, being different from all the given primes, must be a new prime.

Caution: Care must be taken to realize that p1(p2)p3.......(pn) + 1 will not always produce a new prime and if it does, it is not necessarily the next prime.

Examples:

2x3 + 1 = 7 = a prime

2x3x5 + 1 = 31 = a prime

2x3x5x + 1 = 211 = a prime

2x3x5x7x11 + 1 = 2311 = a prime

2x3x5x7x11x13 + 1 = 30,031 = 59x509

* There are an infinite number of primes.

Euclid's proof: Is there a prime greater than N? Derive the quantity N! + 1, N factorial plus one. (N! + 1) is therefore not divisible by any number up to, and including, N, as there is always a remainder of 1. If (N! + 1) is prime, it has no factors other than 1 and itself; if it is not prime, it has factors in addition to 1 and itself.

* While the number of primes is infinite, they become fewer and fewer as the natural numbers approach infinity. For example, the number of primes, p(n) within the first n numbers and their ratio looks like the following:

..n..............p(n)..............p(n)/n........Difference 10^n - 10^(n-1)

10^2............25................(.25)

10^3...........168..............(.168).......................143/900

10^4..........1,229...........(.1229)......................1061/9000

10^5..........9,593..........(.09593).....................8364/90,000

10^6.........78,499........(.078499)..................68,906/900,000

19^7........664,579......(.0664579)................586,080/9,000,000

10^8.......5,761,455...(.057614550)............5,096,876/90,000,000

* As the number of primes decrease and the distance between primes increases, the corresponding sets of consecutive composite numbers become longer. Within the first 100 numbers, there are seven composite numbers between 89 and 97. Within the numbers from 1 to 1000, there are 19 composite numbers between 887 and 907. To define N consecutive composite numbers, you need only compute the numbers (N + 1)! + 2, (N + 1)! + 3, (N + 1)! + 4, (N + 1)! + 5,..... .....(N + 1)! + (N + 1), all being composite.

* Primes can be in arithmetic progression, for example:

7-37-67-97-127-157, 107-137-167-197-227-257, 199-409-619-829-1039-1249-1459-1669-1879-2089.

* There are an infinite number of palindromic primes such as 101, 131, 151, 181, 313, 353, 727, 757, 797, 919,

79997, 91019, 3535353, etc.

* Primes can be both palindromic and in arithmetic progression such as in

13931-14741-15551-16361, 10301-13331-16361-19391 and 94049-94349-94649-94949.

* Unproven hypotheses concerning primes:

Every even number =/> 6 is the sum of two primes.

Every odd number =/> 9 is the sum of three odd primes.

Every even number is the difference between two primes in an infinite number of ways.

Every number is the difference of two consecutive primes in an infinite number of ways.

Every odd number is either a prime or the sum of a prime and twice a square.

Primes can be expressed as the sum of a prime and twice a square.

Every odd number is the sum of a prime and a power of 2.

(Remember - all unproved)

* Goldbach's Conjecture - Every even number is the sum of two prime numbers. No proof exists

* Any positive integer can be written as the product of primes in only one way.

Example: 42 = 2x3x7, 67 = 1x67, 96 = 3x2^5, 52 = 13x2^2.

* Using the digits 1 through 9 only once, form prime numbers the sum of which is a minimum.

2 + 3 + 5 + 41 + 67 + 89 = 207.

Perform the same thing using the digits 0 through 9.

2 + 5 + 7 + 63 + 89 + 401 = 567.

* The squares of the first 7 primes, 2^2 + 3^2 + 5^2 + 7^2 + 11^2 + 13^2 + 17^2, add up to 666, the devil

number.

Finding Primes

The Sieve of Eratosthenes

Lets find the primes between 1 and 100.

Write down the sequence of numbers from 1 to 100.

Cross out the 1.

Beginning with the 2, strike out every second number beyond the 2, i.e., 4, 6, 8, 10, etc.

Starting from the first remaining number, 3, cross out every third number beyond the 3, i.e., 3, 6, 9, 12, etc.

Starting from the first remaining number, 5, cross out every fifth number beyond the 5, i.e., 5, 10, 15, 20, etc.

Continue with the 7, crossing out every seventh number beyond the 7, i.e., 7, 14, 21, 28, etc.

Continue the process until you have reached N or 100.

The numbers remaining are the primes between 1 and 100, namely 2, 3, 5, 7, 11, 13,17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, and 97. By definition, all the others are composite numbers

* The Fundamental Theorem of Arithmetic states that every positive integer/number greater than 1 is either prime or composite and can be written uniquely as a product of primes, with the prime factors in the product written in order of nondecreasing size.

* A prime number is a positive number "p" that has but two positive divisors/factors, 1 and "p".

(The strict interpretation of this definition aids in supporting the statement that the number one is not a prime number as it literally has only one divisor/factor whereas a prime has two factors.)

Examples: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, etc., are all primes, being evenly divisible by only 1 and the number itself.

* A composite number is therefore any number that has 3 or more factors/divisors.

* The number 1 is not considered a prime number, being more traditionally referred to as the unit.

Aristotle regarded the one as not being a number but rather the elemental measure, or building block, of all numbers.

Euclid stated that a unit is that property of each and every thing in the universe that enables it to be called one, while a number can be considered a multitude of units.

Thymaridas called the unit the limiting quantity or limit of fewness.

Some ealy definitions of number were

......-- a collection of units

......-- a progression of multitude starting with the unit

......-- a determinate multitude

......-- limited multitude

......-- a multitude of units

......-- several ones

......-- a multitude measureable by one

Every number N contains N ones or units.

* A composite number is expressable as a unique product of prime numbers and their exponents, in only one way.

Examples: 210 = 2x3x5x7; 495 = 3^2x5x11.

* A prime factor of a number is a divisor/factor of the number which also happens to be a prime number. The factors of 36 are 1, 2, 3, 4, 6, 9, 12, 18 and 36 but only 2 and 3 are prime factors.

* The number 1 is the only number that is a factor of all other numbers.

* Any number that can be expressed as the product of two or more primes and their powers, i.e., ab, abc, ab^2c, ab^2c^3d^2, etc., where a, b, c and d are prime numbers, is composite.

* Any number greater than 1 that is not a prime number must be a composite number, and is the result of multiplying primes together.

Examples: 4, 6, 12, 24, 72, etc., are composite, each being divisible by lower prime numbers.

* Every number n > 1 is divisible by some prime.

* With the exception of the number 2, all prime numbers are odd numbers.

The number 2 is the only even prime, thereby making it the oddest prime.

* All prime numbers of two digits or more end in 1, 3, 7, or 9.

Caution: There are numbers that end in 1, 3, 7, or 9 that are not prime but, in order to be a prime, it must end in 1, 3, 7, or 9.

* Two integers are said to be relatively prime, or prime to each other, if their greatest common divisor is 1.

Examples: 7 and 12 are relatively prime as their g.c.d. is 1 or (7,12) = 1.

* A semi-prime number is one that has exactly two prime factors in addition to the factors of one and the number itself. For example, 14, 15, 21, 39, 142, 143, etc. are semi-prime numbers. By definition, such numbers are also classified as composite numbers.

* Primes differing by 2 are called twin primes.

Examples: 3-5, 5-7, 11-13, 17-19, 29-31, 41-43, 59-61, 71-73, 101-103, 1,000,000,009,649-1,000,000,009,651.

* The sums of all pairs of twin primes (except 3-5) are divisible by 12.

* There is only one set of triple primes - 3, 5, and 7.

* With the exception of 2, all primes are odd numbers.

* Every odd number is congruent to either 1 or 3 modulo(4) meaning that every odd number minus 1 or 3 is divisible by 4.

* Every prime number is congruent to one of 1, 2, 3 or 4 modulo(5).

* There are infinitely many primes of the form N^2 + 1. If of the form N^2 + 1, it does not mean it is automatically prime. Primes of the form N^2 + 1 are either prime or the product of two primes.

* Every prime of the form 4n + 1 can be written as the sum of two squares, 5, 13, 17, 29, 37, 41, 53, etc.

* No primes of the form 4n - 1 can be written as the sum of two squares, 3, 7, 11, 43, 47, 59, 67, etc.

* The number 17 is the only prime that is equal to the sum of the digits of its cube.

* A prime p is the sum of two squares if, and only if, p + 1 is not divisible by 4.

The Sieve of Sundaram

Given the infinite table of p rows and q columns.

.4....7....10...13...16...19...22...25....28....52...57...etc. constant 3 difference .7...12...17...22...27...32...37...42....47....52...57...etc constant 5 difference

10..17...24...31...38...45...52...59....66....73...80...etc. constant 7 difference

13..22...31...40...49...58...67...76....85....94..103..etc. constant 9 difference

16..27...38...49...60...71...82...93...104..115..126..etc. constant 11 difference

19..32...45...58...71...84...97..110..123..136..149..etc constant 13 difference

Required to determine if the number N is prime or composite.

Let k = (N - 1)/2

If the value of k is found in the table, N is composite.

If the value of k is not found in the table, N is prime.

The 1st number in the pth row is given by 3p + 1

The successive difference in each row is given by 2n + 1

The qth number in the pth row is there defined as (2q + 1)p + q

Therefore, if values of p and q can be found to make (2q + 1)p + q = k, N is not a prime.

* One way to determine whether a number N is prime is to divide it by all the primes less than sqrt(N). It would not be necessary to divide by primes greater than sqrt(N) as this would produce numbers that were already covered in the array of numbers less than srt(N). It would appear that this method is relatively simple, and so it is, for relatively small numbers. Large numbers however would require many tiresome calculations either by hand or with a calculator.

* Wilson's Theorem

Wilson's Theorem stated that for every prime number "p", [(p + 1)! + 1] is evenly divisible by "p". The converse was shown to also be true in that every integer "n" that evenly divides [(n + 1)! + 1] is prime. Combining these leads to the famous general theorem that a necessary and sufficient condition that an integer "n" be prime is that "n" evenly divide [(n + 1)! + 1].

Example: For N = 5, (5 - 1)! + 1 = 24 + 1 = 25 is divisible by 5. For N = 11, (11 - 1)! + 1 = 3,628,000 + 1 = 3,628,001 is divisible by 11. On the other hand, for N = 12, (12 - 1)! + 1 = 39,916,800 + 1 = 39,916,801 is not divisible by 12.

* Fermat's Theorem

Fermat's Little Theorem stated that if "a" is any whole number and "p" is a prime number relatively prime to "a", then "p" divides [a^(p-1) - 1]. A corollary to this is if "p" is any prime number and "a" is any whole number, then "p" divides [a^p - a]. With p = 7 and a = 12, the theorem tells us that 7 divides [12^6 - 1] = 2,985,983 which it does, yielding 426,569. Similarly, 7 divides [12^7 - 12] = 35,831,796 yielding 5,118,828. Trying p = 8 and a = 12, we get [12^7 - 1]/7 = 4,478,975.875, confirming that 8 is not prime.

As with Wilson's theorem, it was logically asked if the converse of Fermat's Theorem was also true, i.e., is every integer "n" that evenly divides [a^(p-1) - 1] or [2^n - 2] a prime? This was pursued by Chinese mathematicians in exploring if "n" divides [2^(n-1) - 1], is "n" prime? They initially concluded that "n" would be prime if it divided [2^(n-1) - 1] but were later proven wrong when it was discovered that while the number 341 did evenly divide [2^340 - 1], 341 was itself composite, being equal to 11 times 31. There are supposedly an infinite number of composite numbers, "n", both odd and even, that divide (2^n - 2). They are referred to as pseudoprimes. When it was discovered that there were composite numbers that divided all (a^n - a), they were called absolute pseudoprimes. The smallest of the absolute pseudoprimes is 561.

* The square root of any prime number is an irrational number.

* If a natural number N has a prime factorization where each prime appears an even number of times, the number N is a perfect square and sqrt(N) is a rational number.

* If a natural number N has a prime factorization where at least one prime appears an odd number of times, the square root of N is irrational.

* Goldbach's Conjecture - Every even number is the sum of two prime numbers. No proof exists.

* A prime "p" is either relatively prime to a number "n" or divides it.

* A product is divisible by a prime "p" only when "p" divides one of the factors.

* A product q1xq2x.....qr of prime factors qi is divisible by a prime "p "only when "p" is equal to one of the qi's.

* The number 5 is the only prime that is both the sum and difference of two primes.

* All primes other than 2 are of the form 4x + 1 or 4x - 1.

* All odd primes can be expressed as the difference of two squares in only one way.

Set the two factors of the prime p equal to (x + y) and (x - y) and solve for x and y. Then, x^2 - y^2 = p.

Example: Using the prime 37, (x + y) = 37 and (x - y) = 1. Adding, 2x = 39 or x = 19 making y = 18. Thus, 19^2 - 18^2 = 361 - 324 = 37.

* Primes of the form 4x + 1 can be expressed as the sum of two squares in one way only.

Therefore, any prime that exceeds a multiple of 4 by 1 is the hypotenuse of only one right triangle.

* Primes of the form 4x - 1 cannot be expressed as the sum of two squares in any way.

* Primes of the form Mp = 2^p - 1 are called Mersenne primes where the exponent "p" is itself a prime. Mersenne primes contribute to the derivation of perfect numbers. A perfect number is one that is equal to the sum of its aliquot divisors, i.e., all its divisors except the number itself. (It is also said that a number is perfect if the sum of all its divisors, including the number itself, is equal to twice the number.) Numbers of the form 2^(p-1)[2^p - 1] are perfect when (2^p - 1) is a prime. For example, the primes 2, 3, 5, 7, 13, etc., lead to the Mersenne primes of 3, 7, 31, 127, 8191, etc., and the corresponding perfect numbers of 6, 28, 496, 8128, 33,550,336, etc. There are no odd perfect numbers, or rather, none have been discovered to date.

* The 35th Mersenne Prime, was discovered in late 1996, being 2^1,398,269 - 1 and having 420,921 digits.

On January 27, 1998, the largest known prime was [2^(3,021,377) - 1] having 909,526 digits.

* When a product ac is divisible by a number b that is relatively prime to a, the factor c must be divisible by b.

* When a number is relatively prime to each of several numbers, it is relatively prime to their product.

* Pierre de Fermat once hypothesized that all numbers of the form F(n) = [2^(2^n)] + 1 were primes. This worked for n = 1, 2, 3, and 4 but Euler discovered in 1732 that [2^(2^5) + 1] = 4,294,967,297 = 6,700,416x641.

* Marin Mersenne hypothesized that Mersenne numbers of the form Mp = 2^p - 1, p a prime number, were prime for a select group of primes. In 1947, an electronic computer showed that some were composite and discovered others that were prime. When "p" is not a prime, the Mersenne numbers are composite. Those that were confirmed as primes and all derived since are now referred to as Mersenne Primes. There are relatively few Mersenne Primes. One discovered in 1997 had a p = 2,976,221 with 895,932 digits. The 35th Mersenne Prime was discovered in late 1996, being 2^1,398,269 - 1 and having 420,921 digits.

The largest prime discovered as of June 1, 1999 is 2^6,972,593 - 1. Mersenne Primes contribute to the derivation of Perfect Numbers.

* There are many formulas that yield primes but not all primes. The most misleading is x^2 - x + 41 which works

fine up to x = 39 but breaks down for x = 40 and beyond. Others are 2x^2 - 199, x^2 + x + 11, x^2 + x + 17, x^2 - 79x + 1601, 6x^2 + 6x + 31, x^3 + x^2 - 349, to name a few. There are none that derive all the primes.

* There are an infinite number of Primes

Proof:

From Euclid's Elements (Proposition 20, Book IX)

Assume that p1, p2, p3, ......pn is a finite set of prime numbers.

Create the product P = p1(p2)p3.......(pn) and add 1.

P + 1 forms a new number which is not divisible by any of the given set of primes and must therefore itself be a prime or it contains as a factor a prime differing from those already defined.

If P + 1 is prime, then it is clearly a new prime not of the original set of primes.

If P + 1 is not prime, it must be divisible by some prime q.

However, q cannot be identical to any of the given prime numbers, p1, p2, p3,......pn, as it would then divide both P and P + 1 and consequently, their difference = 1.

However, q must be at least 2 and cannot therefore divide evenly into 1.

Therefore, q, being different from all the given primes, must be a new prime.

Caution: Care must be taken to realize that p1(p2)p3.......(pn) + 1 will not always produce a new prime and if it does, it is not necessarily the next prime.

Examples:

2x3 + 1 = 7 = a prime

2x3x5 + 1 = 31 = a prime

2x3x5x + 1 = 211 = a prime

2x3x5x7x11 + 1 = 2311 = a prime

2x3x5x7x11x13 + 1 = 30,031 = 59x509

* There are an infinite number of primes.

Euclid's proof: Is there a prime greater than N? Derive the quantity N! + 1, N factorial plus one. (N! + 1) is therefore not divisible by any number up to, and including, N, as there is always a remainder of 1. If (N! + 1) is prime, it has no factors other than 1 and itself; if it is not prime, it has factors in addition to 1 and itself.

* While the number of primes is infinite, they become fewer and fewer as the natural numbers approach infinity. For example, the number of primes, p(n) within the first n numbers and their ratio looks like the following:

..n..............p(n)..............p(n)/n........Difference 10^n - 10^(n-1)

10^2............25................(.25)

10^3...........168..............(.168).......................143/900

10^4..........1,229...........(.1229)......................1061/9000

10^5..........9,593..........(.09593).....................8364/90,000

10^6.........78,499........(.078499)..................68,906/900,000

19^7........664,579......(.0664579)................586,080/9,000,000

10^8.......5,761,455...(.057614550)............5,096,876/90,000,000

* As the number of primes decrease and the distance between primes increases, the corresponding sets of consecutive composite numbers become longer. Within the first 100 numbers, there are seven composite numbers between 89 and 97. Within the numbers from 1 to 1000, there are 19 composite numbers between 887 and 907. To define N consecutive composite numbers, you need only compute the numbers (N + 1)! + 2, (N + 1)! + 3, (N + 1)! + 4, (N + 1)! + 5,..... .....(N + 1)! + (N + 1), all being composite.

* Primes can be in arithmetic progression, for example:

7-37-67-97-127-157, 107-137-167-197-227-257, 199-409-619-829-1039-1249-1459-1669-1879-2089.

* There are an infinite number of palindromic primes such as 101, 131, 151, 181, 313, 353, 727, 757, 797, 919,

79997, 91019, 3535353, etc.

* Primes can be both palindromic and in arithmetic progression such as in

13931-14741-15551-16361, 10301-13331-16361-19391 and 94049-94349-94649-94949.

* Unproven hypotheses concerning primes:

Every even number =/> 6 is the sum of two primes.

Every odd number =/> 9 is the sum of three odd primes.

Every even number is the difference between two primes in an infinite number of ways.

Every number is the difference of two consecutive primes in an infinite number of ways.

Every odd number is either a prime or the sum of a prime and twice a square.

Primes can be expressed as the sum of a prime and twice a square.

Every odd number is the sum of a prime and a power of 2.

(Remember - all unproved)

* Goldbach's Conjecture - Every even number is the sum of two prime numbers. No proof exists

* Any positive integer can be written as the product of primes in only one way.

Example: 42 = 2x3x7, 67 = 1x67, 96 = 3x2^5, 52 = 13x2^2.

* Using the digits 1 through 9 only once, form prime numbers the sum of which is a minimum.

2 + 3 + 5 + 41 + 67 + 89 = 207.

Perform the same thing using the digits 0 through 9.

2 + 5 + 7 + 63 + 89 + 401 = 567.

* The squares of the first 7 primes, 2^2 + 3^2 + 5^2 + 7^2 + 11^2 + 13^2 + 17^2, add up to 666, the devil

number.