## Pythagorean Primes

Last Week, we had a look at Pythagorean triples. Remember: a Pythagorean triple is three natural numbers (positive integers) such that $a^2+b^2=c^2$. Most of the times, even with $a$ and $b$ natural numbers, $c$ is irrational. Sometimes $c$ is prime; sometimes $c^2$ is. Is either frequent?

Let’s begin with finding triples where $c$ is a prime number. We basically run last week’s program (or rewrite it in Mathematica). We find that there are only 89 such triples for $0. They're barely visible (click to embiggen):

The first few primes are given by sequence A002144 of Sloane’s On-line encyclopedia of integer sequences. They are also all of the form $4k+1$. This form of primes is useful for quadratic residue probing in hash tables, for example.

How about triples where $c^2$ is prime? (it implies that $c$ is irrational). Intuitively, we might think that they must be rare, but intuition is often lead astray. Indeed:

That’s a big surprise (to me, at least): about 1 out of 10 (squared) hypotenuse is square. Is this a useful way to generate (random) prime numbers efficiently?