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: References: <103352u$l35p$2@dont-email.me> <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 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