We can factorize a value if we take a value and then add a square value. If the result is a square, we can use the difference of squares to determine the factors. Every integer value, apart from prime numbers, can be factorized.
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 import sys value=32128 if (len(sys.argv)>1): value=int(sys.argv[1]) def getfactor(y): i=0 while True: val = y + i*i # print i,val sq = int(math.sqrt(val)) if (sq*sq == int(val)): print ("Factors: (",sq,"+",i,"),(",sq,"-",i,")") return(sq-i,sq+i) i=i+1 if (i==10000): return("Cannot find") return "Cannot find" print ("Finding factors for",value) rtn=getfactor(value) print ("Factors are: ",rtn)