[SOLVED] Sum of Two Squares

Hello all, I've been reading up on numbers that are equal to the sum of two squares. As an example, 5 = 4 + 1 = 2^2 + 1^2, and 100 = 64 + 36 = 8^2 + 6^2. There are a few numbers in my book that say they may or may not be perfect squares. They are listed below

A. 7
B. 19
C. 1295

I believe that none of them are sums of squares because I've found no combinations to indicate so. However, I could be wrong.

Here's the catch: The book says that IF the numbers are NOT sums of squares, it can be proven that they aren't by utilizing the number 4. Can anybody help prove this for me for A,B,C (if indeed they are not sums of squares) ?

All help is very much appreciated!

Quote:

---

Originally Posted by Samson

Hello all, I've been reading up on numbers that are equal to the sum of two squares. As an example, 5 = 4 + 1 = 2^2 + 1^2, and 100 = 64 + 36 = 8^2 + 6^2. There are a few numbers in my book that say they may or may not be perfect squares. They are listed below

A. 7
B. 19
C. 1295

I believe that none of them are sums of squares because I've found no combinations to indicate so. However, I could be wrong.

Here's the catch: The book says that IF the numbers are NOT sums of squares, it can be proven that they aren't by utilizing the number 4. Can anybody help prove this for me for A,B,C (if indeed they are not sums of squares) ?

All help is very much appreciated!

---

Do you want to know the actual statement to prove ? I won't give the proof if you don't want me to.

Quote:

---

Originally Posted by Bacterius

Do you want to know the actual statement to prove ? I won't give the proof if you don't want me to.

---

Sure, you can give it. I'm sure it will help me understand better than what I do now.

Quote:

---

Originally Posted by Samson

Sure, you can give it. I'm sure it will help me understand better than what I do now.

---

All right. There is theorem that states that :

Quote:

---

Any number of the form (or ) may not be represented as the sum of two squares.
Any number of the form may be represented as the sum of two squares.

---

You just have to prove this now :D

Please note I made an error when I first posted, so please reread the theorem if you read the false one.

If you want to read about it online, you can google "Fermat's theorem on sums of two squares" and "Brahmagupta–Fibonacci identity."

Quote:

---

Originally Posted by Bacterius

All right. There is theorem that states that :



You just have to prove this now :D

Please note I made an error when I first posted, so please reread the theorem if you read the false one.

---

So how do I actually prove this and relate it to my discrete examples?

Oh, you want the proof ? :(
I guess a quick google search will have you sorted out (with the keywords provided with undefined).
Don't you want to think around before looking at the proof ?

Quote:

---

Originally Posted by Samson

So how do I actually prove this and relate it to my discrete examples?

---

You might not understand any of these proofs. :-/

Proofs of Fermat's theorem on sums of two squares

Certainly, if you don't see how to apply it (which should be obvious, although I understand you may not be used to the notation, and congruence arithmetic in general), then you will have massive difficulty following the steps.

Quote:

---

Originally Posted by Bacterius

Oh, you want the proof ? :(
I guess a quick google search will have you sorted out (with the keywords provided with undefined).
Don't you want to think around before looking at the proof ?

---

I've looked over the links and they seem way out in left field compared to what I'm able to relate too, although I do believe there should be simpler ways of reaching the formal conclusions. I would do additional thinking but I'm roadblocked which is why I posted this :-(

Quote:

---

Originally Posted by Samson

I've looked over the links and they seem way out in left field compared to what I'm able to relate too, although I do believe there should be simpler ways of reaching the formal conclusions. I would do additional thinking but I'm roadblocked which is why I posted this :-(

---

Fermat's theorem on sums of two squares:

For an odd prime p, there exist integers x, y such that p = x^2 + y^2 if and only if p is congruent to 1 (mod 4).

Some notes:

1) This theorem is "if and only if." The two parts (directions) "if" and "only if" may be considered separately. As the Wikipedia article states, the "only if" direction is much simpler than the "if" direction.

2) p is congruent to 1 (mod 4) is another way of saying that there exists an integer k such that p = 4k + 1.

If you have a basic understanding of modular arithmetic (also known as congruence arithmetic), then you will understand the "only if" part of the proof and be able to answer your book's question.

That is, you will know that if an odd prime is congruent to 3 (mod 4) then it cannot possibly be the sum of two squares.

Quote:

---

Originally Posted by undefined

Fermat's theorem on sums of two squares:

For an odd prime p, there exist integers x, y such that p = x^2 + y^2 if and only if p is congruent to 1 (mod 4).

Some notes:

1) This theorem is "if and only if." The two parts (directions) "if" and "only if" may be considered separately. As the Wikipedia article states, the "only if" direction is much simpler than the "if" direction.

2) p is congruent to 1 (mod 4) is another way of saying that there exists an integer k such that p = 4k + 1.

If you have a basic understanding of modular arithmetic (also known as congruence arithmetic), then you will understand the "only if" part of the proof and be able to answer your book's question.

That is, you will know that if an odd prime is congruent to 3 (mod 4) then it cannot possibly be the sum of two squares.

---

Okay, so let me try and apply this:
7 = 3(mod 4) --> (3-7)/4 = -1 OK
19 = 3(mod 4) --> (3-19)/4 = -4 OK
1295 = 3(mod 4) --> (3-1295)/4 = -323 OK

Is this feasible in proving this provided that I list the statement: "if an odd prime is congruent to 3 (mod 4) then it cannot possibly be the sum of two squares" and cite which Fermat theorem I got it from?

Quote:

---

Originally Posted by Samson

Okay, so let me try and apply this:
7 = 3(mod 4) --> (3-7)/4 = -1 OK
19 = 3(mod 4) --> (3-19)/4 = -4 OK
1295 = 3(mod 4) --> (3-1295)/4 = -323 OK

Is this feasible in proving this provided that I list the statement: "if an odd prime is congruent to 3 (mod 4) then it cannot possibly be the sum of two squares" and cite which Fermat theorem I got it from?

---

Umm that's not how you're supposed to do it. :(

We ask: Is 7 prime? Yes. Is 7 congruent to 3 (mod 4)? This means, when we divide 7 by 4, do we get remainder 3? Yes. So 7 is not the sum of two squares.

Same applies to 19.

1295 we can't say (without invoking the Brahmagupta–Fibonacci identity), because it is not prime.

Quote:

---

Originally Posted by undefined

Umm that's not how you're supposed to do it. :(

We ask: Is 7 prime? Yes. Is 7 congruent to 3 (mod 4)? This means, when we divide 7 by 4, do we get remainder 3? Yes. So 7 is not the sum of two squares.

Same applies to 19.

1295 we can't say (without invoking the Brahmagupta–Fibonacci identity), because it is not prime.

---

But 1295 can't be written as a sum of two squares. How can this be proven then without using this identity?

Quote:

---

Originally Posted by Samson

But 1295 can't be written as a sum of two squares. How can this be proven then without using this identity?

---

From this article on Wikipedia:

"Since the Brahmagupta–Fibonacci identity implies that the product of two integers that can be written as the sum of two squares is itself expressible as the sum of two squares, this shows that any positive integer, all of whose odd prime factors congruent to 3 modulo 4 occur to an even exponent, is expressible as a sum of two squares. The converse also holds."

1295 = 5 * 7 * 37

So, you are right, 1295 cannot be expressed as a sum of two squares.

Quote:

---

Originally Posted by undefined

From this article on Wikipedia:

"Since the Brahmagupta–Fibonacci identity implies that the product of two integers that can be written as the sum of two squares is itself expressible as the sum of two squares, this shows that any positive integer, all of whose odd prime factors congruent to 3 modulo 4 occur to an even exponent, is expressible as a sum of two squares. The converse also holds."

1295 = 5 * 7 * 37

So, you are right, 1295 cannot be expressed as a sum of two squares.

---

So the best way to describe it for 1295 is to show those odd prime factors and explain that since 7 is one of them, this means that it cannot be the sum of two squares (because 5 and 37 both can be written as the sum of 2 squares, but 7 cannot). Does that seem correct?