Euclid, Fermat and theorems of prime numbers
Prime factorization proofs, algorithms and history is a fascinating and field. This page does not, by any means, provide a comprehensive history of this topic, but does not describe many of the 'greatest hits' of this topic and provide links to other sources for further study.
- Euclid's Infinity of Primes
- Fermats Proofs and conjectures of prime numbers
Euclid's proof of infinity of primes
Euclid (circa 325 - 265 BC) provided the first known proof of the infinity of primes. A key idea that Euclid used in this proof about the infinity of prime numbers is that every number has a unique prime factorization. As an example, the prime factorization of 12 is 2²•3. And 12 is the only number with these prime factors! Given that fact, Eculid deduced the following proof:
Given a list of known prime numbers p1,p2, p3...pnMultiply p1•p2 •p3•... •pn and add 1 to get a new number. Let's call that number q
- EITHER q is a new prime that is NOT on the list
- OR q is divisible by some prime number that is not on that list!
Fermat (August 17, 1601 - January 12, 1665)
- Fermat's Little Theorem
October 18, 1640, Fermat wrote a letter stating that: given any two relatively prime numbers (no common factors except 1) a and p where p is a prime number, then p divides ap −1 − 1. You can rewrite Fermat's Little theorem as the following equation aP −1/ p = 1
Example let p = 5. Remember p must be a prime number. Let's Fermat's Little Theorem with a =3. The only prerequisite for a is that it must have any common factors with p (relatively prime).
- Fermat Primes or Fermat Numbers
- F0 = 21 + 1 = 3
- F1 = 22 + 1 = 5
- F2 = 24 + 1 = 17
- F3 = 28 + 1 = 257
- F4 = 216 + 1 = 65537
- F5 = 232 + 1 = 4294967297 = 641 x 6700417
- F6 = 264 + 1 = 18446744073709551617 = 274177 x 67280421310721
- F7 = 2128 + 1 = 340282366920938463463374607431768211457 = 59649589127497217 x 5704689200685129054721
- F8 = 2256 + 1 = 115792089237316195423570985008687907853269984665640564039457584007913129639937 = 1238926361552897 x 93461639715357977769163558199606896584051237541638188580280321
Fermat put forth the following conjecture: Fermat stated that the following formula creates prime numbers. This formula holds true up to and including the fourth number F4 = 216 + 1 = 65537. All Fermat numbers factored after F4 , have been shown to be false, and Mathematicians have become so demoralized about Fermat "primes" that most now believe that there are NO more Fermat Primes after F4 !
As of the writing of this web page, only the first 12 Fermat numbers have been factored. Go here to see more detail.