For cancellation of common terms, we have the following rules:
If a + k ≡ b + k (mod n) for any integer k, then a ≡ b (mod n)
If k a ≡ k b (mod n) and k is coprime with n, then a ≡ b (mod n)
Lastly, let the multiplicative inverse of a be denoted by a-1, then we have the following rules:
Existence of a multiplicative inverse: there exists an integer denoted a-1 such that aa-1 ≡ 1 (mod n) if and only if a is coprime with n.
If a ≡ b (mod n) and a-1 exists, then a-1 ≡ b-1 (mod n) (compatibility with multiplicative inverse)
If a x ≡ b (mod n) and a is coprime to n, the solution to this linear congruence is given by x ≡ a-1b (mod n)
In particular, if p is a prime number then a is coprime with p for every a such that 0 < a < p. Thus, a multiplicative inverse exists for all a that are not congruent to zero modulo p.
Some of the more advanced properties of congruence relations are the following:
A simple consequence of Fermat's little theorem is that if p is prime, then a-1 ≡ ap - 2 (mod p) is the multiplicative inverse of 0 < a < p. More generally, from Euler's theorem, if a and n are coprime, then a-1 ≡ aφ(n) - 1 (mod n).
Another simple consequence is that if a ≡ b (mod φ(n)), where φ is Euler's totient function, then ka ≡ kb (mod n) provided k is coprime with n
Wilson's theorem: p is prime if and only if (p - 1)! ≡ -1 (mod p)
Chinese remainder theorem: If x ≡ a (mod m) and x ≡ b (mod n) such that gcd(m, n) = 1, then x ≡ b mn-1m + a nm-1n (mod mn) where mn-1 is the inverse of m modulo n and nm-1 is the inverse of n modulo m
Lagrange's theorem: The congruence f (x) ≡ 0 (mod p), where f (x) = a0xn + ... + an (mod p) such that a0 ≠ (mod p) and p be prime, has at most n roots.
Primitive root modulo n: A number g is a primitive root modulo n if every number a co-prime to n is congruent to a power of g modulo n. That is, for every integer a co-prime to n, there is an integer k such that gk ≡ a (mod n). A primitive root modulo n exits if and only if n is equal to 2, 4, pk or 2pk where pk is a power of an odd prime number. If the primitive roots modulo n exist, then there are exactly φ(φ(n)) such primitive roots, where φ is the Euler's totient function.
Quadratic residue: An integer a is called a quadratic residue modulo n if it is congruent to a perfect square modulo n; i.e., if there exists an integer x such that x2 ≡ a (mod n). Otherwise, a is called a quadratic non-residue modulo n. For prime p, the Euler's criterion to check if a is or is not a quadratic residue is, as expressed using the Legendre symbol,
The properties of Legendre symbol and its variants can be used to efficiently check whether or not a number is a quadratic residue.
Euler's method for constructing the magic square is similar to De la Hire's method. It consists of breaking the magic square into two primary squares, which when added gives the magic square. As a running example, we will consider a 3×3 magic square. We can uniquely label each number of the 3×3 square by a pair of numbers as
1
2
3
4
5
6
7
8
9
αa
αb
αc
βa
βb
βc
γa
γb
γc
where each pairs of Greek and Latin alphabets, e.g. αa, are meant to be added together, i.e. αa = α + a. Here, (α,β,γ) = (0, 3, 6) and (a,b,c) = (1, 2, 3). An important general constraint to note here is that a Greek letter is paired with a Latin letter only once. Thus, the original square can now be split into two simpler squares:
α
α
α
β
β
β
γ
γ
γ
a
b
c
a
b
c
a
b
c
A magic square can be constructed by ensuring that the Greek and Latin squares are magic squares too. However, the Greek and Latin squares with just three unique terms are much easier to deal with than the original square with nine different terms. The row sum and the column sum of the Greek square will be the same, α + β + γ, if each letter appears only once in a given column and a row. Likewise, for the odd square, since α, β, and γ are in arithmetic progression, their sum is equal to the order of the square times the middle term, i.e. α + β + γ = 3 β. Thus, the diagonal sums will be equal if we have βs in the main diagonal and α, β, γ in the skew diagonal. Similarly, for the Latin square. The resulting Greek and Latin squares and their combination will be as below. Note that the Latin square is just a rotation of the Greek square with the corresponding letters interchanged. Substituting the values of the Greek and Latin letters will give the 3×3 magic square.
There are two basic ways of placing the four alphabets in the central 2×2 sub-square, not including the reflections, such that the letters are paired to their opposites along the column. Likewise there is only one way of placing the letters in the corners for a given central square (the complementary letters are placed at the opposite corners), such that the resulting square is pan-diagonal. Also there are just two basic ways of placing two complementary alphabets in the central square, not including rotations and reflections, which gives rise to pan-diagonal magic squares. Thus there 4 such basic Greek squares, as shown below. However, in order to ensure that the symbols are uniquely paired to each other, only the first two Greek squares can be used to construct a Latin square. Given a Greek square, a valid Latin square can be constructed by flipping it along the main diagonal or the skew diagonal, or rotating 90 degrees clockwise or anti-clockwise. This gives us 4 possible Latin squares from a given Greek square. Since we can pair one Latin square with any two Greek square, the total number of basic most-perfect 4×4 magic squares constructed this way are 2×4×2 = 16.
The "product" of two magic squares creates a magic square of higher order than the two multiplicands. Let the two magic squares be of orders M and N, such that M ≤ N, then the final square will be of order M × N. There will be N sub squares of M order which will also be a magic.
Divide the final checkerboard into N × N sub-checkers of M × M squares.
In the square N, reduce by 1 the value of all the numbers.
Multiply these reduced values by M × M. The results are reported in the boxes of each corresponding sub-checker of the final square.
The squares of the square M are added N × N times to the boxes of the final checkerboard.
In this method, the objective is to wrap a border around a smaller magic square which serves as a core. Let us consider the 3×3 square for example. Subtracting the middle number 5 from each number, we have 0, ± 1, ± 2, ± 3, and ± 4; and the magic constant will be zero. Putting the middle number 0 in the center cell, we want to construct a border such that the resulting square is magic. Let the border be given by:
u
a
v
b*
0
b
v*
a*
u*
Since the sum of each row, column, and diagonals must be a constant (which is zero), we have
a + a* = 0,
b + b* = 0,
u + u* = 0,
v + v* = 0.
Thus, it must be that if we have chosen a, b, u, and v, then we have a* = - a, b* = - b, u* = - u, and v* = - v. But how should we choose a, b, u, and v? We have the sum of the top row and the right column as
u + a + v = 0,
v + b + u* = 0.
Since 0 is an even number, there are only two ways that the sum of three numbers will yield an even number: 1) if all three were even, or 2) if two were odd and one was even. Since in our choice of numbers we only have two even non-zero number (± 2 and ± 4), it must be the case that the second statement is true: that two of the numbers are odd and one even.
The only way that both the above two equations can satisfy this parity condition simultaneously, and be consistent with the set of numbers we have, is when u and v are odd. Thus, taking u = 1 and v = 3, we have a = - 4 and b = -2. Hence, the finished square will be as in the left. Adding 5 to each number, we get the finished magic square.
The namesake of this method derives from mathematical game called medjig created by Willem Barink in 2006, although the method itself is much older. An early instance of a magic square constructed using this method occurs in Yang Hui's text for order 6 magic square. The LUX method to construct singly even magic squares is a special case of the medjig method, where only 3 out of 24 patterns are used to construct the medjig square.
The pieces of the medjig puzzle are 2×2 squares on which the numbers 0, 1, 2 and 3 are placed. There are three basic patterns by which the numbers 0, 1, 2 and 3 can be placed in a 2×2 square, where 0 is at the top left corner:
0
1
2
3
0
1
3
2
0
2
3
1
Each pattern can be reflected and rotated to obtain 8 equivalent patterns, giving us a total of 3×8 = 24 patterns. The aim of the puzzle is to take n2 medjig pieces and arrange them in an n × nmedjig square in such a way that each row, column, along with the two long diagonals, formed by the medjig square sums to 3n, the magic constant of the medjig square. An n × n medjig square can create a 2n × 2n magic square where n > 2.
Given an n×n medjig square and an n×n magic square base, a magic square of order 2n×2n can be constructed as follows:
Each cell of an n×n magic square is associated with a corresponding 2×2 subsquare of the medjig square
Fill each 2×2 subsquares of the medjig square with the four numbers from 1 to 4n2 that equal the original number modulo n2, i.e. x+n2y where x is the corresponding number from the magic square and y is a number from 0 to 3 in the 2×2 subsquares.
The sums of each medjig piece along the rows, columns and diagonals, denoted in italics, are:
1
0
1
5
2
3
3
2
4
3
1
0
1
5
3
2
4
3
3
2
2
0
2
4
3
1
5
3
3
1
Doubly even squares: The smallest medjig square is of order 2 with magic constant 6. While it is possible to construct a 2×2 medjig square, we cannot construct a 4×4 magic square from it since 2×2 magic squares required to "multiply" it does not exist. Nevertheless, it is worth constructing these 2×2 medjig squares. There exists 96 such 2×2 medjig squares. In the examples below, each 2×2 medjig square is made by combining different orientations of a single medjig piece.
Medjig 2×2
0
1
3
2
2
3
1
0
3
2
0
1
1
0
2
3
Medjig 2×2
0
1
2
3
3
2
1
0
1
0
3
2
2
3
0
1
Medjig 2×2
0
2
3
1
3
1
0
2
0
2
3
1
3
1
0
2
We can use the 2×2 medjig squares to construct larger even ordered medjig squares. One possible approach is to simply combine the 2×2 medjig squares together. Another possibility is to wrap a smaller medjig square core with a medjig border. The pieces of a 2×2 medjig square can form the corner pieces of the border. An example of an 8×8 magic square is constructed below by combining four copies of the left most 2×2 medjig squares given above:
Order 4
1
14
4
15
8
11
5
10
13
2
16
3
12
7
9
6
Medjig 4 × 4
0
1
3
2
0
1
3
2
2
3
1
0
2
3
1
0
3
2
0
1
3
2
0
1
1
0
2
3
1
0
2
3
0
1
3
2
0
1
3
2
2
3
1
0
2
3
1
0
3
2
0
1
3
2
0
1
1
0
2
3
1
0
2
3
Order 8
1
17
62
46
4
20
63
47
33
49
30
14
36
52
31
15
56
40
11
27
53
37
10
26
24
8
43
59
21
5
42
58
13
29
50
34
16
32
51
35
45
61
18
2
48
64
19
3
60
44
7
23
57
41
6
22
28
12
39
55
25
9
38
54
The next example is constructed by bordering a 2×2 medjig square core.
Order 4
1
14
4
15
8
11
5
10
13
2
16
3
12
7
9
6
Medjig 4 × 4
0
1
0
1
2
3
3
2
2
3
3
2
1
0
1
0
0
3
0
2
3
1
0
3
1
2
3
1
0
2
1
2
2
1
0
2
3
1
2
1
3
0
3
1
0
2
3
0
3
2
0
1
2
3
0
1
1
0
3
2
1
0
2
3
Order 8
1
17
14
30
36
52
63
47
33
49
62
46
20
4
31
15
8
56
11
43
53
21
10
58
24
40
59
27
5
37
26
42
45
29
2
34
64
32
35
19
61
13
50
18
16
48
51
3
60
44
7
23
41
57
6
22
28
12
55
39
25
9
38
54
Singly even squares: Medjig square of order 1 does not exist. As such, the smallest odd ordered medjig square is of order 3, with magic constant 9. There are only 7 ways of partitioning the integer 9, our magic constant, into three parts. If these three parts correspond to three of the medjig pieces in a row, column or diagonal, then the relevant partitions for us are
Once a 3×3 medjig square has been constructed, we can convert it into a 6×6 magic square. For example:
Order 3
8
1
6
3
5
7
4
9
2
Medjig 3 × 3
2
3
0
2
0
2
1
0
3
1
3
1
3
1
1
2
2
0
0
2
0
3
3
1
3
2
2
0
0
2
0
1
3
1
1
3
Order 6
26
35
1
19
6
24
17
8
28
10
33
15
30
12
14
23
25
7
3
21
5
32
34
16
31
22
27
9
2
20
4
13
36
18
11
29
An easy approach to construct higher order odd medjig square is by wrapping an smaller odd ordered medjig square with a medjig border, just as with even ordered medjig squares.
