View Single Post
Old 2017-02-28, 00:46   #8
"mahfoud belhadj"
Feb 2017
Kitchener, Ontario

22×3×5 Posts

Originally Posted by science_man_88 View Post
though I don't use it I would argue you can use the fact that the squares are certain remainders on division by 8 to help 13*643 = 7 mod ( as it's called) 8 squares are 0,1,4 mod 8 so the square you add has to be either 1,2,5 mod 8 only one of which can be a square number so you are looking for a square that is 1 mod 8 the squares go:

0,1,4,1,0,1,4,1,0 so you know you are looking for an odd square and the sum will have to be an even square.
there are many ways to improve Fermat method, especially if one considers only composite numbers of the form (6k+1) and (6k-1). For example, for numbers of the form N=(6i+1)*(6j+1), the general form is this:
N+9k^2=(10+3m)^2. For example, if N=7*13=91, then 91+3^2=10^2 so that N=(10-3)*(10+3)=7*13. The other simple improvement is to consider the sum of digits of N. The square (10+3m)^2 must have the same sum of digits as N so there is really no point considering squares that have a different sum of digits if we were looking for 9k^2=(10+3m)^2-N. For example, if N=7*19=133, the sum of digits is 7 so we only need to consider (10+3m)^2 with the same sum of digits 7 and the first candidate is 13^2 happens to be the right one since 13^2-133=36=9*2^2.

But even with these few improvements, Fermat's method is still slow because it is sequential, that is you need to consider every square of the form 9k^2 is you are adding it to N to get a square and every square (10+3m)^2 with the right sum of digits if you are subtracting N from it to get a square and the one you skip may be the one you need.
mahbel is offline   Reply With Quote