Magic Squares of Squares Modulo 2^N
by Lee Morgenstern, January 2012.

I would like to make a contribution to the "Buell/Pech Magic Hourglass Modulo 2^N" competition.

In 1998, Duncan Buell's search found a magic hourglass modulo 2^46 (see [12]).  Then in 2006 Lucien Pech's search found a magic hourglass modulo 2^52 (see Dec. 23, 2006).

I can construct not only a magic hourglass, but a full 3x3 magic square of squares modulo 2^N, for any N you want.

Pick any positive values for a,b,c.

Then arrange the following expressions into a magic square.

 8(c+a)+1  8(c-a-b)+1  8(c+b)+1
8(c-a+b)+1    8c+1    8(c+a-b)+1
 8(c-b)+1  8(c+a+b)+1  8(c-a)+1

Since a number congruent to 1 (mod 8) is a quadratic residue modulo 2^N for any N, the above expressions form a magic square of squares modulo 2^N for any N.  You just have to find the integer square roots.

For example, pick

  a,b,c = 1,3,5.

Then

  49   9  65
  57  41  25
  17  73  33

is a magic square of squares modulo 2^N for any N. Magic sum = 123.

To find the square roots, solve the following six integer equations. [The other three entries are already squares]. Integer solutions are guaranteed to exist for any N.

  A^2 = p(2^N) + 65
  B^2 = q(2^N) + 57
  C^2 = r(2^N) + 41
  D^2 = s(2^N) + 17
  E^2 = t(2^N) + 73
  F^2 = u(2^N) + 33

Then use the square roots as follows.

   7^2  3^2  A^2
   B^2  C^2  5^2
   D^2  E^2  F^2

For example, for N = 7, we get the following magic square of squares modulo 2^7 = 128.

   7^2  3^2 31^2       49   9 961 (mod 128)   49  9 65
  21^2 13^2  5^2 ---> 441 169  25 --------->  57 41 25
  23^2 29^2 17^2      529 841 289             17 73 33

Here are some more examples with higher values of N.

N = 8

   7^2   3^2  33^2
  43^2  51^2   5^2
  23^2  29^2  17^2

N = 10

   7^2    3^2   33^2
  85^2  205^2    5^2
 233^2  157^2  111^2

N = 20

       7^2       3^2  115167^2
   10837^2  235827^2       5^2
  206569^2  126819^2  170095^2

N = 30

          7^2          3^2  230047265^2
  176171605^2   13395661^2          5^2
  204265751^2  208539805^2   96298897^2

Here are my own entries to the Buell/Pech Magic Hourglass modulo 2^N competition [with the addition that they are fully magic]

(mod 2^8)

21^2  23^2  61^2         185   17  137
33^2  25^2  47^2  ---->   65  113  161
37^2  55^2  51^2          89  209   41

(mod 2^10)

107^2  233^2  195^2         185   17  137
 33^2  231^2   47^2  ---->   65  113  161
 91^2   73^2  205^2          89  209   41

(mod 2^20)

246165^2  206569^2    4803^2         185   17  137
115167^2   43239^2  211921^2  ---->   65  113  161
184411^2  149065^2  235827^2          89  209   41

(mod 2^30)

 97763733^2  204265751^2  242225859^2
230047265^2   75016423^2    9649105^2  ---->  etc
126013531^2   74824119^2   13395661^2

(mod 2^40)

157937811861^2   54965098775^2  32506899773^2
 42182754783^2   47319656679^2   3748447279^2
128186134437^2  225560607159^2   8576538931^2

(mod 2^50)

231289259834987^2   72512802334441^2    3880797596989^2
 56582666075681^2  115496040573159^2  151728856185809^2
116969802223707^2   79390397807031^2  118738679260877^2

(mod 2^60)

207959822072299115^2  170501323084323095^2  193658664774528317^2
123229457133191647^2  180259481135392999^2   98364512992543791^2
211223202335215707^2  223570521906067895^2  225861670001206989^2

(mod 2^90)

 75203459322122514551553643^2   89064358005087038671628009^2  212694822416174402902168259^2
219077054094880999472512545^2  196302760081661098748061927^2  212510725734995190269295569^2
157075660995567914487459749^2   32945794187736625642620489^2  243922835234547628854450483^2

I have discovered a truly marvelous (and quick) construction method, but the width of this screen is too small to contain larger values of N.

Starting with a solution modulo 2^N, I can recursively compute a solution modulo 2^2(N-1).

So from a solution modulo 2^13, I compute a solution modulo 2^24 and then modulo 2^46 and then modulo 2^90.

Return to the home page http://www.multimagie.com