Hits: 90
The 3×3 and 4×4 squares have been used in the past as building blocks for larger magic squares. To use these as building blocks, the order of the resulting square must be some multiple of 3 or 4. In fact, you can say the same thing about building larger squares from any smaller squares of prime order as well.
The Fundamental Theorem of Arithmetic states that all 
, or all numbers N from 0 to infinity have a prime factorization. If it doesn’t have prime factors, then N is itself prime.
Numbers that are not prime have more factors than just 1 and itself. Those numbers are called composite. There is an exception: the number 1, which is not prime (primes have 2 factors: 1 and itself, while 1 just has 1 as a factor), nor is it composite. Yes, I guess you can say there are infinitely many “order-1” (or 1×1) magic squares. For example, the magic square
21
is magic, since it “adds” to 21 in “all directions”. But that is getting philosophical and does not yield much helpful information for building larger squares. You can say that for any single number.
I bring this up, because I have mentioned high-yielding methods of producing prime-ordered magic squares in the past. Orders that are not prime are multiples of a smaller number. Since no order-2 squares exist, we can’t use order-2 as a building block, so we must divide by 2 and use a different factor as a building block. Sometimes order 4 can be used, as they are for making 8×8, 12×12 or 16×16 squares. It’s a little bit dodgy because every 2nd even number is a multiple of 2 and not 4, like 6 or 14. For order 6 then, we turn to order 3 as a building block; for order 14, we must use order-7 as a building block. Since 2 divides all even numbers, higher even numbers can be just divided by 2, with the other factor being used as the building block, so it looks as though one can say that for all nonprime numbers greater than 3, there will exist a number that has a factor apart from 2. A statement like this requires a proof, but I will just state it here for now.
Investigations into 9×9 squares
Odd composite orders like 9 have 3 as a prime factor. And such squares have often been composed of 3×3 tiles via the Lo Shu Method. Squares of order-15 have prime factors 3 and 5, so that such squares can be composed of tiles of fifteen 3×3 squares or nine 5×5 squares.
I tried a little experiment where I attempt to make a 9×9 square out of these same numbers shown above, but using the numbers above also as scalar multiples of the matrix. Let S be the Lo Shu square, expressed as a matrix. Then, each position becomes another Lo Shu square multiplied by a scalar multiple, as follows:
4S 9S 2S
3S 5S 7S
8S 1S 6S
The result is the following 9×9 matrix which has magic properties:
| 16 | 36 | 8 | 36 | 81 | 18 | 8 | 18 | 4 |
| 12 | 20 | 28 | 27 | 45 | 63 | 6 | 10 | 14 |
| 32 | 4 | 24 | 72 | 9 | 54 | 16 | 2 | 12 |
| 12 | 27 | 6 | 20 | 45 | 10 | 28 | 63 | 14 |
| 9 | 15 | 21 | 15 | 25 | 35 | 21 | 35 | 49 |
| 24 | 3 | 18 | 40 | 5 | 30 | 56 | 7 | 42 |
| 32 | 72 | 16 | 4 | 9 | 2 | 24 | 54 | 12 |
| 24 | 40 | 56 | 3 | 5 | 7 | 18 | 30 | 42 |
| 64 | 8 | 48 | 8 | 1 | 6 | 48 | 6 | 36 |
While the total of 225 is indeed the same in all rows, columns and diagonals, there are a lot of repeated numbers here. Because the 3×3 sections here are based on multiples, most of the prime numbers p where 
are missing (except those less than 9: 2, 3, 5, and 7). But there are a lot of repeated numbers, particularly the highly composite numbers 4, 6, 12, 24, 36, 48 as a consequence of how it was constructed. It would not past muster as magic in the way we have been expecting for this article series.
I was more successful following the same algorithm as was successful for 5×5 squares where you would fill out sequential numbers from 1 to 81 along a diagonal, and obtained the magic sum 369 along all of its rows, columns and both diagonals:
| 47 | 58 | 69 | 80 | 1 | 12 | 23 | 34 | 45 |
| 57 | 68 | 79 | 9 | 11 | 22 | 33 | 44 | 46 |
| 67 | 78 | 8 | 10 | 21 | 32 | 43 | 54 | 56 |
| 77 | 7 | 18 | 20 | 31 | 42 | 53 | 55 | 66 |
| 6 | 17 | 19 | 30 | 41 | 52 | 63 | 65 | 76 |
| 16 | 27 | 29 | 40 | 51 | 62 | 64 | 75 | 5 |
| 26 | 28 | 39 | 50 | 61 | 72 | 74 | 4 | 15 |
| 36 | 38 | 49 | 60 | 71 | 73 | 3 | 14 | 25 |
| 37 | 48 | 59 | 70 | 81 | 2 | 13 | 24 | 35 |
Of course, the disadvantage here is that this is the only square you can produce by this method.
9×9 Squares by the Lo Shu Method
The Lo Shu square refers to the famous 3×3 square discovered some time in the 13th century (some accounts have this as early as the 2nd millenia BCE) by Yang Hui in China. He saw a turtle with an odd arrangement of spots on its back. I could go into the relationship of this particular arrangement of numbers of spots to Chinese mysticism and Feng Shui, but that would be too much of a digression. You can refer to this article in a Feng Shui blog for more detail on its mysticism. But among the things he noticed is that the numbers of spots added to 15 in all directions. The number of dots in each section became known as the famous 3×3 Lo Shu square.
4 9 2
3 5 7
8 1 6
There is another well-known way of producing 9×9 squares, and that is what has earned the name the Lo Shu Method. Unfortunately, you still obtain only one square from this. You begin with an arrangement of 81 numbers in this way, in numerical order by column from right to left:
| 73 | 64 | 55 | 46 | 37 | 28 | 19 | 10 | 1 |
| 74 | 65 | 56 | 47 | 38 | 29 | 20 | 11 | 2 |
| 75 | 66 | 57 | 48 | 39 | 30 | 21 | 12 | 3 |
| 76 | 67 | 58 | 49 | 40 | 31 | 22 | 13 | 4 |
| 77 | 68 | 59 | 50 | 41 | 32 | 23 | 14 | 5 |
| 78 | 69 | 60 | 51 | 42 | 33 | 24 | 15 | 6 |
| 79 | 70 | 61 | 52 | 43 | 34 | 25 | 16 | 7 |
| 80 | 71 | 62 | 53 | 44 | 35 | 26 | 17 | 8 |
| 81 | 72 | 63 | 54 | 45 | 36 | 27 | 18 | 9 |
Then, you take the first row (73, 64, 55, 46, 37, 28, 19, 10, and 1), and arrange them in order analogous to the 3×3 magic square (shown for comparison):
4 9 2 28 73 10
3 5 7 19 37 55
8 1 6 64 1 46
This creates a 3×3 sub-square that is used as a building block for the 9×9 square. You can see that 1, being the lowest number, remains in the bottom center; the 10, being the second lowest, occupies the same position as 2 for the original square. One then proceeds in numerical order for the remaining squares so that the new square has an arrangement analogous to the old arrangement, by ordering of the numbers. The number 73, the largest of this set of numbers, occupies the position held by 9 in the old square, the largest number in that square.
The second row, consisting of the numbers 74, 65, 56, 47, 38, 29, 20, 11, and 2, forms a 3×3 sub-square with the identical arrangement of numbers. In fact, you might notice that this new set is just the old set with 1 added to each element. Taking the small square we just made, we can add 1 and make the next sub-square:
28 73 10 29 74 11 19 37 55 - Add 1 to each element to make: -> 20 38 56 64 1 46 65 2 47
Similarly, we form new 3×3 sub-squares by adding 3, then 4, then 5, until we have nine 3×3 sub-squares to arrange.
28 73 10 29 74 11 30 75 12 31 76 13 32 77 14 19 37 55 20 38 56 21 39 57 22 40 58 23 41 59 64 1 46 65 2 47 66 3 48 67 4 49 68 5 50 33 78 15 34 79 16 35 80 17 36 81 18 24 42 60 25 43 61 26 44 62 27 45 63 69 6 51 70 7 52 71 8 53 72 9 54
You should notice that the bottom center of each sub-square is a single-digit number from 1 to 9. These are identifying marks which tell us where these sub-squares go. And they are arranged according to the positioning of those same numbers in the original 3×3 Lo Shu square. This is what you end up with:
| 31 | 76 | 13 | 36 | 81 | 18 | 29 | 74 | 11 |
| 22 | 40 | 58 | 27 | 45 | 63 | 20 | 38 | 56 |
| 67 | 4 | 49 | 72 | 9 | 54 | 65 | 2 | 47 |
| 30 | 75 | 12 | 32 | 77 | 14 | 34 | 79 | 16 |
| 21 | 39 | 57 | 23 | 41 | 59 | 25 | 43 | 61 |
| 66 | 3 | 48 | 68 | 5 | 50 | 70 | 7 | 52 |
| 35 | 80 | 17 | 28 | 73 | 10 | 33 | 78 | 15 |
| 26 | 44 | 62 | 19 | 37 | 55 | 24 | 42 | 60 |
| 71 | 8 | 53 | 64 | 1 | 46 | 69 | 6 | 51 |
Some squares are highlighted to illustrate the identifying marks I am referring to, and their attached sub-squares relative to each other. This is a fully magic square, with unique numbers from 1 to 81, and a magic total of 369.
We are still hobbled by the disadvantage that this is the only 9×9 square we can make using Lo Shu. There are more ways to make these squares, and Grogono claims that they can even be pan-magic. This will be covered in a later article.