## Concordant Forms

```Recently the question was raised as to which primes are expressible
in the form (x^2 - 1)(y^2 - 1) for rational values of x and y.  This
is essentially equivalent to a question on "concordant forms", because
if there are integers a,b,c,d such that
_             _   _             _
|  / a \ 2      | |  / c \ 2      |
| ( ----)  -  1 | | ( ----)  -  1 |  =  p           (1)
|_ \ b /       _| |_ \ d /       _|

where p is a prime and the fractions are in lowest terms, then we
have (a,b)=(c,d)=1 and without loss of generality

a^2 - b^2 = pd^2          c^2 - d^2 = b^2             (2)

Thus, the prime p is expressible in the form (x^2 - 1)(y^2 - 1) if
and only if the two equations

b^2 + d^2 = c^2          b^2 + pd^2 = a^2             (4)

are concordant, i.e., can be solved simultaneously in integers.

Andre Weil's "Number Theory, an Approach Through History" includes
the following comments on concordant forms

"In 1777 and again in 1782 he [Euler] seeks criteria for...a
'double equation'

X^2 + Y^2 = Z^2         X^2 + NY^2 = T^2           (5)

to have infinitely many solutions.  Not surprisingly, he fails
(it is still an open problem)...  His interest and our own
turns to proofs of impossibility for the cases [N=3 or 4] and
others equivalent to these two.  One may well admire his
beautiful technique (rather different from Fermat's) for
applying the infinite descent to such problems."

It's interesting to see that (at least as of 1984) some aspects of
this were still "open", although Weil doesn't specify which questions
remain unanswered.  Interestingly, Dickson's "History..." contains a
list that supposedly contains all the integers N < 100 for which
equations (5) are concordant, but the list excludes 47, 53, and
83, which are definitely concordant, as was shown by the solutions

(14663)^2  +  (111384)^2  =  (112345)^2
(14663)^2 + 47(111384)^2  =  (763751)^2

(1141)^2  +   (13260)^2  =  (13309)^2
(1141)^2  + 53(13260)^2  =  (96541)^2

(2873161)^2  +   (2401080)^2  =  (3744361)^2
(2873161)^2  + 83(2401080)^2  =  (22062761)^2

Anyway, I've developed a proof of the impossibility of (5) for any
prime p such that p is congruent to 3, 5, 9, 11, or 13 (mod 16) and
every odd prime divisor of p-1 is congruent to 3 (mod 4).  This is
actually a fairly strong proposition; every prime less than 100 is
either known to be concordant or is ruled out by this proposition.

Here's the proof.  Beginning with equations (4)

b^2 + d^2 = c^2          b^2 + pd^2 = a^2            (4)

we can clearly assign any convenient signs to a,b,c,d  because they
only appear squared.  Also, we know that d is even and therefore a,b,c
are all odd, and we have (b,c)=(b,d)=(a,d)=1.  Combining equations
(4) gives
a^2 + (p-1)b^2 = pc^2                     (6)

For some choice of signs for a,b,c there necessarily exists an integer
k and positive mutually coprime integers u,v such that

ka = u^2 - 2(p-1)uv - (p-1)v^2
kb = u^2 + 2uv - (p-1)v^2                     (7)
kc = u^2 + (p-1)v^2

This is just the parametric solution of (6), analagous to the well-
known formulas for Pythagorean triples.  To see that there must be a
solution with u and v both positive, notice that  k(b-a) = 2puv,  so
by giving k the same sign as (b-a) we can make 2puv positive.  Also,
notice that equation (6) modulo p is just (a+b)(a-b)=0, and since
the signs of a,b are arbitrary, we can choose them such that (a-b)
is divisible by p (and of course (a+b) is not).

It will be helpful later to have some bounds on the magnitude of
k, so let's solve equations (7) for the three unknowns u^2, uv, v^2,
to give

p(b+c)-(b-a)             b-a              p(c-b)+(b-a)
u^2 = k ------------      uv = k ---      v^2 = k -------------
2p                    2p                 2p(p-1)

Since a,b,c,p are all odd, and (b-a) is divisible by p, it follows
that the denominator factors 2p are "absorbed" by the numerators.
The result is that k must divide each of the quantities

u^2        uv        (p-1)v^2

Since u,v are coprime this implies that k must be a divisor of
both  u  and  (p-1).  From this it also follows that (u+v) cannot
be divisible by p, because then according to equations (7) both ka
and kb would be divisible by p, and so would k(a+b), but since p
doesn't divide a+b it would have to divide k, which is impossible
because k divides p-1.

Now, combining expressions (7) for kb and kc, we find that the
positive coprime integers u,v satisfy the equation

(k^2)(c^2 - b^2)  =  4uv(u+v)(pv-(v+u))  =  (kd)^2         (8)

It's clear that v is necessarily coprime to each of u, u+v, and
(p-1)v-u, so v is always a square.  Also, since (u+v) is prime to
p, we know that (u+v) is co-prime to all the other factors, so it
too must be a square.  Thus we have coprime integers r,s such that
v=r^2 and (u+v)=s^2.  Substituting these values into (8) gives

uv(u+v)(pv-(u+v))  =  (r^2)(s^2 - r^2)(s^2)(pr^2 - s^2)

so the condition reduces to

(s^2 - r^2)(pr^2 - s^2)  =  square                  (9)

Letting g denote the gcd of (s^2 - r^2) and (pr^2 - s^2).  It follows
that g is the greatest common divisor of u and (p-1).  Remember we
showed previously that k divides gcd(u,p-1), so k divides g.  Anyway,
we have coprime integers t,w such that

s^2 - r^2 = gt^2
pr^2 - s^2 = gw^2

Combining these two equations gives

(p-1)r^2 = g(t^2 + w^2)
(p-1)s^2 = g(pt^2 + w^2)

Since g divides (p-1) we have integers h,f such that (p-1)/g = fh^2
where f is squarefree, and so we arrive at

w^2 +  t^2  =  f(hr)^2                      (10)
w^2 + pt^2  =  f(hs)^2                      (11)

Our objective is to show that if p = 3, 5, 9, 11, or 13 (mod 16) and
all the odd prime divisors of (p-1) are congruent to 3 (mod 4), then
these two equations are impossible.  There are three cases to consider.

First, suppose f is divisible by one of the odd prime factors of (p-1).
In this case equation (10) by itself is impossible by Fermat's theorem
on sums of two squares, i.e., in the factorization of any sum of two
squares, any prime congruent to 3 (mod 4) must occur with an even
exponent.  Thus, we can exclude any odd prime factors in f.

Next we consider the case f=2.  Recalling that p is one of 3,5,9,11,13
(mod 16) and that the parameters t,w are coprime, it's easy to see that
equations (10) and (11) are impossible (mod 16).

This leaves only the third possibility, namely, f=1.  However, notice
that if f=1 then equations (10) and (11) are identical to the original
equations
b^2 +  d^2  =  c^2                      (4)
b^2 + pd^2  =  a^2

For any solution (a,b,c,d) of this pair of equations, define the "norm"
of the solution as (bd)^2.  In view of equation (8), the norm of our
new solution (hs,w,hr,t) is given by

(wt)^2  =  (s^2 - r^2)(pr^2 - s^2)/g^2

=  (k^2 d^2) / (4 r^2 s^2 g^2)

But recall that k divides g, so putting g=km we have

(wt)^2  =   (d^2)/(2rsm)^2

which shows that (wt)^2 is smaller than d^2, so it is obviously
smaller than (bd)^2.  Thus, the norm of our new solution is strictly
smaller than the norm of the original solution.  This implies
an infinite sequence of integer norms with strictly decreasing
magnitudes, which is impossible.  This completes the proof.

I wrote a little program to search for such r,s for each prime p.
The smallest examples for primes p < 100 are listed below.

p      r    s       g       v     u   v+u
---    ---  ---     ---     ---   --- -----
7      1    2       3       1     3     4
11      1    3       2       1     8     9
17      1    3       8       1     8     9
23      5    6      11      25    11    36
31      1    2      15       1     3     4
41      1    3       8       1     8     9
47     13   36      23     169  1127  1296
53      5   13       4      25   144   169
59      1    3       2       1     8     9
61      1    7      12       1    48    49
71      1    6      35       1    35    36
79      1    2       3       1     3     4
83     17   33       2     289   800  1089
97      1    7      48       1    48    49

These results confirm that there are no solutions for primes p such
that p=3,5,9,11,13 (mod 16) and all odd divisors of (p-1) are
congruent to 3 (mod 4).  (In fact, I've checked much further, but
hard to find a solution.

David Einstein and Allan MacLeod checked the primes less than 1000
and found the following results

104   Concordant primes (solutions found)
48   Discordant (no solutions; also excluded by theorem)
16   Unknown (not excluded by theorem, but no solution found)

As both David and Allan have pointed out, all 16 of these can
be ruled out on the basis of the Birch-Swinnerton-Dyer conjecture,
so there's probably not much point in searching for solutions for
any of these.  However, I'm still interested in finding an elementary
proof that these are discordant.  If anyone can find a solution for
one of these, or explain why a solution is impossible, I'd be