Squares, sums of 2 (1) 1

# Squares, sums of 2 (1).

Talking about divisility we found that a number is divisible if it ca be written as twice the sum of two squares on a different way.
If a number can be written as only once the sum of tho squares, it is a prime number.

We can spare ourselves a lot of work if we think about the possibilities before going to work. Are there number which cannot be the sum of two squares? Yes, there are: every number 3(4) cannot be written as the sum of two squares.

The square of any even number, 0(2) or 2(4) is 0(4). The square of any odd number, 1(4) or 3(4) is 1(4). It is evident: when we add 0 + 1(4) the only result is 1(4). When we add 1+1 we get 2(4), so even numbers may be the sum of two squares.

The better is to invoke modulo 8 for determine if a number is the sum of two squares, as we will have additions which exceed 100. An even number squared is either 0(8) or 4(8). Every odd number squared is 1(8). So the sum of two squares may be 0(8), 1(8), 4(8) or 5(8).

It is also useful to invoke mod 9, as this will help us in economising the quantity of work we’ll have to do. For the squares mod 9 there are the possibilities: 0, 1, 4 and 7 mod 9. In sums of squares there are the possibilities: 0, 1, 2, 4, 5, 7 and 8 mod 9. 3 and 6 mod 9 is impossible, as you can easily deduct.

We’ll go at search.

281 is the sum of which squares? As 81 can only be composed by 00 + 81 and 25 + 56. 281 = 2 mod 9, so we can ignore 15 as a candidate as 15² = 0 (9). 5²=25, 16²=256, 25+256=281, and here we have the combination we were looking for.

1349, 8(9). Possibilities: 24, OH (Odd Hundred) + 25, always EH (Even Hundred). Under 1349 we only have 18² = indeed OH, but as 324 = 0(9) 18 drops out. 7² = 49, 4(9) , 20² = 400 = 4(9), 30² = 0(9), and is to low, so 1349 cannot be written as the sum of two squares.

4178. 2(9). As 78 can be composed by 09 + 69, 29 + 49 and 89 + 89, we do better to divide by 2 and have 2089, 1(9), and EH 89 can only be composed by 89, always EH + 00(EH), or 64(EH) and 25, always EH. List of candidates: 5, 8, 15, 17, 33, 45. Which ones drop out and why? 5, as 5² = 7(9) , 15² as  2089 – 225 = 1864 and 1864 is no square, 17 as 17² + 1800 = 2089 but 1800 is no square, 33 as 33² = 1089 but 1000 is no square. What remains is the combination 8² + 45² =2089.
In case of a 89 (OH) either the 64 or 00 have to be OH.

21473, 8(9). 8 mod 9 can be composed as 1 + 7, 4 + 4.  9 has always EH, + 64 EH, or 24 EH + 49, always EH, 44 OH ad 29 (OH) is always EH, 04 OH as 69 is always OH, and 84 OH as 89 is always EH.
We can economise our labour by doubling, 42946, 7(9) because 46 can only be composed by 25, always EH and 21, always OH.
All the squares other than 0 mod 9 and 7(9) drop out automatically.
The candidates and eventual drop outs are 5, 15, 39, 45, 61, 75, 85, 89, 105, 111, 125, 135, 139, 145, 155, 161, 165, 175, 185, 189, 195, 205. Here we can stop, as 205. In this enumeration we can immediately skip the numbers 61, 89, 125, 145,155 and 161 because their squares are neither 0 nor 7 mod 9.

We continue. : 5, 5² = 25 and 42921 is no square, 15, as 15² = 225 and 42721 is no square, 39, as 39³ = 1521and there is no square ending on 425 ( nor there is a square …825), 45 as 40921 is no square, 61² = 4(9), 85²=7225, and (full hit): 35721 is the square of 189. 105 drops out as 31921 is no square. 111 is another hit: 42946-111² = 30625 which is 175².
We have now 42946 = 175² +111², and 189² + 85².
We reduce: 21473 is the sum of the following squares = (175 ± 111) ÷ 2 = 143² and 32² and (189 ± 85) ÷ 2 = 137² + 52². Now we can conclude that 21473 is divisible. In another theme we’ll work out which ones are the factors.