Page 1 of 2 12 LastLast
Results 1 to 15 of 19

Math Help - [SOLVED] Sum of Two Squares

  1. #1
    Member
    Joined
    Jun 2010
    From
    United States
    Posts
    200

    [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!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member Bacterius's Avatar
    Joined
    Nov 2009
    From
    Wellington
    Posts
    927
    Quote Originally Posted by Samson View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Jun 2010
    From
    United States
    Posts
    200
    Quote Originally Posted by Bacterius View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member Bacterius's Avatar
    Joined
    Nov 2009
    From
    Wellington
    Posts
    927
    Quote Originally Posted by Samson View Post
    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 :

    \Rightarrow Any number of the form 4k - 1 (or 4k + 3) may not be represented as the sum of two squares.
    \Rightarrow Any number of the form 4k + 1may be represented as the sum of two squares.
    You just have to prove this now

    Please note I made an error when I first posted, so please reread the theorem if you read the false one.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    If you want to read about it online, you can google "Fermat's theorem on sums of two squares" and "Brahmagupta–Fibonacci identity."
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Jun 2010
    From
    United States
    Posts
    200
    Quote Originally Posted by Bacterius View Post
    All right. There is theorem that states that :



    You just have to prove this now

    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?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Super Member Bacterius's Avatar
    Joined
    Nov 2009
    From
    Wellington
    Posts
    927
    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 ?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by Samson View Post
    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 \equiv notation, and congruence arithmetic in general), then you will have massive difficulty following the steps.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Member
    Joined
    Jun 2010
    From
    United States
    Posts
    200
    Quote Originally Posted by Bacterius View Post
    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 :-(
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by Samson View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Member
    Joined
    Jun 2010
    From
    United States
    Posts
    200
    Quote Originally Posted by undefined View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  12. #12
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by Samson View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Member
    Joined
    Jun 2010
    From
    United States
    Posts
    200
    Quote Originally Posted by undefined View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  14. #14
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by Samson View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  15. #15
    Member
    Joined
    Jun 2010
    From
    United States
    Posts
    200
    Quote Originally Posted by undefined View Post
    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?
    Follow Math Help Forum on Facebook and Google+

Page 1 of 2 12 LastLast

Similar Math Help Forum Discussions

  1. [SOLVED] Simplifying perfect squares
    Posted in the Algebra Forum
    Replies: 3
    Last Post: March 8th 2010, 04:41 PM
  2. [SOLVED] Sum of 4 squares
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: April 10th 2009, 07:54 PM
  3. [SOLVED] Difference of two Squares
    Posted in the Algebra Forum
    Replies: 3
    Last Post: March 24th 2009, 09:02 PM
  4. [SOLVED] Best approximation/least squares/inner product
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: June 19th 2008, 06:44 AM
  5. [SOLVED] Sum of squares of integers
    Posted in the Calculus Forum
    Replies: 1
    Last Post: February 25th 2008, 06:28 AM

Search Tags


/mathhelpforum @mathhelpforum