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 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...pn
Multiply 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.
