All of the grid entries (and diagonals) were not just primes, but primes that are one greater than a multiple of 4, which are known as Pythagorean primes. A theorem given by Fermat and first proved by Euler states that all such primes can be expressed as the sum of two squares (in only one way), and that all other odd primes (which are one less than a multiple of 4) cannot. However, it wasn’t necessary to know that in order to solve the puzzle; recognising them as primes was enough. The puzzle’s title is an anagram of Pierre de Fermat.

This is one possible solution path. The smallest answer possible for a sum clue N is given by the roots that are the nearest integers either side of (but not equal to) N/2; similarly, for a product clue the smallest possible answer is given by the nearest integers either side of √N. For a 2-digit entry, the maximum possible value is 99, so both of the squares in its sum must be < 99, ie, both of its roots are < √99 ≈ 9.9; for a 3-digit entry, both roots are < √999 ≈ 31.6; for 4 digits, they’re both < √9999 ≈ 99.995; for 5 digits, they’re both < √99999 ≈ 316.2. Also, for any sum of squares N, one of the two squares is < N/2 and the other is > N/2, so if the smallest potential value for an entry is M, then at least one of the roots is > √(M/2). For example, any 3-digit sum of squares must have at least one root > √(100/2) ≈ 7.1.

If a product clue has one large prime factor then there may be
few options for the root that is a multiple of that factor.
For example, the 3-digit entry 12dn has the clue 290,
which can’t be the sum of the roots
(because the smallest possible answer would come from roots of 144 and 146,
but the 3-digit entry needs both roots < 31.6),
so it’s a product and is easily factorisable as 2×5×29.
The only product with both roots < 31.6 is 10×29,
giving the answer of **12dn = 941**
= 10^{2} + 29^{2}.
However, factorising numbers with large prime factors is typically laborious
and we’ll try to put that off as long as possible.

The clue for 2dn is 4, so its roots can only be {1×4, 1+3, 2+2},
giving {17, 10, 8}, so it starts with 1.
As 1ac has three digits, its 3-digit clue must be a product,
and both roots must be < 31.6;
150 is easily factorised as 2×3×5×5,
from which the suitable products are {5×30, 6×25, 10×15},
giving {925, 661, 325} respectively,
and as it has to end with 1, **1ac = 661**.
1dn now starts with 6, so both roots must be < √6999 ≈ 83.7,
and the 4-digit clue must be a product.
It doesn’t take much effort to factorise
1596 = 2×2×3×7×19,
so the suitable products, based on increasing multiples of 19,
are {38×42, 57×28, 76×21}, giving {3208, 4033, 6217},
and the only one that fits is **1dn = 6217**.

The largest value that 4dn’s clue of 145 can give is
1^{2} + 145^{2} = 21026, so 4dn starts with 1 or 2.
As 3ac has three digits, its roots are both < 31.6
and its 3-digit clue must be a product;
it’s easily factorised as 220 = 2×2×5×11,
so the only potential products are {11×20, 22×10},
giving {521, 584}, of which only **3ac = 521** fits.
Now 3dn is 5___, so both roots are < √5999 ≈ 77.5
and its 4-digit clue must be a product;
it’s easily factorised as 1190 = 2×5×7×17
and the suitable products are {17×70, 34×35},
giving {5189, 2381}, of which only **3dn = 5189** fits.

Looking at the small entries, 6ac has the clue 7.
As a product, the only possibility is 1^{2} + 7^{2} = 50,
but 7dn can’t start with 0,
so that’s excluded and the clue must be a sum.
The possibilities are {3 + 4, 2 + 5, 1 + 6}, giving {25, 29, 37} respectively,
and 7dn must start with one of {5, 7, 9}.
7dn has 2 digits, so both roots are < 9.9;
the clue is 13, which must be a sum
(because the product can only give 1^{2} + 13^{2} = 170, too big),
for which the possibilities are
{6^{2} + 7^{2} = 85,
5^{2} + 8^{2} = 89,
4^{2} + 9^{2} = 97}.
Only one of those fits with 6ac,
so **7dn = 97** and **6ac = 29**.
Like 7dn, 9dn is a 2-digit entry with the clue 13,
so it’s one of {85, 89} and we can enter the 8.

If 16dn’s clue of 19 is a product,
the only value possible is 1^{2} + 19^{2} = 362;
if it’s a sum the roots end in one of {0+9, 1+8, 2+7, 3+6, 4+5},
with the sum of squares ending in {1, 5, 3, 5, 1} respectively.
Therefore 25ac starts with one of {1, 2, 3, 5} and has 4 digits,
so its roots are both < √5999 ≈ 77.5
and its 4-digit clue is a product;
it’s easily factorised as 1410 = 2×3×5×47,
so the only possible roots are 47×30,
giving **25ac = 3109**.
That means the clue for 16dn is a sum and the roots end in 2 and 7,
so it’s one of {2^{2} + 17^{2} = 293,
12^{2} + 7^{2} = 193}.

21dn is _0__ and its roots are both < √9099 ≈ 95.4.
The clue 924 must be a product (roots of 461+463 would be too big)
and is easily factorised as 924 = 2×2×3×7×11,
so the possible roots are
{11×84, 22×42, 33×28, 44×21, 66×14, 77×12},
giving {7177, 2248, 1873, 2377, 4552, 6073};
the only one that fits is **21dn = 6073**.

24dn has 4 digits, so both roots are < 100
and its 4-digit clue must be a product.
It’s easily factorised as 2754 = 2×3×3×3×3×17
and the possible roots, based on multiples of 17,
are {34×81, 51×54}, giving {7717, 5517} and we can enter the 17.
31ac is now __7 with both roots < 31.6,
and it has a 3-digit clue that must be a product
and is easily factorised as 144 = 2×2×2×2×3×3.
The possible roots are {6×24, 8×18, 9×16},
giving {612, 388, 337} respectively, so **31ac = 337**.
28dn is now _3, so the two squares end in 4 and 9
and the roots end in (2 or 8) and (3 or 7);
that rules out the clue of 9 being a product (as the roots would be 1 and 9),
so the two roots adding up to 9 must be 2 and 7;
therefore **28dn = 53** = 2^{2} + 7^{2}.

For 29ac, the clue 11 can’t be a product of roots
because 1^{2} + 11^{2} = 122 is too big,
so the two roots add up to 11 and are both < 9.9.
That gives the options
{2^{2} + 9^{2} = 85,
3^{2} + 8^{2} = 73,
4^{2} + 7^{2} = 65,
5^{2} + 6^{2} = 61},
so 27dn ends with one of {6, 7, 8}.
Clued by 6, 27dn’s roots are one of {1×6, 2×3, 1+5, 2+4},
giving respectively {37, 13, 26, 20}, of which only {37, 26} can match 29ac.
Then 27ac starts with 2 or 3;
its clue of 10726 must be a product,
and it’s an obvious multiple of 2 but not of 4
(because 26 isn’t a multiple of 4),
which means one of the roots must be even and the other odd,
so the sum of squares is odd.
For 26dn, the clue of 5 allows
{1^{2} + 5^{2} = 26,
1^{2} + 4^{2} = 17,
2^{2} + 3^{2} = 13},
but it has to end in an odd digit,
so 26dn is one of {17, 13} and we can write in the 1.

5dn has 4 digits, so its roots are both < 100, and the clue 306 is a product (if it’s a sum, the smallest value possible is with roots 152 and 154, both too big). It’s easily factorised as 2×3×3×17, and the possible roots are {17×18, 34×9, 51×6}, giving {613, 1237, 2637} respectively, so 5dn is one of {1237, 2637} and we can enter the 37.

18ac is __1, odd,
so one of its two square roots is odd and the other is even.
The clue 39 has only odd factors,
so it must be the sum of the roots (both < 31.6).
For the sum of squares to end in 1,
they must end in (0 and 1) or (5 and 6);
for the roots to add up to 39,
they must end in (0 and 9) or (5 and 4) respectively.
The possibilities are {20+19, 24+15, 25+14, 29+10},
giving {761, 801, 821, 941},
the second of which can be eliminated because 19dn can’t start with 0.
The largest answer possible from 19dn’s clue of 65 is
1^{2} + 65^{2} = 4226, so we can also eliminate 761.

15ac has 7 as the second digit.
The largest answer its clue of 15 can give is
1^{2} + 15^{2} = 226,
so the entry must be in the range [170, 179].
Both roots must be < √179 ≈ 13.4,
and at least one of the roots is > √(170/2) ≈ 9.2.
The clue can’t be a product
(because 1×15 has one root too big
and 3×5 doesn’t have a root that’s big enough),
so the possible roots are, in decreasing order of sums of squares,
{2+13, 3+12, 4+11, 5+10}.
3^{2} + 12^{2} = 153 and the following ones are too small,
so the only one that fits is
**15ac = 173** = 2^{2} + 13^{2}.

If 16ac’s clue of 15 is a product,
the only option is 1^{2} + 15^{2} = 226
(because for 3×5 neither root is > 7.1
needed for a 3-digit sum of squares),
which would make 8dn even.
The clue for 8dn is odd,
so to give an even sum of squares both roots would have to be odd,
ie factors of 35, and the only options would be {1×35, 5×7};
but the sums of squares for these end in 6 and 4 respectively,
not the 2 we want, so the clue for 16ac isn’t a product.
So, the root possibilities for 16ac are {1+14, 2+13, ..., 7+8},
for which the sums of squares are {197, 173, 153, 137, 125, 117, 113};
we can eliminate 125
(because we’ve just established that 8dn can’t end in 2),
so 8dn is odd and its clue is not a product (as above).
Trying the results for {1+34, 2+33, 3+32, 4+31, ...},
they start with {1157, 1093, 1033, 977, ...}
and the rest are all too small for the 4-digit entry,
so 8dn is one of {1033, 1093, 1157},
which limits 16ac to {137, 173};
but we already have 173 at 15ac,
so **16ac = 137**, **16dn = 193**
and 8dn is one of {1033, 1093}.

20ac is _6_.
If its clue of 39 is a product,
the options are 1^{2} + 39^{2} = 1522
and 3^{2} + 13^{2} = 178,
neither of which fits, so the clue is a sum.
The smallest possible sum of squares is
19^{2} + 20^{2} = 761;
18^{2} + 21^{2} = 765 also fits,
but none of the other options from 17+22 to 8+31
(because both roots are < 31.6)
has 6 as the second digit, so 20ac is one of {761, 765}.

For 11ac we have _3_9, so it has one odd and one even root.
Its clue 57 only has odd factors,
so it must be the sum of the roots.
For the sum of squares to end in 9,
they must end in (0 and 9) or (4 and 5);
for the roots to add up to 57,
they must end in (0 and 7) or (2 and 5) respectively.
Of the 11 possibilities
{2+55, 5+52, 7+50, 10+47, 12+45, 15+42, 17+40, 20+37, 22+35, 25+32, 27+30},
only 10+47 gives a result with 3 as the second digit,
so **11ac = 2309**.

So far, we have 15 complete entries,
{29, 53, 97, 137, 173, 193, 337, 521, 661, 941, 2309, 3109, 5189, 6073, 6217},
all of which happen to be primes.
Also, for entries where we have a small set of options
there’s always at least one prime available:
18ac in {821, 941}, 20ac in {761, 765}, 29ac in {61, 65, 73},
2dn in {10, 17}, 5dn in {1237, 2637}, 8dn in {1033, 1093},
9dn in {85, 89}, 24dn in {5517, 7717}, 26dn in {13, 17},
27dn in {26, 37}.
So, it’s not an unreasonable guess that
the common feature all entries share is being prime numbers.
On that assumption, we can fill in
**20ac = 761**, **2dn = 17**,
**5dn = 1237** (because 2637 is an obvious multiple of 3),
**9dn = 89**,
**24dn = 7717** (5517 is an obvious multiple of 3),
**27dn = 37**
and then **29ac = 73**
and **26dn = 13** (because 17 is taken at 2dn).

If every entry is prime and therefore odd, then it’s the sum of an odd and an even square, so one root is odd and the other is even. That means that clues that are products of the roots are all even, and those that are sums are all odd. For any product clue, the two roots must have no factors (greater than 1) in common, or their sum of squares would have the same factor (squared) and not be a prime.

17dn is _19__, so its roots are both < √91999 ≈ 303.3.
It doesn’t take much effort to factorise
22374 = 2×3×3×11×113
(having divided by all the primes up to 11,
the residue of 113 must be prime because its square root is < 11
and none of the smaller primes were factors),
so the potential products are {113×198, 226×99};
but 226^{2} + 99^{2} = 60877 doesn’t fit,
so **17dn = 51973** = 113^{2} + 198^{2}.
Now 30ac starts with 3,
so its roots are both < √399 ≈ 19.97.
The (product) clue is easily factorised as 90 = 2×3×3×5,
so the options are {5×18, 10×9}
(not 15×6, which share a factor of 3);
but 10^{2} + 9^{2} = 181 doesn’t fit,
so **30ac = 349** = 5^{2} + 18^{2}.

For 27ac, factorising the clue begins with 10726/2 = 5363,
and then it takes a bit of trial and error to find
the next prime factor in 5363/31 = 173;
173 must then be a prime because we’ve already tried
dividing by all primes up to √173 ≈ 13.2.
As 27ac is 3_773, both roots are < √39773 ≈ 199.4,
so one of them must be 173 itself,
and **27ac = 33773** = 173^{2} + 62^{2}.

For any clue C that is the sum of the roots of the answer N,
we have C = x + y and N = x^{2} + y^{2}.
Substituting y = C − x,
we can get N = x^{2} + (C − x)^{2},
which in conventional quadratic form gives
x^{2} − Cx + (C^{2} − N)/2 = 0.
Using the quadratic formula, the roots of that are
x = (C ± √(C^{2} − 2(C^{2} − N)))/2
= (C ± √(2N − C^{2}))/2.
To get integer roots, 2N − C^{2} must be a square number.

10ac is 10_89 and the middle digit can’t be any of {0, 3, 6, 9}
because that would make it a multiple of 3.
The clue is odd, so it’s the sum of the roots,
and 2N − 137^{2} must be a square.
Trying the six possible values of 10ac for N,
only 10489 and 10789 give a square,
and the formula gives the roots of (45, 92) and (42, 95) respectively.
Testing for primeness, we can find a factor of 17 for 10489,
so **10ac = 10789** = 42^{2} + 95^{2}.

22ac has 5 digits, so both roots are < 316.2,
which means that both roots are > 31746/316.2 ≈ 100.4.
The entry ends in 7, so its squares end in 1 and 6,
and the roots must end in (1 or 9) and (4 or 6);
as their product ends in 6,
they must end in (1 and 6) or (9 and 4).
The clue has smallish prime factors, so finding
31746 = 2×3×11×13×37 doesn’t take long.
The only combinations giving a factor that ends in 4 are
2×37 = 74 (too small to be one of the roots)
and 2×11×37 = 814 (too big);
the only combinations ending in 6 are 2×3 = 6,
2×3×11 = 66, 2×13 = 26 (all too small),
2×11×13 = 286 and 31746 itself (much too big);
therefore the roots are 286 and 3×37 = 111
and **22ac = 94117**.

26ac is 1___7, so both roots are < √19997 ≈ 141.4,
and the clue is a product,
so both roots are > 9044/141.4 ≈ 63.96.
The entry ends in 7, so its squares end in 1 and 6,
and the roots must end in (1 or 9) and (4 or 6);
as their product ends in 4,
they must end in (1 and 4) or (9 and 6).
The clue has smallish prime factors, so finding
9044 = 2×2×7×17×19 doesn’t take long.
As one of the roots has to be odd,
the even root must use both of the 2s.
The only (multiple of 4) factors ending in 4 are
2×2 = 4 (too small) and 9044 (too big);
the factors ending in 6 are 4×19 = 76
and 4×7×17 = 476 (too big);
therefore the roots are 76 and 7×17 = 119
and **26ac = 19937**.

23dn is 49_9 and the missing digit can’t be any of {2, 5, 8}
(or the entry would be a multiple of 3).
It has a (sum) clue of 97, so using the quadratic test (above)
we need 2N − 97^{2} to be a square.
Trying the seven potential values, only 4969 works,
giving 529 = 23^{2}, so the two roots given by the formula are
(97 − 23)/2 = 37 and (97 + 23)/2 = 60
and **23dn = 4969**.

19dn is either 213_ or 413_,
but the maximum value its (sum) clue can give is
1^{2} + 64^{2} = 4097,
so 19dn starts with 2 and **18ac = 821**.
Now 19dn is 213_, with none of {0, 3, 6, 9} for the last digit,
to avoid a multiple of 3,
so its roots are both < √2138 ≈ 46.2
and both > 65 − 46.2 = 18.8.
For the quadratic, we need 2N − 65^{2} to be square;
trying the six possibilities, only 2137 gives 49 = 7^{2},
so **19dn = 2137**
(with roots of (65 − 7)/2 = 29 and (65 + 7)/2 = 36).

4dn is 1_21_.
For 2N − 145^{2} to be positive,
we need N > 145^{2}/2 = 10512.5,
so the second digit isn’t 0.
For 2N − 145^{2} to be square,
2N must end in one of {0, 4, 6}
and the prime N can only end in one of {3, 7}.
The possibilities (avoiding digit sums that are a multiple of 3) are
{11213, 12217, 13213, 13217, 14213, 15217, 16213, 16217, 17213, 18217, 19213, 19217},
of which only 15217 gives a square, 9409 = 97^{2},
so **4dn = 15217**
(with roots of (145 − 97)/2 = 24 and (145 + 97)/2 = 121).

Now 9ac is 852_7,
and the missing digit isn’t any of {2, 5, 8}.
Both roots are < √85297 ≈ 292.1
and > 23994/292.1 ≈ 82.1.
As the entry ends in 7,
the roots end in (1 or 9) and (4 or 6);
as their product ends in 4,
they must end in (1 and 4) or (9 and 6).
With a bit of labour we can find the clue’s prime factors as
23994 = 2×3×3×31×43;
the root that is a multiple of 3 must use both 3s
(or both roots would share a factor of 3),
so we need to consider combinations of 2×9×31×43.
The factors ending in 4 are 2×9×43 = 774
and 23994 itself (both too big);
the only one ending in 6 is 2×43 = 86,
so the roots are 86 and 23994/86 = 279
and **9ac = 85237**.

For 14dn, the roots add up to 27,
and for 2N − 27^{2} to be positive,
we need N > 27^{2}/2 = 364.5.
Because 13ac is a prime, 14dn starts with one of {3, 7, 9}.
13ac is now 7__9_ with 3 or 9 for the second digit
and {3, 7, 9} for the last.
Both roots are < √79999 ≈ 282.8
and > 32984/282.8 ≈ 116.6,
ie, they’re in the range [117, 282].
Factorising the clue gives 32984 = 8×7×19×31
(keeping 2^{3} together because only one root can be even),
which can be split into two factors in eight ways,
only two of which give numbers in the right range,
namely 133×248 and 152×217.
For the latter, 152^{2} + 217^{2} = 70193
has the wrong second digit,
so **13ac = 79193** = 133^{2} + 248^{2},
which makes **8dn = 1093**.

Now we have 3_9 for 14dn, which we already know is > 364.5.
Its middle digit can’t be any of {0, 3, 6, 9}
or it would be a multiple of 3, which leaves only {379, 389}.
Trying the quadratic test,
2×379 − 27^{2} = 29 isn’t a square,
but 2×389 − 27^{2} = 49 works,
so **14dn = 389**
(with roots of (27 − 7)/2 = 10 and (27 + 7)/2 = 17)
and the grid is complete.

We now want to find a pair of 9-digit primes in the grid. Checking the rows (left to right) and columns (down), they all have a digit sum that’s a multiple of 3 or are even, except for the 6th and 9th columns, which aren’t symmetrically placed. So we want the diagonals, 617984977 and either 730181339 or 933181037. For the first, both roots are < √617984977 ≈ 24859.3, and they must be on either side of √(617984977/2) ≈ 17578.2. For the sum of squares to end in 7, the two roots must end in (1 or 9) and (4 or 6). So, we can search for the larger root as a number in the range [17579, 24859], ending in one of {1, 4, 6, 9}.

The candidates across and down are 21129 (row 1), 19411 (row 6),
21719 (column 1), 18951 (column 4), 21749 (column 6), 23781 (column 7),
but none of them gives a square for 617984977 − n^{2},
so we need to try diagonal numbers.
Reading in a south-east direction, there are 19181, 17984, 20159, 19711,
but none of those gives a square;
NW there are 18191, 11791, neither of which works;
NE there’s only 14839, which doesn’t work;
SW there are 21791, 23561,
the first of which gives 617984977 − 21791^{2} = 11964^{2},
and 11964 appears in a SW direction opposite 21791,
so we can highlight both of them.

For the other pair, symmetry suggests trying the south-easterly 25331 and 17074; the sum of their squares is indeed 933181037, which is the other diagonal, reading SW. Highlighting this pair completes the symmetrical “diamond” arrangement, and the puzzle is finished.