﻿ Prime Factorization Proofs and theorems

# Prime Numbers/Factorization Proofs & Conjectures

### 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
• 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 !

• 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

As of the writing of this web page, only the first 12 Fermat numbers have been factored. Go here to see more detail.

### Ultimate Math Solver (Free)

Free Algebra Solver ... type anything in there!