| Popis: |
How can you decide if a number is the sum of two squares? Euler began with the dumbest possible algorithm imaginable: Take the number, subtract a square, and check if the remainder is a square. If not, repeat, repeat, repeat. But Euler, being Euler, found a way of converting all those subtractions into additions. Then he did several things to speed up the computation even more. He applied this to 1,000,009, and—in less than a page—found that there are two ways to express this as a sum of squares. Hence, by earlier work in E228, it is not a prime. Amusingly, when he later described how to prepare a table of primes “ad millionem et ultra” (E467), he included this number as prime. So he then felt obliged to write another paper, E699 (1797), using another refinement of his method, to show that 1,000,009 is not prime. |
