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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/