Foxy asks whether it’s possible to have a 3*3 magic square all of whose entries are square integers. It’s fairly elementary to show that in a 3*3 magic square, the common sum is three times the middle entry. So let’s say the entries of the magic square go [a^2, b^2, c^2; d^2, e^2; f^2; g^2, q^2, h^2]; we want to have, for example, a^2 + h^2 = 2e^2.
This alone is very restrictive, since it requires (a^2, e^2, h^2) to be an arithmetic sequence, a sufficiently special situation that unless a = e = h, the next term in the sequence will never be a square (no, I can’t prove it; I’ve tried). So to find such magic squares whose entries are not all the same, it makes sense to start bashing through the Diophantine equation a^2 + h^2 = 2e^2.
First, the easy part: we can assume a, e, and h are coprime; otherwise, divide by their greatest common divisor. If e is even, then 2e^2 is divisible by 8, in which case it’s impossible for a and h to be odd since odd squares are equivalent to 1 mod 8, so that a and h are even and the three numbers are not coprime. So e is odd, from which it’s easy to show that so are a and h.
Now, when we have sums of two squares, the most natural environment to study divisibility is Z[i], the ring of Gaussian integers. We get (a + hi)(a – hi) = 2e^2. As a and h are odd, a (+/-) hi is not divisible by 2, so both a + hi and a – hi must be divisible by 1 + i. That condition isn’t a problem: (a + hi)/(1 + i) = (a + hi)(1 – i)/2 = (a + h)/2 + i(h – a)/2, and similarly (a – hi)/(1 – i) = (a + h)/2 + i(a – h)/2.
It now makes sense to write x = (a + h)/2, y = (a – h)/2. Conversely, a = x + y and h = x – y; as a and h are odd, this means that x and y have opposite parities. Since dividing once by 1 + i and once by 1 – i factors out 2 on the right-hand side, this turns the equation into (x + iy)(x – iy) = e^2, or x^2 + y^2 = e^2.
Here is where things get nightmarishly complicated. Any common factor of x and y divides a, e, and h, so x, y, and e are coprime. Consider the primes of Z[i] that divide x + iy; none can be in Z because that would imply a common factor of x and y. But all primes in Z[i] that have no associate in Z have norm equivalent to 1 or 2 mod 4, where here 1 + i is impossible because 1 + i divides x + iy iff x and y have the same parity. So right off the bat, e is the product of primes equivalent to 1 mod 4.
Further, each distinct prime factor after the first of e gives exactly two choices of x and y. To see what I mean, first consider the case when e is prime. Then e = (r + is)(r – is), so e^2 = (r + is)(r – is)(r + is)(r – is). There are two ways of grouping them into x and y, but the one that sends the first two to x + iy factors e^2 as e*e, i.e. x = e and y = 0. Hence there’s only one way, the one that sends (r + is)^2 to x + iy. If e is divisible by an additional prime and breaks as (r1 + is1)(r1 – is1)(r2 + is2)(r2 – is2) then once the decision to send (r1 + is1)^2 to x + iy has been made, it’s possible to send (r2 + is2)^2 or (r2 – is2)^2 to x + iy. This easily generalizes to further prime factors, but not to repeated factors.
This means that e can’t be prime because then the eight elements of the magic square around it will all be either a^2 or h^2, making it impossible for the other magic square conditions to hold. Now, using capital letters to denote squares, we get that the magic square is [A, B, 3E - A - B; 4E - 2A - B, E, 2A + B - 2E; A + B - E, 2E - B, 2E - A].
The above considerations show that E must be divisible only by primes equivalent to 1 mod 4 because it’s sandwiched between A and 2E – A. But by the same token, 2E – A is sandwiched between 4E – 2A – B and B, so it must similarly be divisible only by primes equivalent to 1 mod 4; similar considerations apply to A, which is sandwiched between 2A + B – 2E and 2E – B.