Hi all,
There is an infinite number of solutions for a² +b² =c² for a,b,c natural numbers. It seems obvious, but how can one prove (or disprove) that there are infinitely many c, for which there are no a,b with
a² +b² =c² ?
Thanks a bunch, J.

This is interesting - it looks so obvious but it isn't really.

Let's try a proof by contradiction. Suppose there are only a finite number of c whose square can't be expressible as the sum of two squares. Let the largest one of these be d-1. So for all c > = d, we can express its square as the sum of two squares. Now if you look at Kerwin Hui's posting under Statue of Anonymous (on Pythagorean triples, under the discussion entitled Help!!!!) he demonstrates that for any Pythagorean triple:

a² + b² = c²

we can always express a b c as:

a = p² - q²
b = 2pq
c = p² + q²

without loss of generality.

But we know all c² bigger than d² form part of a Pythagorean triple. So this means that all integers c (which are > = d) are expressible as the sum of two squares.

Consider all the integers between 1 and e² for some e. How many of these integers can we possibly hope to hit with the sum of two squares.

Well clearly only the squares 1² 2² ... e² come into it (anything bigger is useless). The number of ways of choosing two of these squares is:

e + (e-1) + (e-2) + ... + 1 = (1/2)e(e+1)

This is therefore an overestimate for the number of numbers between 1 and e² that are expressible as the sum of two squares.

So the percentage of the numbers between 1 and e² that can be hit with the sum of two squares is no more than:

(1/2)e(e+1) / (e² )

which tends to 1/2 as e tends to infinity. But if all the numbers past a certain value d could be hit with the sum of two squares, this would tend to 1 as e tended to infinity, not 1/2. This is therefore a contradiction, meaning that there are infinitely many c where c² cannot be written as the sum of two squares.

Somebody check that please,

Michael

An easier (?) way to show that there are infinitely many integers which are not the sum of two squares is as follows:

It is easy to check that any square number is congruent to 0 or 1 (mod 4) (just work out 0² (mod 4), 1² (mod 4), 2² (mod 4) and 3² (mod 4)), so any sum of two squares must be congruent to 0, 1 or 2 (mod 4). Therefore, any number which is congruent to 3 modulo 4 (and there are infinitely many of these) cannot be expressed as the sum of two squares.

This trick of looking at an equation modulo a certain number is often quite useful when dealing with equations with integers.

James.

However, this doesn't prove that there are infinitely many numbers c for which there are no a,b with

a² + b² = c²

as if you look again at Kerwin's message it says (something like) "assuming a,b,c is a Pythagorean triple with h.c.f.(a,b,c) = 1 ". This is because if a,b,c is a Pythagorean triple then ka,kb,kc for any integer k is also a Pythagorean triple. So c doesn't have to be a sum of two squares -- it just has to be a multiple of a sum of two squares.

However, if c is prime then it must be a sum of two squares (as if it were k(x² + y² ) for k > 1 then it wouldn't be prime), and it is possible to show that there are infinitely many prime numbers p with p = 3 (mod 4).

There is a proof of this which is a modification of the standard proof that there are infinitely many prime numbers (by considering n! - 1). The proof goes as follows, by contradiction:

Suppose there are only a finite number of primes of this form -- and so let p be the largest of these primes. Then let q = p! - 1. Then p > 4 and so p! is a multiple of 4, so q is congruent to 3 modulo 4.

Now q is not divisible by any number less than or equal to p. But if q is prime we have a contradiction, since q is greater than p, which we assumed to be the greatest such prime. So q is composite, but all its prime factors are greater than p.

But suppose all of its prime factors are congruent to 1 modulo 4 (note that they must be congruent to either 1 or 3 modulo 4 since p is odd). But then q must be congruent to 1 modulo 4 (is it clear why this is true?), and so at least one of the prime factors of q, call this factor s, must be congruent to 3 modulo 4. But s is greater than p -- another contradiction.

Therefore there must be an infinite number of primes of this form.

I hope that this is clear (and correct!) - please tell me if it is not. This result is a particular case of a theorem which says that if A and B are positive integers with h.c.f.(A, B) = 1, then the arithmetic progression An + B is prime for infinitely many values of n, but this general result is extremely hard to prove.

Hope that helps,

James.

Thanks,

James,
Your proof about primes of the form 4n+3 is fine, but I don't understand how it relates to the problem?
Thanks a lot, J.

As James has pointed out my statement that c is always the sum of two squares is false as I misread Kerwin's message. However James' method does fix this problem. I'm still looking if you can do it using the first way, in which you show there simply aren't enough square pairs to reach all the desired numbers. It does show that no more than half of the set of natural numbers can be written as the sum of two squares (and almost certainly a lot less than half) but this isn't quite good enough.

Yours,

Michael

Two possible extensions to the problem:

1) Are there an infinite number of c which aren't one fewer than a multiple of 4 and prime, but such that there don't exist a,b where a² + b² = c² ?

2) If f(n) = no. of numbers between 1 and n that are expressible as a² + b² , what is f(n)/n as n tends to infinity? We know this is less than 1/2. We can probably do a great deal better than this, because in my message above I counted all pairs of squares which included squares from 1² to e² . Loads of these pairs will actually sum to numbers bigger than e² so should be discounted. This should be quite easy. Also some square pairs will sum to the same thing as other square pairs. It will be hard to get round that. When I get a bit of time later, I'll have a go.

Yours,

Michael

J,

The reason that it relates to the question is that if we can show that there are infinitely many prime numbers that aren't the sum of two squares, then we have shown that there are infinitely many numbers c which can't be solutions to a² + b² = c² . This is because any c satisfying this equation must be of the form c = k(p² + q² ) for some integers k,p and q. Now if c is prime, (assuming p =/= 0, q =/= 0) p² + q² > 1, and so k must be 1. Therefore c = p² + q² . Sorry if I haven't explained that very well.

Michael,

In one of my courses this year, we proved the following theorem, which should give a definite answer to your questions - in fact I think it should be able to tell us exactly which numbers are the c of a Pythagorean triple.

The theorem states:

"A positive integer n is the sum of two squares if and only if all the prime factors of n which are congruent to 3 modulo 4 occur to an even power in n."

The proof of this is quite long -- in our lecture course it took 2 lectures to prove it, although in doing so we actually found out lots about much more general questions, but even to prove this specific case would be quite long. If you're interested I shall try and write out a proof though.

Now we know that a² + b² = c² for some a,b if and only if c = k(p² + q² ) for some k,p,q, where p,q > 0, p =/= q (this prevents a or b from being 0). I am going to call such a value of c "Pythagorean". c is Pythagorean if (but not necessarily "only if") c/k is the sum of two non-equal, non-zero squares for some k.

Let us write p = 2ⁿ (p_1)^a_1 ...(p_r)^a_r (q_1)^b_1 ...(q_s)^b_s where the p_i and q_i are distinct primes and p_i = 1 (mod 4) and q_i = 3 (mod 4).

To make the theorem apply, let us take k = (q_1)^{b_1 % 2} ...(q_s)^{b_s % 2} where b_i % 2 means b_i modulo 2. So k is a product (once each) of all the primes modulo 3 which occur to an odd power in c. But then c/k might be a square or 2 times a square. We are OK if c has a prime factor p_i congruent to 1 modulo 4 as we just make j = p_i * k, and then c/j still satisfies the conditions of the theorem, but is not a square or 2 times a square.

So we have shown that c is Pythagorean if it has a prime factor congruent to 1 modulo 4. But what if c does not have any factors congruent to 1 modulo 4? Is it possible that c is Pythagorean then?

Well by the theorem, we cannot have c/k Pythagorean unless c/k = 2^m M² for some m,M. Let's think first about the case where c is odd. But then we're considering c/k = M² , and we know that M² can only be a sum of two non-zero, non-equal squares if M is Pythagorean, but then by induction we have that c is not Pythagorean (is this OK? I think that this is correct if you think about it long enough...).

However, if c is even and has no prime factors congruent to 1 modulo 4 then I'm not sure how to continue. I shall think about this - if you have any ideas then let me know. I hope I haven't confused you too much - I'm slightly confused myself :-)

James.

Obviously c=1 cannot work.
If c=2n then c² =0(mod4)
So a² + b² =0(mod4), because as x² cannot be =3(mod4),
a² =0(mod4)
b² =0(mod4)

so a and b are both even, a=2m, b=2l
but therefore
a² +b² =c²
means 4m² +4l² =4n²
m² +l² =n²

so if 2n is the longer side of a pythagorean then so also is n

so c=2 works if c=1 works, which it doesn't
c=4 works if c=2 works, which it doesn't
c=2^(y+1) works if c=2^y works, which it doesn't
so none of the numbers c=2^y works

Sorry the grammar in this is so bad/absent but its late and I have physics A-level tomorrow. I hope this is right as well!

That looks correct to me. So by a slight generalisation we have that (with my previous terminology) c is Pythagorean iff it has a prime factor which is congruent to 1 modulo 4.

James.

James - Surely -1 is a quadratic non-residue mod p if p is a prime congruent to 3 mod 4 as (-1|p)=(-1)^(p-1)/2 . So if n is divisible by a prime p(p = 3 mod 4) and n=x² +y² then we have x² = -y² mod p. Thus we must have x² = y² = 0 mod p. If n is to be square-free, we would obtain a contradiction, as required.

Kerwin

Kerwin,

I'm not quite sure how this helps with the problem. Can you please explain exactly what this shows - as far as I can see you have shown that if n = x² + y² and p|n (with p = 3 (mod 4)) then p² |n, but I can't see why this is helpful - it also follows from the theorem quoted above. Sorry if I am being stupid,

James.

Well, the complete proof that a number n can be expressed in the form x² +y² if and only if every prime divisors p = 3 mod 4 occurs to an even power in the standard factorisation of n can run as follow:

Let n be a natural number such that n=x² +y² . From the above message, we have p|x and p|y, so we have n'=n/p² =(x/p)² +(y/p)² . Thus we can proof that if a prime p congruent to 3 mod 4 such that p divides n, we can prove that p² divides n, so the result is established by induction.

To proof the converse it suffice to assume that n is square-free and to show than if odd prime divisors of n satisfies p = 1 mod 4 then n is expressible in the form x² +y² , since n=x² +y² gives a² n=(ax)² +(ay)² . Now the discriminant of x² +y² is -4, thus it is the only reduced form and n is properly represented by x² +y² if and only if x² = -4 mod 4n is solvable. But -1 is a quadratic residue mod p for all p divides n. Hence -1 is a quadratic residue mod n and the result follows.

Another way is to use the identity
(a² +b² )(c² +d² )= (ac-bd)² +(ad+bc)²
and the fact that every prime p = 1 mod 4 can be expressed as sum of two square, which can be easily proven by taking norm in gaussian field.

Kerwin

Oops, I forgot to add that since 2=1² +1² , the fact that n is even or odd has no effect on whether n is expressible in terms of x² +y² or not.

Kerwin

OK, but there's still a lot of unproven material in your proof - e.g. the theory about reduced forms.

I'm interested by your comment about proving that a prime p = 1 (mod 4) can be expressed as the sum of two squares - can you explain please?

James.

James,

The message above is meant to be an outline of the proof.

N(l)N(p)=p²

so either N(l), N(p) are the pair 1, p² in any order, or

N(l)=N(p)=p

if p º 3 mod 4 then clearly the former apply, whereas if p º 1 mod 4 we have -1 to be a quadratic residue mod p, so p divides x²+1=(x+i)(x-i) for some integer x. If p is a Gaussian prime then p divides either (x+i) or (x-i), but (x/p±i/p) is not a Gaussian integer, so we have p is not a Gaussian prime and thus N(l)=N(p)=p. Now

l = a+ibÞ N(l)=a²+b². This completes the proof that p º 1 mod 4 can be expressed as the sum of two squares.
Kerwin

Wow! Looks like I'm a bit out of my league here. Anyway, I had a quick attempt at deriving the percentage of numbers which are Pythagorean, and have got an overestimate in terms of an integral which I can't evaluate. Anyway, I'll have more time to work on this once my Chemistry exam is over. (Tomorrow)