Congruent Numbers Part III

Before demonstrating the claims made in Part I and Part II on this topic, let me mention two simple facts about integer solutions to A^2 + B^2 = C^2. First, if some number d divides both A and B, it also clearly divides C. So A and B have a common factor if and only if A, B, and C do. Or saying it another way, A and B are relatively prime if and only if A, B, and C are. From now on I always assume that this is true for A, B, and C.

The second fact is that A and B have opposite parity, that is, one is even and the other odd. It’s clear that A and B can’t both be even, since then they would have a common factor of 2. To see that A and B can’t both be odd, note that the square of an odd number is (2d+1)^2 = 4(d^2 + d) + 1 so the square of an odd number is congruent to 1 modulo 4. This means that if A and B are both odd, the left side of A^2 + B^2 = C^2 is congruent to 2 modulo 4. But then the right-hand side is even, so is of the form (2d)^2 = 4d^2 and is congruent to 0 modulo 4, contradiction.

With these two facts out of the way, let me show that a Pythagorean triple A^2 + B^2 = C^2 is always of the form

(1)   \begin{eqnarray*} A &=& 2PQ  \\ B &=& P^2 - Q^2 \qquad (\mbox{with } P > Q) \nonumber \\ C &=& P^2 + Q^2 \nonumber \end{eqnarray*}

It is easy to check that if A, B and C can be written this way in terms of P and Q then A^2 + B^2 = C^2. But where does the formula come from, and why are there always such P and Q?

A Pythagorean triple can be thought of as a point (x,y) on a unit circle:

(2)   \begin{equation*}\arraycolsep=1.4pt \begin{array}{ccccc} A^2 & + & B^2 & = & C^2 \\ \displaystyle \left(\frac{A}{C}\right)^2 & + & \displaystyle \left( \frac{B}{C}\right)^2 &=& 1 \\ \rule{0pt}{15pt}x^2 & + & y^2 & = & 1 \end{array} \end{equation*}

Each point (x,y) corresponds to a single point z on the x-axis, as in the left half of the figure below. The slanted line connects (0, 1) to a point z on the x-axis.

pythagThe key fact is that each pair (x,y) corresponds to a single number z. And z is rational if and only if (x,y) is rational. This can be seen from explicit formulas linking (x,y) and z. To get those formulas consult the right half of the figure where the triangle with sides E, F is proportional to the triangle with sides G, H. So

    \begin{eqnarray*} \frac{F}{E} & = & \frac{H}{G} \\ \frac{x}{1 - y} & = & z \\ z^2(1-y)^2 & = & x^2 = 1 - y^2 \\ z^2(1-y)(1-y) & = & (1-y)(1+y) \\ z^2(1-y) & = & 1+y \\ z^2 - 1 & = & (z^2 + 1)y \\ y & = & \frac{z^2 - 1}{z^2 + 1} \\ x & = & \frac{2z}{z^2 + 1} \end{eqnarray*}

The second equation shows that if x and y are rational then so is z. And the last two equations show the converse. But they show more. Writing z = P/Q in reduced form (i.e. P and Q relatively prime) and combining with (2) shows

    \begin{eqnarray*} x = \frac{A}{C}& = & \frac{2z}{z^2+1} \; = \; \frac{2PQ}{P^2 + Q^2}\\ y = \frac{B}{C} & = & \frac{z^2-1}{z^2+1} \;=\; \frac{P^2 - Q^2}{P^2 + Q^2} \end{eqnarray*}

Equating numerators suggests that A = 2PQ and B = P^2 - Q^2. But there is a subtlety: this is guaranteed only if A and B are relatively prime. For example 9^2 + 12^2 = 15^2, but there are no P and Q with 12 = 2PQ and 9 = P^2 - Q^2. The small print below gives two ways to turn the suggestion into a proof.

Both {\scriptstyle A/C} and {\scriptstyle B/C} are in reduced form since {\scriptstyle A} and {\scriptstyle B} are relatively prime. Therefore, the equation above shows only that there is an integer {\scriptstyle k} with
{\scriptstyle \mbox{ } kA = 2PQ \qquad kC = P^2 + Q^2 \qquad kB = P^2 - Q^2}
So I need to show that {\scriptstyle k=1}. First note that by adding and subtracting the last two equations, {\scriptstyle k|2P^2} and {\scriptstyle k|2Q^2}. Since {\scriptstyle P/Q} is in lowest form, at least one is odd so {\scriptstyle k} cannot be divisible by 4. Also, {\scriptstyle k} cannot be divisible by an odd prime {\scriptstyle p}, since that would then be a common factor of {\scriptstyle P} and {\scriptstyle Q}. So {\scriptstyle k} is either 1 or 2. Suppose {\scriptstyle k=2}. Since {\scriptstyle A/C}, and {\scriptstyle B/C} are reduced, they aren’t all even; and since {\scriptstyle A^2 + B^2 = C^2} one of {\scriptstyle A} and {\scriptstyle B} is odd. The geometric construction works when you switch {\scriptstyle x} and {\scriptstyle y}, so I can assume that {\scriptstyle B} is odd. Then {\scriptstyle kB = 2B \equiv 2 \pmod 4}. If {\scriptstyle P} and {\scriptstyle Q} have the same parity, then {\scriptstyle P^2 - Q^2 \equiv 0 \pmod 4}. So they must have opposite parities. But then {\scriptstyle P^2 - Q^2} is odd and can’t equal {\scriptstyle kB = 2B}, contradiction. Therefore {\scriptstyle k=1}. Forcing {\scriptstyle B} to be odd is crucial. If {\scriptstyle B} is even, {\scriptstyle k > 1} is possible. For example {\scriptstyle B=4, A=3, C=5} has a solution {\scriptstyle P=3}, {\scriptstyle Q=1}, {\scriptstyle k=2}.There’s also a fancy proof that uses unique factorization in the ring {\scriptstyle \mathbb{Z}[i]}. Write {\scriptstyle A^2 + B^2 = (A+iB)(A-iB) = C^2}. The two numbers {\scriptstyle A \pm iB} are relatively prime (see below) so each prime factor of {\scriptstyle C^2} divides only one of them. Therefore, each is a square and {\scriptstyle A+iB = \epsilon(P+iQ)^2} where {\scriptstyle \epsilon} is {\scriptstyle \pm 1} or {\scriptstyle \pm i}. So {\scriptstyle A+iB = (P^2 - Q^2) + i2PQ}, possibly switching {\scriptstyle A} and {\scriptstyle B}.

To see that the relative primality of {\scriptstyle A} and {\scriptstyle B} implies the relative primality {\scriptstyle A \pm iB}, suppose that a complex integer {\scriptstyle Z} divides both of {\scriptstyle A \pm iB}. If {\scriptstyle Z} is a real integer, then it divides both {\scriptstyle A} and {\scriptstyle B}, contradicting their relative primality. Similarly if {\scriptstyle Z} is purely imaginary. That means I can assume that {\scriptstyle Z \neq \overline{Z}}. By conjugating, it follows that {\scriptstyle \overline{Z} | A \pm iB} and so both {\scriptstyle Z} and {\scriptstyle \overline{Z}} divide {\scriptstyle A+iB}. Since these are distinct, the real integer {\scriptstyle |Z|^2} divides {\scriptstyle A+iB} which is again a contradiction. The final detail is that although {\scriptstyle Z \neq \overline{Z}}, they could be associates, that is {\scriptstyle Z = \pm iZ}. But that would imply {\scriptstyle Z = K(1\pm i)} so {\scriptstyle 1 \pm i | A + iB} which after taking norms becomes {\scriptstyle 2 | A^2 + B^2}, and that contradicts the statement from the beginning of this post that {\scriptstyle A} and {\scriptstyle B} are of opposite parity.

Formula (1) gives an easy way to show why there isn’t a triangle with integer sides and area 5. If \frac{1}{2}AB = N then that formula shows that there is a pair P, Q with (P,Q) = 1 and

    \[ PQ(P - Q)(P+Q) = N \]

When N=5 this has no integer solution because three of the factors must be 1, the other 5. Since P+Q is the largest of the four factors, it would have to be 5 and P = Q = P - Q = 1, which is clearly impossible.

Since the numbers A, B, C, and D are used to compute the sides \alpha = A/D, \beta = B/D and \gamma = C/D, you can remove any common factors if necessary since that won’t change the side lengths \alpha, \beta, \gamma. So I will always assume that \gcd(A,B,C,D) = 1, or using a common shorthand (A,B,C,D) =1.

Proposition: If A,B,C,D represents a square-free congruent triangle and (A,B,C,D) = 1, then (A,B,C) = 1.

Proof: By contradiction. Suppose (A,B,C) > 1. Then some prime p divides (A,B,C). First suppose p = 2 so 2 | (A,B,C) but 2 \nmid D. Then A'= A/2, B'= B/2, and C'= C/2 are integers so A'^2 + B'^2 = C'^2. It follows that one of A' or B' is even. This means that one of A, B is divisible by 4, the other by 2, so 8 | AB. Since \frac{1}{2}(A/D)(B/D) = N

    \[ \frac{1}{2}AB = N D^2 \]

It follows that 4|ND^2, but 2 \nmid D and N is square free. This is a contradiction, so 2 \nmid (A,B,C). Similarly, if p is an odd prime, and p divides A, B, and C but not D, then p^2|N, contradiction. So (A,B,C) = 1. \; {\rule{.6ex}{1.8ex}}

I use this to give a shortcut in the exhaustive search over P and Q. You only need to consider a subset. In the lemma below, the parity of N is N \pmod 2, i.e. odd or even.

Lemma: For a square-free congruent triangle, if (A,B,C,D) = 1 then (P,Q) = 1 and P, Q are of opposite parity. And such pair of (P,Q) generates a triangle with (A,B,C,D) = 1.

First assume (A,B,C,D) = 1. If P and Q have the same parity, then from equation (1) all of A, B and C are even, contradicting the proposition. If P and Q have a common factor, so do A, B and C, so that is not possible either. For the other direction, note that since P and Q have different parities, then A is odd and B is even so 2 \nmid (A,B, C). Thus you only need to consider an odd prime p. If p|(A,B,C) then p|B+C so p|2P^2 so p|P and similarly p|Q. \; {\rule{.6ex}{1.8ex}}

It follows that in exhaustive search, you only need to consider P, Q that are relatively prime and of opposite parities. Note: this is the glitch in the web table I mentioned earlier. For N=559, the web table gives P=2608225, Q=4489, which are both odd. If you use them to generate (A,B,C,D), remove the common factor of 2, and then recompute P, Q you get P' = 1306357, Q'= 1301868 with P' < P.

Next, I’ll verify the important speedup, which is that P and Q are almost squares.

Proposition: If P, Q are relatively prime and generate a square-free congruent number, then P = sP_0^2 and Q = tQ_0^2 where st|N (in particular, s|N and t|N).

Proof: Combine equation (1) and \frac{1}{2}\alpha \beta = \frac{1}{2}(A/D)(B/D) = N to get

    \[ D^2N = \frac{1}{2}AB = \left(P^2 - Q^2\right) PQ \qquad (P,Q) = 1 \]

If a prime p has p | P then p|N or p|D. If the latter, p^2 | (P^2 - Q^2)PQ but since (P,Q) = 1), p|Q is impossible, and so p|(P^2 - Q^2) is impossible so p^2 | P. Therefore every factor of P is either a square or a factor of N. It follows that P = sP_0^2 where each factor of s divides N. If any factor of s is a square then incorporate it into P_0 after which s|N. Similarly Q = tQ_0^2. Since (P,Q) = 1, (s,t) = 1 so st|N. \; {\rule{.6ex}{1.8ex}}

We observed earlier that in our tables, the denominator of \alpha times the denominator of \beta equals the denominator of \gamma. Here is the proof that it is true in general. Repeating the equations:

    \[\alpha = \frac{a}{d} \qquad \beta = \frac{b}{d} \qquad \gamma = \frac{c}{d}\]

    \begin{eqnarray*} \left(\frac{a}{d}\right) ^2 + \left(\frac{b}{e}\right) ^2 & = & \left(\frac{c}{f}\right) ^2 \\ \left(\frac{A}{D}\right) ^2 + \left(\frac{B}{D}\right) ^2 & = & \left(\frac{C}{D}\right) ^2 \end{eqnarray*}

Even though (A,B,C,D) = 1, A and D can have a common factor in which case a \neq A and b \neq B.

Lemma: With the usual assumption that (A,B,C,D) = 1, then de=f.

Proof: First check that (C,D) = 1 so that f=D. If not, then there is a p > 1 with p|D and p|C. From p|D and

(3)   \begin{equation*}  AB = 2nD^2 \end{equation*}

it follows that p|A (or perhaps B). But p|C and A^2 + B^2 = C^2 implies p|(A,B,C), contradiction. Next from (3) every prime factor of D must divide either A or B. Start with A/D and B/D. Then consider the prime factors of D one-by-one. For each factor p, remove it from either the numerator and denominator of A/D or from B/D. After the removal process A/D becomes A'/D' and B/D becomes B'/D'' and since a/d and b/d are completely reduced, d|D', e|D'' and so de | D'D''. Since each factor of D was removed, D'D'' = D so de | D'D'' = D and thus de \leq D. Finally, write

    \begin{eqnarray*} \frac{A^2}{D^2} + \frac{B^2}{D^2} & = & \frac{C^2}{D^2} \\ \frac{a^2}{d^2} + \frac{b^2}{e^2} & = & \frac{C^2}{D^2} \\ \frac{a^2e^2 + b^2d^2}{d^2e^2} & = & \frac{C^2}{D^2} \end{eqnarray*}

The last equation shows that de \geq D. If not, then it writes C^2/D^2 in a more reduced form, contradicting the first part of the proof. I previously showed de \leq D so it follows that de = D. And the first part of the proof showed that f=D. \; {\rule{.6ex}{1.8ex}}

Powered by QuickLaTeX