Path: news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail
From: Mike Terry <news.dead.person.stones@darjeeling.plus.com>
Newsgroups: rec.puzzles
Subject: Re: Pythagorean Primitives
Date: Fri, 27 Jun 2025 01:20:27 +0100
Organization: A noiseless patient Spider
Lines: 116
Message-ID: <103ko4c$3o9gs$1@dont-email.me>
References: <103352u$l35p$2@dont-email.me>
 <c96608ab99caab054afe90673ef69520@www.novabbs.com>
 <1034dml$7dg8$1@dont-email.me> <CYf*E6WfA@news.chiark.greenend.org.uk>
MIME-Version: 1.0
Content-Type: text/plain; charset=windows-1252; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Fri, 27 Jun 2025 02:20:29 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="d77d5378345e83feb5e80582f8ac6988";
	logging-data="3941916"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX18zOwUomwiimo44MPpoxgaGAO9fcIEoOfs="
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101
 Firefox/91.0 SeaMonkey/2.53.18.2
Cancel-Lock: sha1:AtoBzvCECGAVkCHyjwsGOBYpphU=
In-Reply-To: <CYf*E6WfA@news.chiark.greenend.org.uk>

On 25/06/2025 19:05, Gareth Taylor wrote:
> 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
> 

Excellent work!
Mike.