Pythagorean triples have a long and storied tradition. But what about the near misses?

You’d be surprised how much math[s] you can learn by exploring some of the implications and ramifications of what may seem at first no more than a trivial brainteaser

Martin Gardner

Every so often, I get nerdsniped good and proper. In some cases, multiple times in a week. Here is Chris Smith doing just that:

Here’s Chris’s question in text form:

Can we find three different triangular numbers $a$, $b$ and $c$ so that every combination of the three gives a triangular number?

So \(a+b\), \(a+c\), \(b+c\) and \(a+b+c\) should all be triangular numbers.

In this case, it wasn’t the puzzle itself that did for me; I solved that fairly quickly. But in so doing, I dug up something deeper and more interesting, and – to the best of my knowledge – unsolved.

Welcome to the fascinating world of almost Pythagorean triples.

What is an almost Pythagorean triple?

You, being an avid Aperiodical reader, might have come across Pythagorean triples before: three integers, \(a\), \(b\) and \(c\), such that \(a^2 + b^2 = c^2\). Examples of this have been known for about 4,000 years, and Euclid had a method for generating all of them. Been there, done that, and — like Hippasus — got the swimsuit.

In the 1980s, Orrin Frink wondered: what about triples that are off by one? That is, what if \(a^2 + b^2 = c^2 + 1\)? Quite naturally, he called these almost Pythagorean triples, or APTs.

Some examples of APTs include \(a=4, b=7, c=8\) and \(a=5, b=5, c=7\). To save space, I’m going to use brackets for my APTs from now on: instead of \(a=4, b=7, c =8\), I’ll simply write \((4,7,8)\).

Antalan and Tomenes also looked at APTs, and asked the key question I will answer in this article: “Is there an explicit formula to generate APTs?” The answer to this is “yes”, but we’ll need to do some work to get there.

First, some definitions: it’s useful to distinguish between isosceles APTs, such as \((5,5,7)\) and \((29,29,41)\), where \(a=b\) and scalene ones, where \(a \ne b\), as in \((4,7,8)\) and \((23,41,47)\).

The two shorter elements of an APT cannot both be even – if they were:

• \(a^2+b^2\) would be a multiple of 4
• \(c\) would be odd, so \(c^2+1\) would be two more than a multiple of 4

These two things can’t both be true! So at least one of \(a\) and \(b\) must be odd — and \( c \) is even if and only if one of the shorter elements is also even. Alternatively, if I suppose \( b \) is odd, which I will do presently, then \( c \) and \( a \) must have the same parity.

Without loss of generality, I can assume that \(b\) is odd. Define an odd APT as one where \(a\) and \(c\) also odd, and an even APT as one where \(a\) and \(c\) are both even.

So: \((4,7,8)\) is an even scalene APT, and \((5,5,7)\) is an odd isosceles APT. In fact, all isosceles APTs are odd.

What can I easily say about APTs?

Let’s apply some algebra to the key equation \(a^2 + b^2 = c^2 + 1\).

That can be rearranged to \(b^2 -1 = c^2- a^2\), and by difference of two squares to \((b-1)(b+1) = (c-a)(c+a)\).

I’ve asserted that \(b\) is odd and it follows that \(c\) and \(a\) are of the same parity, so all four of the factors here are even, and it makes sense to halve them: \( \left(\frac{b+1}{2}\right)\left( \frac{b-1}{2}\right) = \left(\frac{c+a}{2}\right)\left( \frac{c-a}{2} \right) \).

The algorithm I’m about to present treats each of these four factors as a product of two integers, so that the product on the left-hand side and the product on the right-hand side match. In particular, I’m going to generate four integers, \(s\), \( s’ \), \(t\) and \(t’\) such that:

• \(\frac{c+a}{2} = st\)
• \(\frac{c-a}{2} = s’t’\)
• \(\frac{b+1}{2} = ss’\)
• \(\frac{b-1}{2} = tt’\)

Note that \(ss’ – tt’ = 1\), which places a severe restriction on our values: \(\gcd(ss’, tt’)=1\). In fact, the ‘primed’ variables \(s’\) and \(t’\) can be deduced from any pair of coprime positive integers \(s\) and \(t\). I’ll explore how to generate the variables a little later (after we’ve talked about Bézout).

The goal is to begin with values of \( s \) and \(t \), find the corresponding values of \( s’ \) and \( t’ \), and use these to generate APTs. There are four major questions to answer:

• How can \(s’\) and \(t’\) be found?
• Does every pair of coprime \(s\) and \(t\) give an APT?
• Is every APT is generated by some \((s,t)\) pair?
• Is every APT is generated by exactly one \((s,t)\) pair?

If the answers to this are (respectively) “like so”, “yes”, “yes” and “yes”, then I’ll have an answer to Antalan and Tomenes’s challenge.

Generating APTs

I’m going to give a proposition:

Given a pair of coprime integers, \(s\) and \(t\), there are infinitely many integer values of \(s’\) and \(t’\) such that \(ss’ – tt’=1\). However, there is only one of each such that \(0 \le t’ < s\) and \(0 \le s’ < t\), which is a lemma you may wish to prove.

Using the multiplicative inverse, let \(s’ = s^{-1} \pmod t\) and \(t’ = (-t)^{-1} \pmod s\).

Then \((st – s’t’, ss’ + tt’, st + s’t’)\) is an almost Pythagorean triple.

A proof will follow later. You may provide your own if you can’t wait that long.

Hold on hold on hold on, what’s this multiwhotsit hoojimaflip?

I thought you’d never ask. We need to take a quick detour into modular arithmetic — or rather, the world of remainders; modular arithmetic is fascinating and wonderful, but we’re only after one small aspect of it here.

A tl;dr, in case you just don’t recognise the term: if you’ve got two coprime integers, \( p \) and \( q \), then the multiplicative inverse of \( p \pmod q\) is the unique integer \(r \) such that \( 0 \le r < q \) and \( pr \) is one more than a multiple of \( q \).

Again, with the \( \le \) in the inequality, equality holds if and only if \( q = 1 \). We don’t usually do arithmetic modulo 1, but it helps to avoid an edge case with APTs.

For example, suppose \( q = 10 \) and \( p = 3 \). We’re looking for a number \( r \) that’s between 0 and 10 (exclusive), and with \( pr \) one more than a multiple of 10. The only option is \( 3 \times 7 = 21 \), so \( r = 7 \)

Modulo 10, 7 is the multiplicative inverse of 3, and we write that as \(7 \equiv 3^{-1} \pmod{10}\). In general, \(r \equiv p^{-1} \pmod{q}\) whenever \(pr \) is one more than a multiple of \( q \), and \( 0 \le r < q \).

So how do we find a multiplicative inverse if the numbers are too big to bother listing all the possibilities? We know an identity about that!

Bézout’s identity: Suppose \(\gcd(a,b)=d\). Then there exist integers \(a’\) and \(b’\) such that \(aa’ + bb’ = d\), and all multiples of \(d\) can be obtained this way.

In particular, if \(a\) and \(b\) are coprime, we can find \(a’\) and \(b’\) such that \(aa’ + bb’ = 1\) using the extended Euclidean algorithm, which I will explain only by example – suppose I want to find the multiplicative inverse of 3, modulo 10. I let \(a=10\) and \(b=3\):

• \(10 = (1 \times 10) + (0 \times 3)\)
• \(3 = (0\times 10) + (1 \times 3)\)
• Take away as many \(3\)s from \(10\) as possible: \(1 = (1\times 10 )- (3 \times 3)\)
• Take away as many \(1\)s from \(3\) as possible: \(0 = (-3 \times 10 )+ (10 \times 3)\), which makes sense, if you think about it.

I can add any multiple of \(0\) to the \(1\) to get another answer, so \(1 = 10(1-3k) + 3(10k – 3)\) for any integer \(k\). This gives \(a’ = 1-3k\) and \(b’ = 10k-3\). Since I want \( b’ \) to be the inverse of 3, modulo 10, I need \(0 \le b’ < 10\), so \(k=1\), \(a’=-2\) and \(b’=7\).

To double-check: \( (-2 \times 10) + (7 \times 3) = -20 + 21\), which is indeed one.

TL;DR, repeated for emphasis: Given that \(a\) and \(n\) are coprime, the multiplicative inverse \(a^{-1}\) of an integer \(a\), modulo \(n\) is the unique integer between \(0\) and \(n-1\) (inclusive) such that \(aa^{-1}\) is one more than a multiple of \(n\).

With regard to the algorithm, Euclid offers two-for-the-price-of-one here: if I work out \(s’ = s^{-1} \pmod t\) this way, the other coefficient (in absolute value) is the multiplicative inverse of \( -t \), modulo \(s \). Again, let’s check that with the example: I want \(t’ \) to be a number between \( 0 \) and \( 3 \), exclusive, such that \( -10 t’ \) is one more than a multiple of 3. Indeed, -20 is one more than -21, so it works!

A fuller example

Let’s pick two coprime integers at random to try this with: \( s= 14 \) and \( t = 9\).

Step 1: apply the Euclidean algorithm to find \( s’ \) and \( t’ \).

• \( 14 = 1s + 0t \)
• \( 9 = 0s +1t \)
• Take away as many \(9\)s as possible: \( 5 = 1s – 1t \)
• Take away as many \(5\)s as possible: \( 4 = -1s + 2t \)
• Take away as many \(4\)s as possible: \( 1 = 2s – 3t \)
• Take away as many \(1\)s as possible: \( 0 = -9s + 14t \), as one would hope.

In this case, the \( s \) coefficient is positive, so it doesn’t need to be adjusted: \( 14^{-1} \pmod 9 = 2\) and \((-9)^{-1} \pmod 14 = 3\), so \(s’ = 2 \) and \( t’ = 3 \).

Solving the simultaneous equations:

• \(\frac{c+a}{2} = st= 126\)
• \(\frac{c-a}{2} = s’t’ = 6\)
• \(\frac{b+1}{2} = ss’ = 28\)
• \(\frac{b-1}{2} = tt’ = 27\)

gives \( a = 120 \), \( b = 55 \) and \(c = 132\); checking, \( 120^2 + 55^2 = 17,425\), which is \( 132^2 + 1\). Therefore, \( s= 14\), \( t= 9 \) generates the APT \( (120, 55, 132 ) \).

Proofs

A quick note on an edge case: as I mentioned previously if \( s = 1 \) the multiplicative inverse of \( t\) is not conventionally defined. However, the extended Euclidean algorithm does give a value, zero, for \( t’ \), which serves perfectly well for the algorithm. In fact, if \( s = 1 \) or \( t= 1\), the result is an isosceles APT of the form \( (a, 1, a) \) or \( (1, b, b) \), respectively.

In the proofs that follow, I adopt the convention that \( x^{-1}\pmod 1 = 0\) for all \( x \).

1 The algorithm always gives an APT

Proposition:

• If \(s\) and \(t\) are positive integers with \(\gcd(s,t)=1\)
• Let \(s’ = s^{-1}\pmod t\) and \(t’ = t^{-1}\pmod s\)
• If:
  • \(a = st -s’t’\)
  • \(b = ss’ + tt’\)
  • \(c = st + s’t’\)
• Then \(a^2 + b^2 = c^2 + 1\).

Proof:

Note that for given coprime \(s\) and \(t\):

• \(ss’ = \lambda t + 1\) for some integer \(\lambda\)
• \(tt’ = \mu s – 1\) for some integer \(\mu\).

By inspection, \(\lambda = t’\) and \(\mu = s’\); this gives \(ss’ = tt’ +1\).

Now, let’s show that this gives an APT.

Consider \(c^2 – a^2 = (st + s’t’)^2 – (st – s’t’)^2\). By the difference of two squares, this works out to be \(4sts’t’\).

Similarly, \(b^2 – 1 = (ss’ + tt’)^2 – 1\). By the difference of two squares, this is \((ss’ + tt’ – 1)(ss’ + tt’ + 1)\).

However, \((ss’ + tt’ – 1) = 2tt’\) and \((ss’ + tt’ + 1) = 2ss’\), so \(b^2 -1 = 4sts’t’\).

So, \(c^2 – a^2 = b^2- 1\), which implies \(a^2 + b^2 = c^2 + 1\) as required. ∎

2 Every APT is generated by the algorithm

Proposition: For every triple of positive integers \((a,b,c)\) such that \(a^2 + b^2 = c^2 + 1\), where \(b\) is odd, there exist two positive integers \(s\) and \(t\) such that the algorithm outlined above produces the triple.

Proof:

Note that \(\frac{c-a}{2}\times\frac{c+a}{2} = \frac{b-1}{2}\times\frac{b+1}{2}\), so every factor on the left hand side must also appear on the right hand side.

Let:

• \(s = \gcd\left(\frac{b-1}{2},\frac{c+a}{2} \right)\)
• \(t = \gcd\left(\frac{b+1}{2},\frac{c+a}{2} \right)\)

Note that \(\gcd(\frac{b+1}{2},\frac{b-1}{2})=1\) , and every factor of \(\frac{c+a}{2}\) must be a factor of either \(\frac{b-1}{2}\) or \(\frac{b+1}{2}\), it must be the case that \(\frac{c+a}{2} = st\).

Let:

• \(p = \gcd(\frac{b-1}{2}, \frac{c-a}{2})\)
• \(q = \gcd(\frac{b+1}{2},\frac{c-a}{2})\)

By similar reasoning, \(pq = \frac{c-a}{2}\).

• Since \(\frac{c-a}{2} < \frac{c+a}{2}\), \(pq < st\).
• Since \(\frac{c-a}{2}\times\frac{c+a}{2} = pqst\), I can say \(\frac{b-1}{2}\times\frac{b+1}{2} = pqst\)
• So \(\frac{b-1}{2} = ps\) and \( \frac{b+1}{2}=qt\).

This means \(qt – ps = 1\) with \(pq < st\). The only solution to this in positive integers is \(p = s^{-1}\pmod t\) and \(q=t^{-1}\pmod s\).

Therefore, for any \((a,b,c)\) such that \(a^2 + b^2 = c^2 + 1\), there exists at least one \((s,t)\) pair for which the algorithm generates the APT. ∎

3 No APT is generated more than once

Suppose an APT \((a,b,c)\) is generated by applying the algorithm to coprime integers \((x,y)\) and to coprime integers \((X,Y)\).

This implies:

• \(\frac{c+a}{2} = xy = XY\)
• \(\frac{c-a}{2} = x’y’ = X’Y’\)
• \(\frac{b-1}{2} = xx’ = XX’\)
• \(\frac{b+1}{2} = yy’ = YY’\)

Note that \(yy’ – xx’ = 1\) [*].

Let \(p\) and \(q\) be such that \(X = \frac{p}{q}x\). This implies that \(q\) is a factor of \(x\).

Since \(XY = xy\), \(Y = \frac{q}{p}y\), so \(p\) is a factor of \(y\).

Since \(YY’ = yy’\), \(Y’ = \frac{p}{q}y’\), so \(q\) is a factor of \(y’\). However, since \(\gcd(x,y’)=1\) (by [*]), this implies \(q=1\).

Since \(X’Y’ = x’y’\), \(X’ = \frac{q}{p}x’\), so \(p\) is a factor of \(x’\). However, since \(\gcd(x’,y)=1 \), this implies \(p=1\).

Therefore, if \((x,y)\) and \((X,Y)\) generate the same APT, \(x=X\) and \(y=Y\). ∎

A small wrinkle

We’ve shown that the triple \((a,b,c)\) is only generated once. However, an odd scalene APT is also generated as \((b,a,c)\); odd scalene APTs are thus generated twice by this method.

If we care about this, we can place restrictions on our inputs to insist that \(b \ge a\) if \(a\) is odd.

For \(b \ge a\), we require \(ss’ + tt’ \ge st – s’t’\).

I’m not aware of a simple restriction on \(s\) and \(t\) that satisfies this, although \((s+t’)(s’+t) \ge 2st\) is moderately pleasing as these things go.

Instead, we can simply reject any APTs where \(b < a\).

Consequence

Since (1) every pair of positive coprime integers \((s,t)\) generates an APT, (2) every APT \((a,b,c)\) is generated by at least one seed, and (3) under the restriction every APT is generated by exactly one seed, there’s a bijection between (restricted) coprime integer pairs and almost Pythagorean triples.

As a result, by looping over the coprime positive integers and applying the given restriction, each possible APT is generated exactly once.

Conclusion

In this article, I’ve answered Antalan and Tomenes’s question: yes, there is a simple method to generate almost Pythagorean triples. It’s not clear to me that this is a new result (I haven’t been able to find any more on the topic, but I don’t know if that’s because (a) it’s not been done, (b) it’s been done and I’m looking in the wrong places, or (c) it’s been done and considered too trivial to be worth writing down.)

I haven’t answered Chris’s original question here, which is whether you can find a set of three triangular numbers \(\{x,y,z\}\) such that \(x+y\), \(x+z\), \(y+z\) and \(x+y+z\) are all triangular. The answer to that is also yes, but that’s for another post.

Neither have I explained the link between the puzzle and APTs. I’ll happily send a postcard to the first reader who figures it out!

More information

This article refers to:

• Antalan, J.R.M. and Tomenes, M.D.: A Note on Generating Almost Pythagorean Triples, International Journal Of Mathematics And Scientific Computing, Vol. 5, No. 2, 2015, pp. 100-102
• Frink, O.: Almost Pythagorean Triples, Mathematics Magazine, Vol. 60, No. 4, October 1987, pp. 234-236

I’m grateful to Chris Smith, Dominika Vasilkova and Elizabeth A. Williams for their help with this article.

Post edited 2021-11-22 to fix a typo in the ‘small wrinkle’ section (I had \( > \) instead of \( \ge \)). Thanks to Shlomi Fish for pointing out the error.