Fermat Factorization Method

Pierre de Fermat

Before Fermat introduced his factorization method, the classical method was to divide n by all prime numbers not exceeding √n.

In his method, Fermat assumes that n is odd and observed that the search for factors of n is equivalent to obtaining the integral solutions of x and y of the equation n = (x^2) – (y^2) = (x – y) (x + y)

If n has a factorization n = ab, a ≥ b ≥ 1
We may write n = ((a+b)/2)^2 – ((a-b)/2)^2 ; (a+b)/2 > 0 and (a-b)/2 > 0

We then determine the smallest integer k for which k^2 ≥ n, k^2 – n, (k+1)^2 – n, (k+2)^2 – n, … until a value of m ≥ √n is found making m^2 – n a square.

We know that this process cannot go on indefinitely, we know we will eventually arrive at ((n+1)/2)^2 – n = ((n-1)/2)^2, the representation of n corresponding to the trivial factorization n = n ∙ 1. Meaning that n is a prime.

Examples:
1. n = 2027651281, k= 45030
45030^2 – 2027651281 = 49619
45031^2 – 2027651281 = 139680
45032^2 – 2027651281 = 229743
45033^2 – 2027651281 = 319808
45034^2 – 2027651281 = 409875
45035^2 – 2027651281 = 499944
45036^2 – 2027651281 = 590015
45037^2 – 2027651281 = 680088
45038^2 – 2027651281 = 770163
45039^2 – 2027651281 = 860240
45040^2 – 2027651281 = 950319
45041^2 – 2027651281 = 1040400 = 1020^2
=> 2027651281 = 45041^2 – 1020^2
=> 2027651281 = (45041+1020)(45041–1020)
=> 2027651281 = (46061)(44021)

---

2. n = 17, k = 5
5^2 – 17 = 8
6^2 – 17 = 19
7^2 – 17 = 32
8^2 – 17 = 47
9^2 – 17 = 64 = 8^2
=> 17 = 9^2 – 8^2
=> 17 = (9 + 8)(9 – 8)
=> 17 = (17)(1)

NOTE:
Squares must end in 0, 1, 4, 5, 6, and 9
And from 0-99 (mod 100) ends in 00, 01, 04, 09, 16, 21, 24, 25, 29, 36, 41, 44, 49, 56, 61, 64, 69, 76, 81, 84, 89, 96

See How it Works HERE!

Download Now

Daghang salamat sa pagbasa!!!

Fermat Numbers

The Fermat Numbers form a sequence in the form

Fn = (2^(2^n)) + 1, n = 0, 1, 2, …
or Fn = pow(2,(pow(2,n))) + 1

The number of digits for a Fermat number is
D(Fn) = └[log (2^(2^n))+ 1)] + 1┘
D(Fn) = └[log (2^(2^n))] + 1┘
D(Fn) = 1 + └2^n log 2┘
or D(Fn) = 1 + floor((2^n) log 2)

The first few Fermat numbers are:

F0 = 2^(2^0) + 1 = (2^1) + 1 = 2 + 1 = 3
F1 = 2^(2^1) + 1 = (2^2) + 1 = 4 + 1 = 5,
F2 = 2^(2^2) + 1 = (2^4) + 1 = 16 + 1 = 17,
F3 = 2^(2^3) + 1 = (2^8) + 1 = 256 + 1 = 257,
F4 = 2^(2^4) + 1 = (2^16) + 1 = 65536 + 1 = 65537

The corresponding number of digits:

D(F0) = 1 +└(2^0) log 2┘= 1 +└1 log 2┘= 1 + 0 = 1
D(F1) = 1 +└(2^1) log 2┘= 1 +└2 log 2┘= 1 + 0 = 1
D(F2) = 1 +└(2^2) log 2┘= 1 +└4 log 2┘= 1 + 1 = 2
D(F3) = 1 +└(2^3) log 2┘= 1 +└8 log 2┘= 1 + 2 = 3
D(F4) = 1 +└(2^4) log 2┘= 1+└16 log 2┘= 1+ 4 = 5

These numbers are more popularly known as Fermat primes.
F5, F6, F7, F8, F9, F10 and F11 are factorable numbers. F11 being the largest known Fermat number to be factored out.

I have created a PHP code for computing the number of digits found in a Fermat number, and the Fermat Number itself if possible.

See How it Works HERE!

Download Here!! 


Daghang salamat sa pagbasa!!!