# A theorem about primes proved on a chessboard

> An annotated edition of this paper on Fermat's Library, where scientists and readers explain its ideas, equations and history in the margins. Annotated edition: https://fermatslibrary.com/s/a-theorem-about-primes-proved-on-a-chessboard

- **Authors:** Loren C. Larson
- **Topic:** Mathematics
- **Original:** https://s3-us-west-1.amazonaws.com/fermatslibrary/uploads%2F1467443116716-pdcri04ey0y95ura-411abb82f8b5f2000834af45ddcff8bb%2FLar1977.pdf
- **Pages:** 6
- **Annotations:** 13 comments in 11 threads
- **Featured:** Fermat's Library Journal Club
- **Annotated edition:** https://fermatslibrary.com/s/a-theorem-about-primes-proved-on-a-chessboard

## Annotations

### Annotation 1 (page 1)

Beside the passage: “An elementary treatment of a class of solutions to the n-queens problem leads to a proof of Fermat's theorem on primes which are sums of two squares.”

**Annotation** by Luís Batalha (2016-09-04):

> The **n-queens problem** is a generalization of   the 8-queens problem published by chess composer Max Bezzel in 1848. Max Bezzel, whose main occupation was creating chess problems, challenged people to find a way to place 8 non-attacking queens on an 8x8 chessboard.
>
> ![Max Bezzel](http://www.schach-chess.com/media/deutsch/Schachgeschichte/Schachaufgaben/schachspieler-max-bezzel.jpg)
>
> Franz Nauck was the first person to publish solutions to the 8-queens problem in 1850 and also generalized the puzzle to the n-queens problem.
>
> Many famous mathematicians including Gauss and Dijkstra worked on the problem and proposed various methods to find solutions.
>
> These days the 8-queens problem is most often encountered as an exercise in introductory artificial intelligence programming courses. In fact, the n-queens problem is one of the benchmarks by which backtracking algorithms have been compared.

**Reply** by João Rico (2016-09-06):

> This reminds me of a boardgame, played with 8 queens on a chess board, that was part of the National Mathematical Games Championship when I was in high school (in Portugal). It's called Game of the Amazons [1], and each player owns 4 queens. They take turns moving one of their queens to a valid position and then placing a stone within "sight" of this queen. Stones block cells and the first player to not be able to move any of his queens loses. Quite dynamic, and fun to devise successful strategies.
>
> Again, cool paper!
>
> [1] https://en.wikipedia.org/wiki/Game_of_the_Amazons

### Annotation 2 (page 1)

Beside the passage: “An elementary treatment of a class of solutions to the n-queens problem leads to a proof of Fermat's theorem on primes which are sums of two squares.”

**Annotation** by Luís Batalha (2016-09-04):

> Fermat's theorem on sums of two squares says that an odd prime $p$ is expressible as
>
> $$p = x^2 + y^2$$
>
> with $x$ and $y$ integers, if and only if
> $$
> p \equiv 1 \pmod{4}
> $$
>
> which is the same thing as saying if and only if $p=4k+1$, where $k \in \mathbb{N}$.
>
> The prime numbers for which this is true are called Pythagorean primes.
> For example, the primes 5, 13, 17, 29, 37 and 41 are all congruent to 1 modulo 4, and they can be expressed as sums of two squares in the following ways:
>
> $$
> 5 = 1^2 + 2^2 \\
> \quad 13 = 2^2 + 3^2\\
> \quad 17 = 1^2 + 4^2
> $$
>
> A one-sentence proof of Fermat's theorem on sums of two squares has already been discussed on [Fermat's Library](http://fermatslibrary.com/p/eea4212e).

### Annotation 3 (page 2)

Beside the passage: “The additive group of integers will be denoted by Z, and Z,, = {1 2, 3, .. ., n} will denote the cyclic group of order n, having the operation of addition modulo n. If x is an integer, [x] will denote that integer between 1 and n inclusive which is congruent to x modulo n. (Since we will be working on an n x n …”

**Annotation** by Luís Batalha (2016-09-04):

> The set of all integers which have the same remainder when divided by $q$ is called the $\textbf{congruence class}$ of a modulo $q$. The collection of all congruence classes modulo q is called the $\textbf{set of integers modulo q}$, denoted by $\bar Z_q$
>
> For instance, the set of integers modulo 3 $\bar Z_3$ has three elements which we will call {$\bar1,\bar2,\bar3$}. Don't confuse these elements with the regular integers 1,2,3.  As an example, $\bar 2$ denotes the set of all integers which have remainder 2 when divided by 3:  {2,5,8,...}
>
> Now we can perform standard modular arithmetic to determine the addition table for this set. We find that $\bar 1 + \bar 1= \bar 2 $ (mod 3), and $\bar 2 + \bar 2= \bar 4= \bar 1$ (mod 3).
>
> It's also easy to see that $\bar Z_q$ is a cyclic group of order q: $Z_q=\{g^0,g^1,g^2,g^3,...,g^{q-1} \}=\{\bar 1,\bar 2,\bar 3,\bar 4,...,\bar q \}$, where $g^1 \cdot g^2 =g^3 $.

### Annotation 4 (page 2)

Beside the passage: “FIGURE 1”

**Annotation** by Tony Chen (2016-09-07):

> the only symmetrical solution!

**Reply** by Luís Batalha (2016-09-07):

> Tony it is indeed a symmetric solution but it's not unique. As we discuss at the end of page 73, the number of regular solutions for p=13 is $p(p-3)= 130$, including many symmetric solutions (both doubly symmetric - invariant under 90 degree rotations - and just symmetric - invariant under 180 degree rotations ).

### Annotation 5 (page 2)

Beside the passage: “It is important to observe that every regular solution can be expressed in the form (n, c) + ((1, d)) for some c, d E Z,n. For, suppose that (a, b) + ((s, t)) is a regular solution. We know that k (s, t) is a generator of ((s, t)) whenever k is an integer relatively prime to n. (Geometrically, the solution can be …”

**Annotation** by Luís Batalha (2016-09-06):

> This result is not obvious, particularly for someone without any knowledge of group theory.
>
> I'll give a motivation of why this might be true by showing an example for $\bar Z_6 $.
>
> In $\bar Z_6 = \{1, 2, 3, 4, 5,6\}$, the generators of $\bar Z_6$ are the integers
> $k$ between 1 and 6 such that gcd (6, k) = 1 (in other words 6 and k are relatively primes) that is 1, 5. We can verify that, $\langle 1\rangle  = \{1, 2, 3, 4, 5,6\}$ and $\langle 5\rangle  = \{5, 4, 3,2,1,6\} = \{1, 2, 3, 4, 5,6\}$ but $\langle 6\rangle  = \{6\}$, $\langle 3\rangle  = \{3,6\}$, $\langle 4\rangle  = \{4,2,6\}$, $\langle 2\rangle  = \{2,4,6\}$.
>
>
> If you want to see a proof of this theorem you can go [here](https://www.math.lsu.edu/~adkins/m4201/cyclicgroup.pdf).

### Annotation 6 (page 2)

Beside the passage: “It is important to observe that every regular solution can be expressed in the form (n, c) + ((1, d)) for some c, d E Z,n. For, suppose that (a, b) + ((s, t)) is a regular solution. We know that k (s, t) is a generator of ((s, t)) whenever k is an integer relatively prime to n. (Geometrically, the solution can be …”

**Annotation** by Luís Batalha (2016-09-06):

> Since we are going to place n queens in an nxn board, every queen needs to be in a different column, otherwise at least two of the queens would be attacking each other.  This means that $s$ has to be able to "generate" all the different possibilities for the columns: {1,2,...,n}.
>
> As we have seen before, for $s \in \bar Z_n$, $s$ is a generator of $\bar Z_n$ if and only if n and s are relatively prime. We conclude that s and n need to be relatively prime!
>
> At the same time, according to the [Bézout's identity](https://en.wikipedia.org/wiki/B%C3%A9zout%27s_identity), for 2 numbers n and s that are relatively prime there exist integers r and y such that $rs + yn = 1 \leftrightarrow rs\equiv 1 \text{ (mod n)} $.

### Annotation 7 (page 2)

Beside the passage: “It is important to observe that every regular solution can be expressed in the form (n, c) + ((1, d)) for some c, d E Z,n. For, suppose that (a, b) + ((s, t)) is a regular solution. We know that k (s, t) is a generator of ((s, t)) whenever k is an integer relatively prime to n. (Geometrically, the solution can be …”

**Annotation** by Luís Batalha (2016-09-06):

> For the example in Figure 1, since $n=13$ if we choose $r=2$, $(13,3) + \langle (1,8) \rangle$ gives:
>
> $$
> (13,3)+(2,3)=(2,6) \\
> (13,3)+(4,6)= (4,9)\\
> (13,3)+(6,9)=(6,12)\\
> (13,3)+(8,12)= (8,2)\\
> (13,3)+(10,2)= (10,5)\\
> (13,3)+(12,5)= (12,8)\\
> (13,3)+(1,8)= (1,11)\\
> (13,3)+(3,11)= (3,1)\\
> (13,3)+(5,1)= (5,4)\\
> (13,3)+(7,4)= (7,7)\\
> (13,3)+(9,7)= (9,10)\\
> (13,3)+(11,10)= (11,13)\\
> (13,3)+(13,13)= (13,3)\\
> $$
>
> If you check the positions generated above are exactly the solution for the 13-queens problem in Figure 1.

### Annotation 8 (page 3)

Beside the passage: “We are interested in finding conditions on c and d so that (n, c) + ((1, d)) will be a solution to the n-queens problem. It is easy to see that a necessary condition is that d be relatively prime to n (so that each row be occupied); but this is not sufficient, since, for ex`ample, d = 1 violates the diagonal …”

**Annotation** by Luís Batalha (2016-09-06):

> Note that $(n,c) + \langle (1,d) \rangle $ generates positions of the form $(n+i,c+id)$. Since $n+i$ is equal to $i$ (mod n), the positions of the queens can be written as $(i,c+id)$. $n$ is the size of the chessboard, so if we add $i$ and $n$ we will just be looping back to the original position $i$

### Annotation 9 (page 3)

Beside the passage: “Suppose that p is an odd prime number and that u and v are positive integers such that u2 + v2= p. Choose an integer r so that r(u, v) = (1, d) for some d E Z,. Then r2u2+ r2v2 = r2p, 12+ d2 0 (mod p) and therefore d2- 1(mod p). Thus (d + 1)(d - 1)d21 - 2 (mod p). It follows that d - 1, d and d + 1 are each relatively …”

**Annotation** by Luís Batalha (2016-09-06):

> As seen before two numbers a and b are relatively prime if and only if there exists an integer y such that by ≡ 1 (mod a).
>
> For d:
>
> $d^2 \equiv - 1 \leftrightarrow d(-d) \equiv 1 \text{(mod p)}  $
>
> and so $y = -d$
>
> For d +1 :
>
> $(d+1)(d-1) \equiv -2 \leftrightarrow (d+1)\frac{d-1}{-2} \equiv 1 \text{(mod p)}  $
>
> and so $y = \frac{d-1}{-2}$
>
> Finally for d -1 :
>
> $(d+1)(d-1) \equiv -2 \leftrightarrow (d-1)\frac{d+1}{-2} \equiv 1 \text{(mod p)}  $
>
> and so $y = \frac{d+1}{-2}$

### Annotation 10 (page 3)

Beside the passage: “c + ( ) d (mod p)”

**Annotation** by Luís Batalha (2016-09-06):

> $(p,c)+ \langle(1, d)\rangle = (p + i, c+ id)$ where $i=1,2,...,n$. If we want to have a queen in the center position we end up with two equations for the coordinates
>
> $$
> p+i = \frac{p+1}{2} \leftrightarrow p+2i = 1 \leftrightarrow 2i \equiv 1 \text{(mod p)} \\
> c+id = \frac{p+1}{2} \leftrightarrow 2c + 2id = p+1 \leftrightarrow 2c+2id \equiv 1 \text{(mod p)}
> $$
>
> Combining the two equations
>
>
> $$
> 2c+d \equiv 1 \text{(mod p)}
> $$

### Annotation 11 (page 5)

Beside the passage: “Proof. We know that regular solutions have the form (p, c) + ((1, d)). Clearly we do not get a solution when d is p, p - 1, or 1. But any of the other p - 3 possibilities for d, in Zp, will produce regular solutions, since in these cases d - 1, d, and d + 1 will each be relatively prime to p. Since c can take on any …”

**Annotation** by Luís Batalha (2016-09-06):

> If $d=p$, d is obviously not relatively prime to p.
>
> If $d=p-1$, $d+1=p$ is obviously not relatively prime to p.
>
> And finally if $d=1$, as we have seen above in page 71, we violate the diagonal requirements.

## Full text

Extracted from the PDF. [Annotation N] marks where each annotation above sits.

#### Page 1

A Theorem about Primes

Proved on a Chessboard

An elementary treatment [Annotation 1] of a class of solutions to the n-queens problem leads to a proof of Fermat's theorem on primes which are sums of two squares. [Annotation 2]

LOREN C. LARSON St. Olaf College

Arrange queens on a 13 x 13 chessboard according to the following rule: place a queen on the center square and from it locate others by making successive (2, 3) movements - two squares to the right and three squares upward (top and bottom edges are identified, as well as right and left). The resulting queen placement (FIGURE 1) shows exactly one queen in each row and column, and no two on the same diagonal; as such, it is a solution to the n-queens problem (to place n nonattacking queens on the n x n chessboard) for n = 13. The solution is distinguished from other solutions in two respects: (i) it is regular, meaning that the queens are located at successive (s, t) movements from each other, for some integers s and t (a more precise definition will be given later), and (ii) it is doubly symmetric, meaning that it is invariant under a 900 rotation of the board about the center square. More generally, suppose that u and v are positive integers and u2+ v2 is an odd prime p. We will show that queens located at successive (u, v) movements from a queen on the center square of the p x p chessboard give a regular, doubly symmetric solution to the p-queens problem. Conversely, we will see that regular, doubly symmetric solutions to the p-queens problem, for p a prime, yield positive integers u and v such that u2+ v2 =p. In the final section we will show by a simple combinatorial argument that there is a regular, doubly symmetric solution to the p-queens problem whenever p is a prime of the form 4k + 1. Combining this result with the preceding implication gives a proof of Fermat's Two-Square Theorem: primes of the form 4k + 1 can be expressed as the sum of two squares.

This proof of Fermat's theorem is both elementary and concrete. It avoids the usual first step of knowing that - 1 is a quadratic residue modulo p when p is a prime of the form 4k + 1. Moreover it uses the chessboard to provide a specific geometrical setting for illustrating and interpreting abstract concepts usually first encountered in an introductory abstract algebra course. The ideas on which this approach is based are scattered throughout references [1] and [2]. The chief insight - relating Fermat's Two-Square Theorem to the n-queens problem - is due to George Polya.

This content downloaded from 129.128.216.34 on Wed, 13 Nov 2013 15:26:47 PM

All use subject to JSTOR Terms and Conditions

#### Page 2

Preliminaries

The additive group of integers will be denoted by Z, and Z,, = {1 2, 3, .. ., n} will denote the cyclic group of order n, having the operation of addition [Annotation 3] modulo n. If x is an integer, [x] will denote that integer between 1 and n inclusive which is congruent to x modulo n. (Since we will be working on an n x n chessboard, there will be no need to write [x],n to indicate the modulus.) There is little danger of confusion in using [x] to denote an element of Z and also an element of Zn, for the context will make the intention clear. For convenience we will identify the chessboard with the group Zn x Zn. Geometrically, the group element (i,j) represents the square in the ith column (from the left) and the jth row (from the bottom). A regular solution to the n-queens problem is a solution in which the queens are located on the squares (represented by the elements) of the coset (a, b) + ((s, t)) for some (a, b), (s, t) E Zn x Zn where ((s, t)) is the cyclic subgroup of Zn x Zn generated by (s, t). In this case, we will say that (a, b) + ((s, t)) is a regular solution.

FIGURE [Annotation 4] 1

It is important to observe that every regular solution can be expressed in the form (n, c) + ((1, d)) for some c, d E Z,n. For, suppose that (a, b) + ((s, t)) is a regular solution. We know that k (s, t) is a generator of ((s, t)) whenever k is an integer relatively prime to n. (Geometrically, the solution can [Annotation 5] be generated by many different regular movements.) Since s must be relatively prime to n in order that each column be occupied (similarly for [Annotation 6] t and the rows), there exists an integer r, relatively prime to n, such that rs 1 (mod n). For this r, r(s, t) is of the form (1, d) for some d E Z,n. Thus ( (s, t))= (r(s, t)) = ((1, d)). Since a queen occurs in column n, we have, for -some c E Zn, (n, c) E (a, b) + ((s, t)), or equivalently, (n, c) E (a, b) + ((1, d)). It follows, then, that (a, b) ? ((s, t)) = (n, c) ? ((1, d)). (For the [Annotation 7] example in the introduction, c =3 and d = 8.)

70~ IIIII x

This content downloaded from 129.128.216.34 on Wed, 13 Nov 2013 15:26:47 PM

All use subject to JSTOR Terms and Conditions

#### Page 3

We are interested in finding conditions on c and d so that (n, c) + ((1, d)) will be a solution to the n-queens problem. It is easy to see that a necessary condition is that d be relatively prime to n (so that each row be occupied); but this is not sufficient, since, for ex`ample, d = 1 violates the diagonal requirements. Notice that two queens lie on the same rising diagonal (diagonals having slope 1) if the differences (in Z) of their coordinates are the same, and on the same falling diagonal if the sums (in Z) of their coordinates are equal. For the coset above, queens are located on the [Annotation 8] squares (i, [c + id]) for i = 1, 2,..., n. Since i + [c + id] c + i(d + 1) (mod n), the sums of these coordinates will be different provided that d + 1 is relatively prime to n. Similarly, since [c + id] - i c + i(d - 1) (mod n), the differences will be distinct if d - 1 is relatively prime to n. Thus, a sufficient condition for (n, c) + ((1, d)) to be a solution is that d - 1, d and d + 1 each be relatively prime to n. We leave it as an exercise to prove that this condition is also necessary. (Warning: this converse is not immediate since two of the coordinate sums (differences) may be equal in 4, but unequal in Z.) We summarize the preceding discussion in the following formal lemma:

FUNDAMENTAL LEMMA. The placement (n, c) + ((1, d)) is a solution to the n-queens problem if and only if d - 1, d and d + 1 are each relatively prime to n.

An immediate corollary helps explain why the 8-queeens problem is so much more difficult than the 7-queens problem, which most beginners solve very quickly. We will state and prove it here, even though we will not need it (nor, for that matter, the "only if" part of the Fundamental Lemma) for the main result of the paper.

COROLLARY. There exists a regular solution to the n-queens problem if and only if n ? 1 (mod 6).

Proof We have seen that regular solutions have the form (n, c)+((I, d)) for some c and d. If n + 1 (mod 6) we get a regular solution by taking d = 2 (ordinary knight moves). However, for n 0, 2, 3, 4 (mod 6) we cannot have regular solutions since one of d - 1, d, d + 1 is divisible by 3 and at least one of them is even.

From Number Theory to the Chessboard

Suppose that p is an odd prime number and that u and v are positive integers such that u2 + v2= p. Choose an integer r so that r(u, v) = (1, d) for some d E Z,. Then r2u2+ r2v2 = r2p, 12+ d2 0 (mod p) and therefore d2- 1(mod p). Thus (d + 1)(d - 1)d21 - 2 (mod p). It follows that d - 1, d and d + 1 are each relatively prime to p and therefore (1, d) movements will [Annotation 9] generate a regular solution. The center square has coordinates ((p + 1)/2, (p + 1)/2), so in order that (p, c) + ((1, d)) have a queen on the center square, it is necessary and sufficient that

c + ( ) d (mod [Annotation 10] p)

or

(1) 2c+d 1 (modp).

Suppose that c is so determined. Now under a 900 clockwise rotation, the queen located on the square (i, [c + id]) will rotate to the square ([c + id], [1 - iJ). But this square is occupied by a queen in (p, c)+((1, d)), since [c + [c + id]d] = [c + cd + id2] = [c(1 + d)- il = [(1- d)12)(1 + d)- i= [(1 - d2)/2)- il = [1 - il. Therefore the solution is doubly symmetric.

From the Chessboard to Number Theory

Suppose now that p is a prime and that (p, c) + ((1, d)) is a regular, doubly symmetric solution to the p-queens problem. Since the 2 x 2 board does not admit such a solution, the prime p is odd. Observe that a queen is located on the center square, since queens off the center come in sets of four,

VOL. 50, NO. 2, MARCH 1977 71

This content downloaded from 129.128.216.34 on Wed, 13 Nov 2013 15:26:47 PM

All use subject to JSTOR Terms and Conditions

#### Page 4

these located at quarter turns from each other (rotational symmetry). (Incidentally, this shows that p has the form 4k + 1.) From among all the queens on the board, pick one that is closest to the queen on the center square; suppose it is located at a (u, v) movement from the center square. Because of rotational symmetry we may suppose that u and v are positive. (Other closest queens will be located at (v, - u), (- u, - v), and (- v, u) movements from the center square.) Because the solution is regular, no two queens can be located closer together than these two queens. (To get from one queen to another requires an i(l, d) E Zp X Zp movement for some integer i, and this same movement could be made from the center square.) The center queen and the two queens located at (u, v) and (v, - u) movements from it, occupy three vertices of a square region; the fourth vertex of this square is occupied by a queen in the solution since it is a (u, v) + (v, - u) E Zp x Zp movement from the center (and each summand is a multiple of a (1, d) movement). Furthermore, no queen in the solution will be located in the interior of this square (since that would violate our choice of u and v). In the same way, every queen on the board can be associated with a square region whose vertices are given by its own position and those queens at (u, v), (v, - u) and (u, v) + (v, - u) movements from it. It is understood that left and right, top and bottom edges are identified, so that squares which overlap an edge are continued on the opposite side (see FIGURE 2). In this way the p x p chessboard is dissected into p regions (one for each queen) each of equal area. Since the total area of the chessboard is p2, each individual square has an area equal to p. It follows that the side length of each square is \/p, and therefore, from the Pythagorean theorem, that p = u2+ V2.

FIGURE 2

72 MAHMTC MAGAZIN

This content downloaded from 129.128.216.34 on Wed, 13 Nov 2013 15:26:47 PM

All use subject to JSTOR Terms and Conditions

#### Page 5

It may be instructive to point out that the queen positions in a regular solution are part of a lattice that extends to the entire plane. This can be seen algebraically by first observing that the mapping k: Z x Z -> Z x Zn defined by ((x, y))4 = ([x], [y]) is a group homomorphism. Let H be the cyclic subgroup of Z x Z generated by (u, v). Then the elements of (HO)4f` may be interpreted geometrically as the positions of the queens obtained by tiling the entire plane with copies of the chessboard having queens located on the squares Ho. However, (HO)O` is a subgroup of Z x Z, and therefore it is a lattice of dimension two, having a fundamental region of area equal to the absolute value of the determinant of the matrix gotten by expressing the lattice basis in terms of the canonical basis of Z x Z. Now an arbitrary regular solution to the n-queens problem is a translation of Ho for some cyclic group H of Z x Z, and this corresponds to the same translation in Z x Z of the subgroup (H4)f '.

Fermat's Two Square Theorem In order to prove Fermat's result, we need to show that there is a regular, doubly symmetric solution to the p-queens problem whenever p is a prime of the form 4k + 1. To do this, we will count the total number of regular solutions for the p x p board in two different ways.

LEMMA. The number of regular solutions to the p-queens problem, where p is a prime, is p(p - 3).

Proof. We know that regular solutions have the form (p, c) + ((1, d)). Clearly we do not get a solution when d is p, p - 1, or 1. But any of the other p - 3 possibilities for d, in Zp, will produce regular solutions, since in these cases [Annotation 11] d - 1, d, and d + 1 will each be relatively prime to p. Since c can take on any of p values, the total number of regular solutions is p(p - 3).

A second way of counting the regular solutions is to partition them into three classes, depending upon their symmetry - doubly symmetric, symmetric (invariant under a 1800 rotation but not a 900 rotation), or nonsymmetric (no symmetry). The symmetries of the square consist of four reflections and four rotations, and these form a group G, under composition. If x denotes a regular solution and U E G, the regular solution which results from x by applying the transformation U will be denoted by xU. Two regular solutions x and y are essentially the same if and only if there exists a U E G such that xU = y. This is an equivalence relation on the set of all regular solutions. The equivalence class of a solution x consists of all those solutions that can be obtained from x by rotation and reflection. For each regular solution x, let HIdenote the set of all symmetries of x; that is, HI = {U E G I xU = x}. HIis a subgroup of G. Furthermore, if U, V E G, xU = xV if and only if xUV- = x, and this happens if and only if UV- E HI-. It follows that the number of elements in the equivalence class of x is equal to the index of HIin G, and this is 2, 4, or 8 depending upon whether x is doubly symmetric, symmetric, or nonsymmetric respectively. Thus we have the following lemma:

LEMMA. The number of regular solutions to the n-queens problem is 2x + 4y + 8z, where x, y, z are, respectively, the number of essentially different doubly symmetric, symmetric, and nonsymmetric regular solutions to the n-queens problem.

Now suppose that p is a prime of the form 4k + 1. Combining the results of the preceding two lemmas, we know that p(p -3) = 2x + 4y + 8z. Since, in this equation, p 1 (mod 4), it becomes 2 2x (mod 4). But this completes the proof, since this last equation implies that x, the number of essentially different regular, doubly symmetric solutions, is not zero. Finally, we can show that the positive integers u and v in Fermat's result are unique. To do this, it is sufficient to prove that there are only two regular, doubly symmetric solutions to the p-queens problem - a single solution, and its horizontal reflection, both of which induce the same positive integers u and v for which u2 + v2 = p. So, suppose that (p, c) + ((1, d)) is a regular, doubly symmetric solution to the p-queens problem. Since a queen is located on the square (1, [c + d]), there must also be (by rotational symmetry) a queen on the square ([c + d], p). This means that

VOL. 50, NO. 2, MARCH 1977 73

This content downloaded from 129.128.216.34 on Wed, 13 Nov 2013 15:26:47 PM

All use subject to JSTOR Terms and Conditions

#### Page 6

(2) c+[c+d]d-p (mod p).

The fact that the center square is occupied means that (1) holds, so that we may substitute c (1 - d)12 from (1) into (2) to get

(2 d)+( 2 d) p (mod p)

which simplifies to

(3) d2+ 1 O (mod p).

Thus d satisfies x2 + 1 = 0 over the field Zp. Alternatively, if we substitute d 1 - 2c from (1) into (2) we see that c must satisfy x2 + (x - 1)2 = 0 over Zp. Thus the existence of a regular, doubly symmetric solution to the p queens problem, for p a prime of the form 4k + 1, also implies the existence of two solutions to each of the equations x2+ 1 = 0 and x2+ (x - 1)2 = 0 in 4. Since Zp is a field, these second order polynomial equations can have only two solutions in Zp, which implies that there can be only two possible values for d and c. But once one of these values is known, so is the other by equation (1), proving that there are at most two regular, doubly symmetric solutions to the p-queens problem when p is a prime. In conclusion, we note that these latter equations offer an alternative, albeit less elegant, procedure for proving the existence of a regular, doubly symmetric solution to the p-queens problem for p a prime of the form 4k + 1; simply choose d by (3) and c by (1) and apply the argument following equation (1).

References [1] Maurice Kraitchik, La Mathematique des Jeux ou Recreations Mathematiques, Chapter XIII, Le Probleme des Reines, Bruxelles, 1930, pp. 300-356. [2] G. Polya, Uber die "doppelt-periodischen" Losupgen des n-Damen Problems, Mathematische Unterhaltungen und Spiele, Dr. W. Ahrens. Zweiter Band, B. G. Teubner, Leipzig, 1918, pp. 363-374.

Proof without words: Cubes and squares 12 3 4 5 6 7

r rLl- J . BARRY LOVE

s _ _ ~~~I I I 111 1__11 :T

Naioa LibertyCH i Corp.110 -

13~ ~~ ~~~~~~~~ 3r 3 I 3 5 I -F I1I_TEI-_

Va 1,1 lle Foge Penn. _I _

7T+M2+M3+ + n)2 _ _ 7 __N

-J. BARRY LOVE National Liberty Corp. Valley Forge, Penn.

74 MATHEMATICS MAGAZINE

This content downloaded from 129.128.216.34 on Wed, 13 Nov 2013 15:26:47 PM

All use subject to JSTOR Terms and Conditions

---

Source: [Fermat's Library](https://fermatslibrary.com/) — https://fermatslibrary.com/s/a-theorem-about-primes-proved-on-a-chessboard. More annotated papers: https://fermatslibrary.com/llms.txt
