Results 1 to 4 of 4

Thread: sum of squares and congruence problem

  1. #1
    Junior Member
    Joined
    Jan 2009
    Posts
    27

    sum of squares and congruence problem

    I searched around and couldn't find anything like this, so here's my questions:

    Show that if an integer x is the sum of two squares, then $\displaystyle x \not\equiv 3 mod 4$

    proof:
    $\displaystyle x = a^2 + b^2$ for a,b integers

    Assume $\displaystyle x \equiv 3 mod 4$. (going for a contradiction here)
    $\displaystyle a^2+b^2 \equiv 3 mod 4 $ -subsitution
    $\displaystyle 4 | (a^2+b^2-3)$ -def. of congruence
    $\displaystyle a^2+b^2-3 = 4k$ for some k int - def. of divides

    So, I have to some how show that this ISN'T true. I'm not sure if I am even going about this correctly by contradiction, but it just seems like what I would need to do.

    Thanks
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor red_dog's Avatar
    Joined
    Jun 2007
    From
    Medgidia, Romania
    Posts
    1,252
    Thanks
    5
    $\displaystyle a=2m, \ b=2n\Rightarrow a^2+b^2=4(m^2+n^2)$

    $\displaystyle a=2m, \ b=2n+1\Rightarrow a^2+b^2=4(m^2+n^2+n)+1$

    $\displaystyle a=2m+1, \ b=2n\Rightarrow a^2+b^2=4(m^2+n^2+m)+1$

    $\displaystyle a=2m+1, \ b=2n+1\Rightarrow a^2+b^2=4(m^2+n^2+m+n)+2$
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by Th3sandm4n View Post
    I searched around and couldn't find anything like this, so here's my questions:

    Show that if an integer x is the sum of two squares, then $\displaystyle x \not\equiv 3 mod 4$

    proof:
    $\displaystyle x = a^2 + b^2$ for a,b integers

    Assume $\displaystyle x \equiv 3 mod 4$. (going for a contradiction here)
    $\displaystyle a^2+b^2 \equiv 3 mod 4 $ -subsitution
    $\displaystyle 4 | (a^2+b^2-3)$ -def. of congruence
    $\displaystyle a^2+b^2-3 = 4k$ for some k int - def. of divides

    So, I have to some how show that this ISN'T true. I'm not sure if I am even going about this correctly by contradiction, but it just seems like what I would need to do.

    Thanks
    Depending on whether $\displaystyle a$ is even or odd we get $\displaystyle a^2\equiv 0,1(\bmod 4)$.
    Thus, $\displaystyle b^2\equiv 0,1(\bmod 4)$ which means $\displaystyle x = a^2+b^2 \equiv 0,1,2(\bmod 4)$. Thus, $\displaystyle x\not \equiv 3(\bmod 4)$.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Jan 2009
    Posts
    27
    Thanks, I was just thinking about that on the bus ride back home
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Congruence Problem
    Posted in the Number Theory Forum
    Replies: 7
    Last Post: Jun 29th 2011, 07:41 AM
  2. congruence problem
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: Dec 14th 2009, 07:53 PM
  3. Congruence problem with gcd
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: May 9th 2009, 12:18 AM
  4. Congruence Problem
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Mar 14th 2007, 10:25 AM
  5. Congruence problem with LCM
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: Feb 19th 2007, 12:55 PM

Search Tags


/mathhelpforum @mathhelpforum