From Newsgroup: rec.puzzles

On Fri, 20 Jun 2025 13:30:12 -0400, Charlie Roberts
<croberts@gmail.com> wrote:

I could not make progress on the elegant front. For the above
a(2) problem, we need to find a pair of doublets (u1, v1)
and (u2, v2) such that

u1^2 + v1^2 = u2^2 + v2^2 (same hypotenuse)
u1 and v1 are coprime with only one being even and
u2 and v2 are coprime with only one being even.

Not sure if this is even the correct approach!
For n = 3, 4, .... the conditions of the triplets,
quadraplets, ..... grow and it seems a rather
unwieldly approach.

Waiting for others to make the breakthrough.

After much time the flourescent light faintly flickered ....
I remembered Fermat's theorem about factoring integers
into a sum of two primes.

https://en.wikipedia.org/wiki/Fermat%27s_theorem_on_sums_of_two_squares

But, the light died .... I was headed the wrong way as
I that the the squares related the two right sides of the
Pythagorean triangle. Fortunately, there are smarter
people in the world. The trick is to associated the
squares with the hypotenuse as we have

u1^2 + v1^2 = u2^2 + v2^2 = c

where c is the common hypotenuse. How this is used
can be read at

https://math.stackexchange.com/questions/3972140/find-exactly-3-matching-primitive-pythagorean-triples-for-a-given-hypotenuse

which shows a(2) = 65 as Ilan Mayer found. But, the
critical thing different here is whether there is a triplet
of Pythagorean primes. The poster concludes with

" .... tests for 4-triples, 5-tiples, 6-triples and 7-triples but, in
all [my admittedly limited] cases, only an even number of them were
primitive."

So is a(n) even for all n > 1??

The story continues in

https://math.stackexchange.com/questions/4979408/show-that-1105-is-the-smallest-hypothenuse-for-which-four-distinct-primitive-p

where the a(4) = 1105 is analysed.

Here, the statement

"The number of "primitive" triples for any side of a Pythagorean
triple is 2^(n-1), where n is the number of unique prime factors of
that side length. There may be more imprimitives than this but not
primitives."

is made, but I cannot figure out where it comes from. Please post if
you can shed light of this.

But, this seems crucial to the issue. Some manual search is still
required, but I doubt there is a nice closed form answer to David's
initial problem.
--
This email has been checked for viruses by Avast antivirus software. www.avast.com
--- Synchronet 3.21a-Linux NewsLink 1.2

From Newsgroup: rec.puzzles

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
--- Synchronet 3.21a-Linux NewsLink 1.2

From Newsgroup: rec.puzzles

On Tue, 24 Jun 2025 15:18:46 -0400, Charlie Roberts
<croberts@gmail.com> wrote:

On Fri, 20 Jun 2025 13:30:12 -0400, Charlie Roberts
.....

"The number of "primitive" triples for any side of a Pythagorean
triple is 2^(n-1), where n is the number of unique prime factors of
that side length. There may be more imprimitives than this but not >primitives."

Well, the goose may have finally been cooked (for me, at least).

It took a little reading, which always helps. I pushed back the
frontiers of my (meagre) knowledge of number theory, especially the
territory around Fermat's theorem of expressing an integer as the sum
of two squares.

My previous post indicated a route to finding the number of distinct Pythagorean primitives for a given hypotenuse. In https://math.stackexchange.com/questions/4979408/show-that-1105-is-the-smallest-hypothenuse-for-which-four-distinct-primitive-p

the following statement is made

"The number of "primitive" triples for any side of a Pythagorean
triple is 2^(n-1), where n is the number of unique prime factors of
that side length. There may be more imprimitives than this but not
primitives."

but no proof (or pointers to a proof) is given.

But, I did find almost everything in this page:

https://nonagon.org/ExLibris/fermat-sum-two-squares-calculator

In the section headed "Fundamental Theorem on Sums of Two Squares"

it is stated that for a given number n such that

n = 2^k*(p1^a1)(p2^a2)... (pr^ar)(q1^b1)(q2^b2)....(qs^bs)

where the pi are distinct primes with pi=1 (mod4) and the qi are
distinct primes with qj=3 (mod4). Then, n is expressible as the sum of
two squares if and only if the bj are all even. The number of distinct solutions is given by

ceiling{(a1+1)(a2+1)....(ar+1)/2}

A pointer to a proof is quoted. (This result was completely new to
me.)

I guess that is pretty much it.

As the hypotenuse c has to be odd, k=0. Further, the 4k+3 type prime
factors do not give any "extra" solutions as the number is completely
decided by the 4k+1 primes. So, it makes sense to start with only
these primes.

For a minimal primitive we need a1=a2= ...... =ar=0 and we get the
number of disctinct solutions as 2^(r-1).

Thanks, David, for this problem. I am a number theory "hobbyist" and
this helped to expand my horizons a wee bit.
--
This email has been checked for viruses by Avast antivirus software. www.avast.com
--- Synchronet 3.21a-Linux NewsLink 1.2

From Newsgroup: rec.puzzles

In article <sm7r5k1qn6jir93tn8jl4nlo75j5uqiufq@4ax.com>,
Charlie Roberts <croberts@gmail.com> wrote:

Well, the goose may have finally been cooked (for me, at least).

"The number of "primitive" triples for any side of a Pythagorean
triple is 2^(n-1), where n is the number of unique prime factors of
that side length. There may be more imprimitives than this but not primitives."

but no proof (or pointers to a proof) is given.

Hello. Yesterday, I posted some maths waffle in a reply elsewhere in
this thread. I mention it partly in case you missed it, but partly in
case it hasn't shown up at all. (I haven't posted to a newsgroup for
ages and might have got it wrong!)

Gareth
--- Synchronet 3.21a-Linux NewsLink 1.2

From Newsgroup: rec.puzzles

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.


--- Synchronet 3.21a-Linux NewsLink 1.2

From Newsgroup: rec.puzzles

On 25 Jun 2025 19:05:44 +0100 (BST), Gareth Taylor wrote:

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.

Thanks Gareth for the comprehensive and clear explanation.

That's an great insight.
--
David Entwistle
--- Synchronet 3.21a-Linux NewsLink 1.2

From Newsgroup: rec.puzzles

On 26 Jun 2025 21:08:31 +0100 (BST), gtaylor@chiark.greenend.org.uk
(Gareth Taylor) wrote:

In article <sm7r5k1qn6jir93tn8jl4nlo75j5uqiufq@4ax.com>,
Charlie Roberts <croberts@gmail.com> wrote:

Hello. Yesterday, I posted some maths waffle in a reply elsewhere in
this thread. I mention it partly in case you missed it, but partly in
case it hasn't shown up at all. (I haven't posted to a newsgroup for
ages and might have got it wrong!)

Gareth

Thanks for pointing it out. I missed it and would have not gone back
at all if you had not pointed it out. As I have not got to the
Gaussian integers yet, I certainly was in the dark. More to learn!
--
This email has been checked for viruses by Avast antivirus software. www.avast.com
--- Synchronet 3.21a-Linux NewsLink 1.2