Sum of Squares

Decomposing an integer $ n $ into a sum of squares involves writing this number as an addition of squared numbers:

— Sum of 2 squares: $ n = a^2 + b^2 $

— Sum of 3 squares: $ n = a^2 + b^2 + c^2 $

— Sum of 4 squares: $ n = a^2 + b^2 + c^2 + d^2 $

where $ a $, $ b $, $ c $, and $ d $ are integers (positive, zero, or negative)

An integer $ n > 1 $ can be written as the sum of two squares $ n = a^2 + b^2 $ if and only if in the prime factorization of $ n $ there is no prime factor $ p^k $ such that $ p \equiv 3 \mod 4 $ and the exponent $ k $ is even.

In other words, if a prime number of the form $ 4k + 3 $ is present to an odd power, then $ n $ is not a sum of two squares.

Here are the primes up to 1000: 0, 1, 2, 4, 5, 8, 9, 10, 13, 16, 17, 18, 20, 25, 26, 29, 32, 34, 36, 37, 40, 41, 45, 49, 50, 52, 53, 58, 61, 64, 65, 68, 72, 73, 74, 80, 81, 82, 85, 89, 90, 97, 98, 100, 101, 104, 106, 109, 113, 116, 117, 121, 122, 125, 128, 130, 136, 137, 144, 145, 146, 148, 149, 153, 157, 160, 162, 164, 169, 170, 173, 178, 180, 181, 185, 193, 194, 196, 197, 200, 202, 205, 208, 212, 218, 221, 225, 226, 229, 232, 233, 234, 241, 242, 244, 245, 250, 256, 257, 260, 261, 265, 269, 272, 274, 277, 281, 288, 289, 290, 292, 293, 296, 298, 305, 306, 313, 314, 317, 320, 324, 325, 328, 333, 337, 338, 340, 346, 349, 353, 356, 360, 361, 362, 365, 369, 370, 373, 377, 386, 388, 389, 392, 394, 397, 400, 401, 404, 405, 409, 410, 416, 421, 424, 425, 433, 436, 441, 442, 445, 449, 450, 452, 457, 458, 461, 464, 466, 468, 477, 481, 482, 484, 485, 488, 490, 493, 500, 505, 509, 512, 514, 520, 521, 522, 529, 530, 533, 538, 541, 544, 545, 548, 549, 554, 557, 562, 565, 569, 576, 577, 578, 580, 584, 585, 586, 592, 593, 596, 601, 605, 610, 612, 613, 617, 625, 626, 628, 629, 634, 637, 640, 641, 648, 650, 653, 656, 657, 661, 666, 673, 674, 676, 677, 680, 685, 689, 692, 697, 698, 701, 706, 709, 712, 720, 722, 724, 725, 729, 730, 733, 738, 740, 745, 746, 754, 757, 761, 765, 769, 772, 773, 776, 778, 784, 785, 788, 793, 794, 797, 800, 801, 802, 808, 809, 810, 818, 820, 821, 829, 832, 833, 841, 842, 845, 848, 850, 853, 857, 865, 866, 872, 873, 877, 881, 882, 884, 890, 898, 900, 901, 904, 905, 909, 914, 916, 922, 925, 928, 929, 932, 936, 937, 941, 949, 953, 954, 961, 962, 964, 965, 968, 970, 976, 977, 980, 981, 985, 986, 997, 1000

The list of integers that can be decomposed into the sum of 2 squares is listed in the OEIS A001481 series here

The numbers that cannot be decomposed into the sum of 2 squares are: 3, 6, 7, 11, 12, 14, 15, 19, 21, 22, 23, 24, 27, 28, 30, 31, 33, 35, 38, 39, 42, 43, 44, 46, 47, 48, 51, 54, 55, 56, 57, 59, 60, 62, 63, 66, 67, 69, 70, 71, 75, 76, 77, 78, 79, 83, 84, 86, 87, 88, 91, 92, 93, 94, 95, 96, 99, etc.

According to Legendre's theorem (also called the 3-square theorem):

An integer $ n $ is a sum of $ 3 $ squares unless it is of the form: $ n = 4^k(8m + 7) $ with $ k $ and $ m $ natural numbers.

The list of integers that can be decomposed into sums of 3 squares is listed in the OEIS sequence A000378 here

The numbers that cannot be decomposed into sums of 3 squares are: 7, 15, 23, 28, 31, 39, 47, 55, 60, 63, 71, 79, 87, 92, 95, 103, 111, 112, 119, 124, 127, 135, 143, 151, 156, 159, 167, 175, 183, 188, 191, 199, 207, 215, 220, 223, 231, 239, 240, 247, 252, 255, 263, 271, 279, 284, 287, 295, 303, 311, 316, 319, 327, 335, 343, 348, 351, 359, 367, 368, 375, 380, 383, 391, 399, 407, 412, 415, 423, 431, 439, 444, 447, 448, 455, 463, 471, 476, 479, 487, 495, 496, 503, 508, 511, 519, 527, 535, 540, 543, 551, 559, 567, 572, 575, 583, 591, 599, 604, 607, 615, 623, 624, 631, 636, 639, 647, 655, 663, 668, 671, 679, 687, 695, 700, 703, 711, 719, 727, 732, 735, 743, 751, 752, 759, 764, 767, 775, 783, 791, 796, 799, 807, 815, 823, 828, 831, 839, 847, 855, 860, 863, 871, 879, 880, 887, 892, 895, 903, 911, 919, 924, 927, 935, 943, 951, 956, 959, 960, 967, 975, 983, 988, 991, 999, etc.

Lagrange's four-square theorem states that any natural number $ n \geq 0 $ can be written as the sum of four squares of integers.

Fermat's theorem states that any prime number $ p > 2 $ can be written in the form: $ p = a^2 + b^2 $ if and only if $ p \equiv 1 \mod 4 $