x^2 + y^2 Is Composite?

Date: 01/30/2003 at 21:38:59
From: Allan
Subject: Discrete Mathematics

Prove or give a counterexample: 

   For all integers, if x + y is composite and x - y is composite, 
   then x^2 + y^2 is composite.

I know a composite number is an integer b such that a|b and 1<a<b. So 
there is a number c such that a*c=b, by definition of divisibility. I 
get this far and think, okay, so x+y is equal to a composite number so 
that x+y= a*c and for the other x-y= g*h. This also holds true for 
x^2+y^2= e*f. Now this is where I get stuck. I have six different 
variables, which is probably incorrect. I know that this is probably a 
very simple problem but I am completly confused. Any help would be 
appreciated.

Thank you, Dr. Math!

Date: 01/31/2003 at 17:30:59
From: Doctor Marshall
Subject: Re: Discrete Mathematics

Hi Allen, 

Interesting question. I looked for a way to prove it for a 
long time, then decided to play with some numbers to see if I might 
understand it better. I came up with this:

  for x=47, y=2

  (47 + 2)       = 7^2 is composite

  (47 - 2)       = 3^2 * 5 is composite

  (47^2) + (2^2) = 2113 is prime.


(To check for primality, I used the list of The First 10,000 Primes 
from the University of Tennessee at Martin at

   http://www.utm.edu/research/primes/lists/small/10000.txt 

It's possible that many other combinations would work. Here's how I
chose this one.  

I decided to look for a counter-example. That requires (x^2 + y^2) to
be prime, which requires that exactly one of the numbers (x,y) be odd. 
(If they are both odd or even, then the sum of their squares is even, 
and composite without a contest.)

Now, let's recognize that

  x^2 + y^2 = x^2 - y^2 + 2y^2 

            = (x-y)(x+y) + 2y^2. 

Now, if exactly one of the numbers (x,y) is odd, then both (x-y) and
(x+y) must be odd. Since (x-y) and (x+y) are assumed to be composite,
there exists a number n that divides (x-y) and a number m that divides
(x+y), such that neither n nor m is even.

Let's assume that n=m, i.e., that (x-y) and (x+y) share a common
divisor. Then n divides ((x+y) - (x-y)), which is equal to 2y. Hence
n, which is odd, divides y.

Now we can show that n divides (x^2 + y^2) because 

  x^2 + y^2 = (x-y)(x+y) + 2y^2

and n divides each of these terms. Therefore, if n=m, our number 
(x^2+y^2) is composite.

So I found TWO ODD, COMPOSITE numbers WITHOUT a COMMON DIVISOR, and 
it worked. 

I hope this facilitates a better understanding of the problem; 
however, some insight into why this might generally not be valid might
help you (and me) out more. 

Is it possible, for example, that for EVERY pair of odd composites 
(x-y) and (x+y) without a common divisor, it must be true that
(x^2 + y^2) is prime? I don't know.

I hope this helps (a little bit).  Feel free to write back if you have
questions.

- Doctor Marshall, The Math Forum
  http://mathforum.org/dr.math/