(related to Problem: The Sultan's Army)

The smallest primes of the form $4n + 1$ are $5,$ $13,$ $17,$ $29,$ and $37,$ and the smallest of the form $4n - 1$ are $3,$ $7,$ $11,$ $19,$ and $23.$ Now, primes of the first form can always be expressed as the sum of two squares, and in only one way. Thus, $5 = 4+ 1;$ $13 = 9 + 4;$ $17 = 16 + 1;$ $29 = 25 + 4;$ $37 = 36 + 1.$ But primes of the second form can never be expressed as the sum of two squares in any way whatever.

In order that a number may be expressed as the sum of two squares in several different ways, it is necessary that it shall be a composite number containing a certain number of primes of our first form. Thus, $5$ or $13$ alone can only be so expressed in one way; but $65,$ $(5 \times 13),$ can be expressed in two ways, $1,105,$ $(5 \times 13 \times 17)$, in four ways, $32,045,$ $(5 \times 13 \times 17 \times 29)$, in eight ways. We thus get double as many ways for every new factor of this form that we introduce. Note, however, that I say new factor, for the repetition of factors is subject to another law. We cannot express $25,$ $(5 \times 5),$ in two ways, but only in one; yet $125,$ $(5 \times 5 \times 5),$ can be given in two ways, and so can $625,$ $(5 \times 5 \times 5 \times 5);$ while if we take in yet another $5$ we can express the number as the sum of two squares in three different ways.

If a prime of the second form gets into your composite number, then that number cannot be the sum of two squares. Thus $15,$ $(3 \times 5),$ will not work, nor will $135,$ $(3 \times 3 \times 3 \times 5);$ but if we take in an even number of $3$'s it will work, because these $3$'s will themselves form a square number, but you will only get one solution. Thus, $45,$ $(3 \times 3 \times 5,$ or $9 \times 5) = 36 + 9.$ Similarly, the factor $2$ may always occur, or any power of $2,$ such as $4, 8, 16, 32;$ but its introduction or omission will never affect the number of your solutions, except in such a case as $50,$ where it doubles a square and therefore gives you the two answers, $49 + 1$ and $25+ 25.$

Now, directly a number is decomposed into its prime factors, it is possible to tell at a glance whether or not it can be split into two squares; and if it can be, the process of discovery in how many ways is so simple that it can be done in the head without any effort. The number I gave was $ 130.$ I at once saw that this was $2 \times 5 \times 13,$ and consequently that, as $65$ can be expressed in two ways $(64 + 1$ and $49 + 16),$ $130$ can also be expressed in two ways, the factor $2$ not affecting the question.

The smallest number that can be expressed as the sum of two squares in twelve different ways is $160,225,$ and this is, therefore, the smallest army that would answer the Sultan's purpose. The number is composed of the factors $5 \times 5 \times 13 \times 17 \times 29,$ each of which is of the required form. If they were all different factors, there would be sixteen ways; but as one of the factors is repeated, there are just twelve ways. Here are the sides of the twelve pairs of squares: $(400, 15),$ $(399, 32),$ $(393, 76),$ $(392, 81),$ $(384, 113),$ $(375, 140),$ $(360, 175),$ $(356, 183),$ $(337, 216),$ $(329, 228),$ $(311, 252),$ $(265, 300).$ Square the two numbers in each pair, add them together, and their sum will in every case be $160,225.$

**Dudeney, H. E.**: "Amusements in Mathematics", The Authors' Club, 1917

This eBook is for the use of anyone anywhere in the United States and most other parts of the world at no cost and with almost no restrictions whatsoever. You may copy it, give it away or re-use it under the terms of the Project Gutenberg License included with this edition or online at http://www.gutenberg.org. If you are not located in the United States, you'll have to check the laws of the country where you are located before using this ebook.