Factoring by recognizing squares of integers.

Last Up date: 2007 October 9
This Page made from an earlier page on: 2007 October 09 13:51:42

We note that when we square any number the last digit of the number we are squaring determines the last digit of the result. The square of the digits 0 through 9 are: 0 1 4 9 16 25 36 49 64 81. Keeping only the last digit we get: 0 1 4 9 6 5 6 9 4 1 Notice the symmetry on each side of the digit 5. If were are not interested in duplicates we really only needed to square the digits up through 5.

In base ten, the last digit of any number that is a "square" can only be: 0, 1, 4, 5, 6, or 9
If we are checking numbers for being squares, by just looking at the last digit of any number we can reject nearly half. In any number system base nearly half the last digits never occur in numbers that are squares.

If we were to examine the last two digits. (We would essentially be doing the above for number base 100.) We would discover the only last pair of digits for a square would be:
00 01 04 09 16 21 24 25 29 36 41 44 49 56 61 64 69 76 81 84 89 96
In the above 22 possible "last digit pairs" some simple rules can be deduced:

  1. The last digits of 2 3 7 and 8 are never squares.
  2. If the last digit is 6 the preceding digit must be odd.
  3. If the last digit is 1 4 or 9 the preceding digit must be even.
  4. 00 and 25 are the only last two digits that end in 0 or 5.
Note that in number base 100 there are prime factors that occur more than once. When this happens there are less than half the "last digits" that occur in squares.

Squares of numbers 0 through 502

In the following I have numbered the lines simply so we can reference where in the table we want to direct attention. 
 1                          Sun  07-14-2002  05:04:32
 2 
 3 0 1 4 9 16 25 36 49 64 81 100 121 144 169 196 225 256 289 324 361 400 441
 4 484 529 576 625 676 729 784 841 900 961 1024 1089 1156 1225 1296 1369 1444
 5 1521 1600 1681 1764 1849 1936 2025 2116 2209 2304 2401 2500 2601 2704 2809
 6 2916 3025 3136 3249 3364 3481 3600 3721 3844 3969 4096 4225 4356 4489 4624
 7 4761 4900 5041 5184 5329 5476 5625 5776 5929 6084 6241 6400 6561 6724 6889
 8 7056 7225 7396 7569 7744 7921 8100 8281 8464 8649 8836 9025 9216 9409 9604
 9 9801 10000 10201 10404 10609 10816 11025 11236 11449 11664 11881 12100 12321
10 12544 12769 12996 13225 13456 13689 13924 14161 14400 14641 14884 15129
11 15376 15625 15876 16129 16384 16641 16900 17161 17424 17689 17956 18225
12 18496 18769 19044 19321 19600 19881 20164 20449 20736 21025 21316 21609
13 21904 22201 22500 22801 23104 23409 23716 24025 24336 24649 24964 25281
14 25600 25921 26244 26569 26896 27225 27556 27889 28224 28561 28900 29241
15 29584 29929 30276 30625 30976 31329 31684 32041 32400 32761 33124 33489
16 33856 34225 34596 34969 35344 35721 36100 36481 36864 37249 37636 38025
17 38416 38809 39204 39601 40000 40401 40804 41209 41616 42025 42436 42849
18 43264 43681 44100 44521 44944 45369 45796 46225 46656 47089 47524 47961
19 48400 48841 49284 49729 50176 50625 51076 51529 51984 52441 52900 53361
20 53824 54289 54756 55225 55696 56169 56644 57121 57600 58081 58564 59049
21 59536 60025 60516 61009 61504 62001 62500 63001 63504 64009 64516 65025
22 65536 66049 66564 67081 67600 68121 68644 69169 69696 70225 70756 71289
23 71824 72361 72900 73441 73984 74529 75076 75625 76176 76729 77284 77841
24 78400 78961 79524 80089 80656 81225 81796 82369 82944 83521 84100 84681
25 85264 85849 86436 87025 87616 88209 88804 89401 90000 90601 91204 91809
26 92416 93025 93636 94249 94864 95481 96100 96721 97344 97969 98596 99225
27 99856 100489 101124 101761 102400 103041 103684 104329 104976 105625 106276
28 106929 107584 108241 108900 109561 110224 110889 111556 112225 112896 113569
29 114244 114921 115600 116281 116964 117649 118336 119025 119716 120409 121104
30 121801 122500 123201 123904 124609 125316 126025 126736 127449 128164 128881
31 129600 130321 131044 131769 132496 133225 133956 134689 135424 136161 136900
32 137641 138384 139129 139876 140625 141376 142129 142884 143641 144400 145161
33 145924 146689 147456 148225 148996 149769 150544 151321 152100 152881 153664
34 154449 155236 156025 156816 157609 158404 159201 160000 160801 161604 162409
35 163216 164025 164836 165649 166464 167281 168100 168921 169744 170569 171396
36 172225 173056 173889 174724 175561 176400 177241 178084 178929 179776 180625
37 181476 182329 183184 184041 184900 185761 186624 187489 188356 189225 190096
38 190969 191844 192721 193600 194481 195364 196249 197136 198025 198916 199809
39 200704 201601 202500 203401 204304 205209 206116 207025 207936 208849 209764
40 210681 211600 212521 213444 214369 215296 216225 217156 218089 219024 219961
41 220900 221841 222784 223729 224676 225625 226576 227529 228484 229441 230400
42 231361 232324 233289 234256 235225 236196 237169 238144 239121 240100 241081
43 242064 243049 244036 245025 246016 247009 248004 249001 250000 251001 252004
There seems to be 159 unique last triples in squares. 
000 001 004 009 016 024 025 036 041 044 049 056 064 076 081 084 089 096
100 104 116 121 124 129 136 144 156 161 164 169 176 184 196
201 204 209 216 224 225 236 241 244 249 256 264 276 281 284 289 296
304 316 321 324 329 336 344 356 361 364 369 376 384 396
400 401 404 409 416 424 436 441 444 449 456 464 476 481 484 489 496
500 504 516 521 524 529 536 544 556 561 564 569 576 584 596
600 601 604 609 616 624 625 636 641 644 649 656 664 676 681 684 689 696
704 716 721 724 729 736 744 756 761 764 769 776 784 796
801 804 809 816 824 836 841 844 849 856 864 876 881 884 889 896
900 904 916 921 924 929 936 944 956 961 964 969 976 984 996

159 unique triples seems like a strange number? Also, I find the lack of symmetry in each block of 100's surprising? Sat 2002-Nov-02 I recieved a note from Angela M. Hey: "I verified your 159 number for the number of 3-digit strings at the end of a squared number - also for 4 its 1044."

Factoring

If N is odd, then its factors will be odd. Call the factors: f1 and f2 then the sum and difference of the factors will be even. (If it helps: Think about the factors in binary.)
So we can talk about the "average" and "difference" of the factors:
a=(f1+f2)/2 and b=(f1-f2)/2


Notice: a, b, and N are all integers, and when the two factors of N are both large. b will be small. b would be zero if N is a square.

N=(a-b)(a+b)
N=a2-b2

But this can be written as:
  1. a2=N+b2 From this we can note that a2>N or a>Square Root(N)
  2. b2=a2-N
Either 1 or 2 above can be used to factor large numbers. If we can find integers for a2 and b2. For serious work 2 has definite advantages!

Fermat's factorization method is based on substituting successive values above Square Root(N) for a, in equation 2 above, until we find a2-N is a square. This is quite easy because, as shown above, many values can be rejected by a simple inspection of their last digit(s).

Important note: When we have figured a2-N to get: (a+1)2-N all we have to do is add on: 2a+1 which is an odd number. This is because: (a+1)2=a2+2a+1 To get successive values to test for being a square one only has to add successive odd numbers. Believe me this simple add is much easier than successive multiplies or divides. Hence: The value of Fermat's method.

Generally equation 2 is used because b is smaller and verifying the square of the smaller number is easier, even though the numbers that have to be added each time is larger. In my first example I will use equation 1, because adding the number one and then successive odd number is a bit simpler.

We add b2 to N, and checking to see if N+b2 is a square.

a2=N+b2 Factoring examples.

In the first example below the values in the 2nd column are b2 but we get both columns by simply adding successive odd numbers.

Factoring 513 using equation 1

* marks last digit check as a possible square
N+b2 b2
513 00
514 01  * but 514 is not a square
517 04
522 09
529 16  * 529 is a square! a=23, b=4 thus 513=(23-4)(23+4) or 19*27

Notice how well this technique found the largest factors first. And, the factors need not always be prime numbers.

Factoring 511 using equation 2

We start with a such that a2 is just greater than N.
 The square root of 511 is 22.6?? so we start with a=23.

a2-N a
 18 23  to get the value for a=24 we will just add 2*a+1 or 47
 65     to this we add 49
114     to this we add 51
165     to this we add 53
218     to this we add 55
273     to this we add 57
330     to this we add 59
389*    to this we add 61
450     to this we add 63
513     to this we add 65
578     to this we add 67
645     to this we add 69
714     to this we add 71
785     to this we add 73
858     to this we add 75
933     to this we add 77
1010    to this we add 79
1089*   this is 33 squared! Which is b squared. So 1089+511=a squared 1600
Hence we know 40+33=73 is one factor and the other is 40-33=7

This may seem like a lot of work but: Lehmer's chain machine would tell us to check just the two values with the * if it only had one chain with 100 links. And it would have only turned through 18 links, but that is a bit beyond what I have explained here. The real work would have been in setting the locations of the stopping screws.

Factoring 511 using equation 1

I include this just to show the difference in using the two equations.

Again * flags last two digit check
N+b2 b
511 00
512 01
515 02
520 03
527 04
536 05  *
547 06
560 07
575 08
592 09
611 10
632 11
655 12
680 13
707 14
736 15  *
767 16
800 17  *
835 18
872 19
911 20
952 21
995 22
1040 23
1087 24
1136 25 *
1187 26
1240 27
1295 28
1352 29
1411 30
1472 31
1535 32
1600 33 *  a=40 b=33  (a-b)=7, (a+b)=73 thus 511=7*73

The above examples were done using base ten number system. If we had a single chain of 100 links with a "stopping screw" at the numbers that we noted above as valid last digits for squares the machine would have stopped where there are * in the above examples. This single chain would be checking "last valid" digits in number system base 100.

If we added a second chain of say 49 links. With "stopping screws" placed again for numbers that are squares the machine would not stop except on numbers that are squares in both base 100 and base 49 Lehmer's machine has 19 chains for simultaneously checking in 19 different number systems.

Last "Digits" of Squares for the D. H. Lehmer Chain Machine
Bold number in each group is the chain length. Tue 02-10-02 22:35:12

  1. 64 - 0, 1, 4, 9, 16, 17, 25, 33, 36, 41, 49, 57
  2. 27 - 0, 1, 4, 7, 9, 10, 13, 16, 19, 22, 25
  3. 25 - 0, 1, 4, 6, 9, 11, 14, 16, 19, 21, 24
  4. 49 - 0, 1, 2, 4, 8, 9, 11, 15, 16, 18, 22, 23, 25, 29, 30, 32, 36, 37, 39, 43, 44, 46
  5. 22 - 0, 1, 3, 4, 5, 9, 11, 12, 14, 15, 16, 20
  6. 26 - 0, 1, 3, 4, 9, 10, 12, 13, 14, 16, 17, 22, 23, 25
  7. 17 - 0, 1, 2, 4, 8, 9, 13, 15, 16
  8. 19 - 0, 1, 4, 5, 6, 7, 9, 11, 16, 17
  9. 23 - 0, 1, 2, 3, 4, 6, 8, 9, 12, 13, 16, 18
  10. 29 - 0, 1, 4, 5, 6, 7, 9, 13, 16, 20, 22, 23, 24, 25, 28
  11. 31 - 0, 1, 2, 4, 5, 7, 8, 9, 10, 14, 16, 18, 19, 20, 25, 28
  12. 37 - 0, 1, 3, 4, 7, 9, 10, 11, 12, 16, 21, 25, 26, 27, 28, 30, 33, 34, 36
  13. 41 - 0, 1, 2, 4, 5, 8, 9, 10, 16, 18, 20, 21, 23, 25, 31, 32, 33, 36, 37, 39, 40
  14. 43 - 0, 1, 4, 6, 9, 10, 11, 13, 14, 15, 16, 17, 21, 23, 24, 25, 31, 35, 36, 38, 40, 41
  15. 47 - 0, 1, 2, 3, 4, 6, 7, 8, 9, 12, 14, 16, 17, 18, 21, 24, 25, 27, 28, 32, 34, 36, 37, 42
  16. 53 - 0, 1, 4, 6, 7, 9, 10, 11, 13, 15, 16, 17, 24, 25, 28, 29, 36, 37, 38, 40, 42, 43, 44, 46, 47, 49, 52
  17. 59 - 0, 1, 3, 4, 5, 7, 9, 12, 15, 16, 17, 19, 20, 21, 22, 25, 26, 27, 28, 29, 35, 36, 41, 45, 46, 48, 49, 51, 53, 57
  18. 61 - 0, 1, 3, 4, 5, 9, 12, 13, 14, 15, 16, 19, 20, 22, 25, 27, 34, 36, 39, 41, 42, 45, 46, 47, 48, 49, 52, 56, 57, 58, 60
  19. 67 - 0, 1, 4, 6, 9, 10, 14, 15, 16, 17, 19, 21, 22, 23, 24, 25, 26, 29, 33, 35, 36, 37, 39, 40, 47, 49, 54, 55, 56, 59, 60, 62, 64, 65

    These are the chain lengths the 1928 paper says Lehmer's machine used.

    I have no idea why the machine in the Computer History Museum does not exactly follow what was described in the 1928 paper. Also, the paper states that the zero position of each chain should be painted red. (Useful, for initialize the machine.) This to seems to be missing in the replica in the Computer History Museum.

    In actual use the stopping screws are not set to the values given above, but are "customized" for every number being factored. But this involves mathematics beyond what I have described here.

    You can: E-mail me or Click on the phone numbers for my BIO:

    Go to: My Home Page My phone #'s Go to: This page TOP