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 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 252004There 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."
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.
Fermat's factorization method is based on substituting successive values above Square Root(N) for a, in equation 2 above, until we find a^{2}-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 a^{2}-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}=a^{2}+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 b^{2} to N, and checking to see if N+b^{2} is a square.
In the first example below the values in the 2nd column are b^{2} but we get both columns by simply adding successive odd numbers.
* marks last digit check as a possible square N+b^{2} b^{2} 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.
We start with a such that a^{2} is just greater than N. The square root of 511 is 22.6?? so we start with a=23. a^{2}-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.
I include this just to show the difference in using the two equations.
Again * flags last two digit check N+b^{2} 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.
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.
Go to: My Home Page | Go to: This page TOP |