Path: nntp.eternal-september.org!news.eternal-september.org!eternal-september.org!feeder3.eternal-september.org!nntp-feed.chiark.greenend.org.uk!ewrotcd!.POSTED.chiark.greenend.org.uk!not-for-mail
From: gtaylor@chiark.greenend.org.uk (Gareth Taylor)
Newsgroups: rec.puzzles
Subject: Re: Pythagorean Primitives
Date: 25 Jun 2025 19:05:44 +0100 (BST)
Organization: SGO
Message-ID: <CYf*E6WfA@news.chiark.greenend.org.uk>
References: <103352u$l35p$2@dont-email.me> <c96608ab99caab054afe90673ef69520@www.novabbs.com> <1034dml$7dg8$1@dont-email.me>
Injection-Info: chiark.greenend.org.uk; posting-host="chiark.greenend.org.uk:93.93.131.173";
	logging-data="12322"; mail-complaints-to="abuse@chiark.greenend.org.uk"
X-Newsreader: trn 4.0-test77 (Sep 1, 2010)
Originator: gtaylor@chiark.greenend.org.uk ([93.93.131.173])

In article <1034dml$7dg8$1@dont-email.me>,
David Entwistle  <qnivq.ragjvfgyr@ogvagrearg.pbz> wrote:

> "a(n) is the product of the first n primes congruent to 1 (mod 4)". 
>
> Does anyone have any insight into why that would be so?

Warning, incoming maths!  But I've tried to make it friendly and 
legible.

It comes down to factorisations in the "Gaussian integers", which are 
numbers of the form a+bi, with a, b integers and i = sqrt(-1).

For example, using these we can now factorise 5 = (2+i)(2-i), but we
can't factorise 7 any more than it already is.

It can be shown (proof omitted!) that all integer primes which are 1 mod 
4 factorise as (a+bi)(a-bi) for some a, b, and moreover that there is 
only one such factorisation.  (Well, only one up to moving irrelevant 
factors of -1 or +-i around, e.g. writing 5 = (1+2i)(1-2i) instead).  
The prime 2 also factorises, as (1+i)(1-i), but that's not going to 
matter to us.

And integer primes which are 3 mod 4 don't factorise.  This is easier to 
show.  Suppose that p = (a+bi)(c+di) for prime p which is 3 mod 4. 
Multiplying both sides by their complex conjugates gives p^2 = 
(a^2+b^2)(c^2+d^2), a factorisation in the integers.  So we must have 
a^2+b^2 = c^2+d^2 = p.  However, you can't write any number which is 3 
mod 4 as a sum of two squares: working mod 4, even numbers square to 0 
and odd numbers square to 1, so a^2+b^2 can only ever be 0 or 1 or 2 mod 
4, and so can never equal p since that's 3 mod 4.

Suppose that we have a primitive Pythagorean triple: a^2 + b^2 = c^2.

First, c must be odd.  If c is even then the right-hand side is 0 mod
4, and then a and b must both be even.  (As above: if exactly one is
odd then the left-hand side is 1 mod 4, and if both are odd then it's
2 mod 4.)  But if all three are even then the triple isn't primitive.

Can c have any prime factor p which is 3 mod 4?  No.  Suppose it did,
and factorise the left-hand side as (a+bi)(a-bi).  Since p itself
doesn't factorise in the Gaussians, we get that each of a+bi and a-bi
is a multiple of p, so that a and b themselves are multiples of p, and
so again the triple isn't primitive.

So c's prime factors are all of the form 1 mod 4.  Now we factorise each 
of those primes in the Gaussians.  To make a^2+b^2, we aim for 
(a+bi)(a-bi), by gathering together one of each pair of complex factors 
making up each prime to form a+bi, and then gathering their conjugates 
to form a-bi.

For example, c = 1105 = 5 x 13 x 17.

In the Gaussians, c = (2+i)(2-i) x (2+3i)(2-3i) x (4+i)(4-i)

So the factorisation of c^2 has each of these twice.

Grouping gives the following choices for a+bi.

   [(2+i)(2+3i)(4+i)]^2 = [-4 + 33i]^2 = -1073 +  264i
   [(2+i)(2+3i)(4-i)]^2 = [12 + 31i]^2 =  -817 +  744i
   [(2+i)(2-3i)(4+i)]^2 = [32 - 9i]^2  =   943 -  576i
   [(2+i)(2-3i)(4-i)]^2 = [24 - 23i]^2 =    47 - 1104i

(While there are eight choices of the plus or minus signs for the three 
factors, there are only four products listed because in each case our 
product gives one of a+bi and a-bi and then the other is forced.  
Equivlently, we could assume that we'll choose plus for the first factor 
and then choose the other two freely.  This is where 2^{n-1} comes from 
the final answer.)

So we get 1105^2 equals:

   1073^2 +  264^2
    817^2 +  744^2
    943^2 +  576^2
     47^2 + 1104^2

Note that on the way we also found all ways to write 1105 itself as a
sum of two squares:

    4^2 + 33^2
   12^2 + 31^2
   32^2 +  9^2
   24^2 + 23^2

If the prime factors aren't distinct then we can still do this but we
get less choice.  For example, c = 325 = 5 x 5 x 13.

In the Gaussian, c = (2+i)^2 x (2-i)^2 x (2+3i) x (2-3i)

We can now only group them as:

   [(2+i)^2 (2+3i)]^2 = [-6+17i]^2 = -253 - 204i
   [(2+i)^2 (2-3i)]^2 = [18-i]^2   =  323 -  36i

We can't choose (2+i)(2-i)(2+3i) because then both it and its complex 
conjugate are multiple of 5, and the triple isn't primitive.

So we get 325^2 has two non-primitive ways:

   253^2 + 204^2
   323^2 +  36^2

Hence, to get the smallest number with a given number of distinct
ways, we need c to be a product of the first N primes which are 1 mod
4, and then there are 2^{N-1} ways.

Gareth