Residues and quadratic residues

1. Congruence of magic squares

Let n≥1. Two integral squares are congruent modulo n when their corresponding entries are congruent. For magic squares, the form m(E,x,y) turns this condition exactly into congruence of the three coordinates.

Proof

If the coordinates are pairwise congruent, then all entries are congruent because each is an integral linear combination of E,x,y. Conversely, E is the central entry, x=A−E, and y=G−E. Entrywise congruence therefore immediately gives coordinate congruence. The modulus need not be prime.

The general form m(E,x,y) and its classification proof →

2. Squares modulo n

Let Sq(n) denote the full image of r↦r² in ℤ/nℤ. This definition includes zero and applies to composite n. The term “quadratic residue” below is reserved for a nonzero class modulo an odd prime.

The first four rows follow by squaring a complete residue system. Modulo 8 one may instead observe that an odd square is 1, while an even square is 0 or 4. The list modulo 24 is obtained by combining the conditions modulo 8 and modulo 3.

3. Restrictions modulo 4 and 3

Assume that all nine entries of an integral magic square are squares. To distinguish the central entry from its root, write the center as E=e²:

Proof modulo 4

The entries A=e²+x and J=e²−x both lie in Sq(4)={0,1}. If e²≡0, the only class x for which both x and −x are squares is 0. If e²≡1, checking x=0,1,2,3 again leaves only x=0. Hence 4∣x. Applying the same argument to G=e²+y and C=e²−y gives 4∣y.

Proof modulo 3

Every entry is congruent to 0 or 1. Each row sums to 3e²≡0. Three elements of {0,1} sum to 0 modulo 3 only when they are all 0 or all 1. Thus each row has one divisibility color. The same condition on the columns forces all three rows to have the same color: the entire square consists either of zeros or of ones modulo 3. In particular A≡E≡G, so 3∣x and 3∣y.

Since 3 and 4 are coprime, 12∣x,y. This is a necessary condition; the converse is false.

4. Primitive squares and modulus 24

Call an integral square primitive when the gcd of its nine entries is 1. For a magic square this is equivalent to gcd(E,x,y)=1.

Proof

If e is even, then e², x, and y are divisible by 4, so all nine entries are divisible by 4, contradicting primitivity. If 3∣e, the preceding proof shows that every entry is divisible by 3; because the entries are squares, each is in fact divisible by 9. This is again a contradiction. Hence e is coprime to 6.

We already know that x,y are divisible by 12, so every entry is congruent to e² modulo 12. Thus the root of every entry is odd and not divisible by 3. The square of every integer coprime to 6 is congruent to 1 modulo 24. Hence all entries are 1 modulo 24. Finally, x=A−E and y=G−E are differences of two such entries and are therefore divisible by 24.

5. Exact classification modulo 5

Modulo 5, squares are 0, 1, or 4. The complete residue check has a short hand proof and gives exactly nine feasible triples:

Proof that the list is complete

If e≠0, then e² is 1 or 4. For either value, the condition e²+x,e²−x∈{0,1,4} permits only x=0; the pair e²±y similarly gives y=0. If e=0, the opposite pairs give x,y∈{0,±1}. Substitution into the four side entries e²±x±y excludes the case in which x and y are both nonzero. This leaves (0,0), (±1,0), and (0,±1), all of which indeed give only square classes. Thus the list is necessary and sufficient modulo 5.

In the primitive case, the class (0,0,0) with e≡0 is impossible because then every square entry is divisible by 25. Therefore either 5∤e and 5∣x,y, or 5∣e and exactly one of x,y is ±1 while the other is 0 modulo 5.

6. Quadratic residues modulo a prime

Let p be an odd prime and p∤a. The Legendre symbol (a/p) is 1 when a is a nonzero square modulo p and −1 otherwise. Euler's criterion also proves multiplicativity:

Proof of Euler's criterion

By Fermat's little theorem, a^((p−1)/2) is a root of z²=1 and is therefore ±1. Every nonzero square a=b² gives b^(p−1)=1. There are exactly (p−1)/2 nonzero square classes, while the polynomial X^((p−1)/2)−1 has at most (p−1)/2 roots. Its roots are therefore exactly the nonzero squares, and the value on every other class is −1. The product formula follows by raising ab to the same power.

The first law follows directly from Euler's criterion. For the second, apply Gauss's lemma to 2. Among 2,4,…,p−1, the number N of least positive representatives exceeding p/2 is (p−1)/2−⌊p/4⌋. Replacing these representatives by their negatives permutes the absolute values 1,…,(p−1)/2; cancelling the factorial gives (2/p)=(−1)ᴺ. For p≡1,3,5,7 mod 8, N is respectively even, odd, odd, even, which proves the formula.

7. Prime divisors of a corner entry

Proof

After a rotation, take this entry to be A=a². The general form gives f²+h²=2a². Let q∣a and q≡3 mod 4. Then −1 is not a quadratic residue modulo q. From f²+h²≡0 it follows that q∣f and q∣h; otherwise f/h or h/f would be a square root of −1.

The congruences A=e²+x≡0 and F=e²+x+y≡0 give y≡0 and x≡−e². Hence the whole square has the following form modulo q:

If q∣e, all nine square entries are divisible by q², contradicting primitivity. Thus e is invertible modulo q. Since 2e² is a square, 2 is a quadratic residue: (2/q)=1. The supplementary law leaves q≡1 or 7 mod 8; together with q≡3 mod 4, only q≡7 mod 8 remains.

8. What these conditions do not prove

All congruences obtained here are necessary local conditions. They quickly exclude impossible coordinates and factorizations, but they do not construct a rational or integral point of the original system. Solvability modulo many integers is not by itself a proof that a magic square of squares exists.

The next arithmetic layer is representation as a sum of two squares and factorization in ℤ[i]. That is where local restrictions on prime divisors become constructive norm identities.