20170620, 00:56  #89  
Feb 2017
Nowhere
11617_{8} Posts 
Quote:
Of course, I must concede, the OP's method stands an excellent chance of finding factors  provided they're less than 100! The fact that trial division will almost certainly find all such factors much more quickly, in no way detracts from this. As to factors of any size, I refer the reader to my remarks in post #40, linked to above. I will add that, forming all combinations of a^2, b^2, c^2, d^2, a, b, c, and d, with coefficients from the set {1, 0, 1}, will give 6561 numbers (not necessarily all different) for each 4tuple (a, b, c, d), so the number of possibilities is multiplied by less than 10,000  far less than the factor of a trillion I allowed for in my analysis. I find it ironic that the OP demands others "say it with math," when he has already stated he doesn't understand the math. I did a bit of math with the question partly to satisfy my own curiosity, and partly to test the OP's receptiveness. At this point, my inclination to mathify further on the subject is tempered by the wisdom of the Good Book, particularly Matthew 7:6. I approve of the change to the subject name for this thread. I found the adjective "strong" an inapt modifier of "problem" in the thread from whence the new name of this thread originated. It is at least applicable to the term "method," even if the description of the method under discussion as "strong" is of dubious accuracy. 

20170620, 15:15  #90  
Feb 2017
Nowhere
3×1,669 Posts 
Quote:
Going through the thread, the only numbers I could find for which the OP produced factors, are 91 and 77. As it turns out, both have 7 as a factor. Also as it turns out, numbers this small are quickly factored by a simple differenceofsquares method. Such methods were favored by, e.g. Fermat. For example, adding squares to 77 gives 77 + 1 = 78 (not a square), 77 + 4 = 81 = 9^2, and the factors are 9  2 = 7 and 9 + 2 = 11. Alternatively, sqrtint(77) = 8; 9^2  77 = 4, again giving the factors 9  2 = 7 and 9 + 2 = 11. Similarly, 91 + 1 = 92 (not square), 91 + 4 = 95 (not square), 91 + 9 = 10^2, giving the factors 10  3 = 7 and 10 + 3 = 13. Alternatively, sqrtint(91) = 9; 10^2  91 = 9 = 3^2, giving the factors 10  3 = 7 and 10 + 3 = 13. I invite the OP to try his method on N = 19673. One of the differenceofsquares methods gives the factors in fewer than ten tries. Now mind, I am not advocating the simpleminded differenceofsquares methods exemplified above as general factoring methods. They're far too slow. However, I would be remiss if I did not point out that the best methods known today for factoring large numbers with no "small" factors, are avatars of the differenceofsquares method. The basic idea behind them is to find two squares which are congruent (mod N), both of which are "smooth," i.e. all (or perhaps all but one or two of) their prime factors are less than a fairly small preset bound B. Regarding the number field sieve, I refer the interested reader to Murphy's thesis and Bai's thesis. 

20170621, 06:54  #91  
Dec 2012
The Netherlands
1751_{10} Posts 
Quote:


20170621, 12:33  #92 
"mahfoud belhadj"
Feb 2017
Kitchener, Ontario
60_{10} Posts 
On a possible justification of using combinations of nonsquare (a,b,c,d) to find factors.
There are two ways to look at using the 4sq reps, the arithmetic way and the geometric way. The arithmetic way is the one which uses combinations of squares (a^2,b^2,c^2,d^2) and find a factor by evaluating the gcd. The geometric way is similar to tiling of squares or rectangles using 4sq reps. I will use the example of 3*5=15 to explain what I mean. 15=(3,2,1,1). if we draw a rectangle with sides 3 by 5, we will be able to tile that rectangle exactly with a square 3^2, a square 2^2 and 2 squares of 1^2. This example is one of those perfect examples where the rectangle 3*5 is tiled as stated before. Now if we look at the picture of that rectangle (not provided), we see that 3 is a factor and (3+2) is also a factor. The general case is not always this nice. Even when considering the simple case of 77=7*11, we run into problems. That is we can't fit the 4sq rep (6,6,2,1) into a rectangle of 7 by 11 ( simply because 6+6>11). But there is a way around that if we expand 6^2 itself into a 4sq rep and find a way to fit the different squares into the rectangle. I did that for the 4sq rep (5^2,6^2,4^2) of 77. We can fit 5^2 and 6^2 into a rectangle of 7 by 11. But we will be left with a space, with of course a surface area of 4^2, but which does not have a shape of a 4x4 square. But 4^2 can itself be expanded into 4^2=2^2+2^2+1+1+1+1+1+1+1+1. After all, there is no rule or theorem that says we can't expand a square into a sum of 4 or more than 4 squares. If we do that, we will be able to fit the original 4sq rep exactly but with the new 10 term rep for 4^2. If we look at the drawing (no picture will be provided), we then can see that the factors are 5+2=7, 5+6=11 and 6+1=7. Can factoring integers be reduced to a tiling of rectangles problem? Well, everyone is free to find an answer for themselves. Last fiddled with by mahbel on 20170621 at 12:38 Reason: correct a spelling. 
20170621, 12:41  #93 
"Forget I exist"
Jul 2009
Dumbassville
10000011000000_{2} Posts 
so you are trying to do things like:
? 
20170621, 13:23  #94 
"mahfoud belhadj"
Feb 2017
Kitchener, Ontario
2^{2}×3×5 Posts 
Not really. Fitting squares into squares looks more complicated to me. Fitting squares into rectangles is what I am trying to do to justify using nonsquares (a,b,c,d) to find factors. If one (or more than one) square of the original 4sq rep cannot be fit into the rectangle, we just expand it into a sum of n squares and try again. There is no rule to tell us what the value of n should be.
In the example provided (77=7*11), the work was done backward so the difficulties were not apparent. But the principle itself is a general one. 
20170621, 13:30  #95  
"Forget I exist"
Jul 2009
Dumbassville
2^{6}·131 Posts 
Quote:
Last fiddled with by science_man_88 on 20170621 at 13:52 

20170621, 16:35  #96  
Feb 2017
Nowhere
3·1,669 Posts 
Quote:


20170621, 17:06  #97  
Aug 2006
3×1,993 Posts 
Quote:


20170621, 18:42  #98  
"mahfoud belhadj"
Feb 2017
Kitchener, Ontario
2^{2}·3·5 Posts 
Quote:
in the example I gave about 77=7*11, it was shown using the (5^2,6^2,4^2) rep that some combinations of (a,b,c,d) provided a factor before we had a complete tiling. namely 5+6=11 combination. In fact, I did not provide the complete tiling. It's only if you wanted to tile the whole rectangle that you need to do more work. In this case, you would have had to express 4^2 as a sum of squares in a way that allows the full tiling. But it's not needed. Last fiddled with by mahbel on 20170621 at 18:51 Reason: added example to explain 

20170621, 20:16  #99 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
2×4,787 Posts 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
A Sierpinski/Riesellike problem  sweety439  sweety439  1250  20211001 12:53 
Another factoring method rides the bus  3.14159  Factoring  233  20110515 18:50 
Square numbers and binary representation  ET_  Miscellaneous Math  40  20100606 12:55 
Is this a feasible factoring method?  1260  Miscellaneous Math  46  20100531 17:37 
Representation of integer as sum of squares  kpatsak  Math  4  20071029 17:53 