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
--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)