Factoring: Difference of Square

Method

First we start with:

\(x^2 - y^2 = (x-y) (x+y)\)

If we now have a value of \(N\) which we can present as:

\(N= y^2 - x^2 \)

The factors of \(N\) will then be:

\((x+y)\) and \((x-y)\)

Now if we rearrange \(N= x^2 - y^2 \) we get:

\(N + y^2 = x^2\)

We can thus take N and then take values of \(y\), and see if the result is a square. If it is, we have found two factors. An example, if \(N\) is 4823, we can then take values of \(y\):

x   N + (y*y)
------------ 
0  4823
1  4824
2  4827
3  4832
4  4839
5  4848
6  4859
7  4872
8  4887
9  4904
10 4923
11 4944
12 4967
13 4992
14 5019
15 5048
16 5079
17 5112
18 5147
19 5184 --> 5,284 = 72 * 72 ! We have found it!

In this case we have found that \(4924 + 19^2 = 72^2\)

The factors are thus \(72+19\) and \(72-19\), or 91 and 53.

Finding factors for 4823
Factors: ( 72 + 19 ),( 72 - 19 )
Factors are:  (53, 91)

Code

An outline of the code used is:

import math
value=32128

def getfactor(N):
        i=0
        while True:
                val = N + i*i
                sq = int(math.sqrt(val))
                if (sq*sq == int(val)):
                        return(sq-i,sq+i)
                i=i+1
                if (i==1000): return("Cannot find")
        return i

print getfactor(value)