Results 1 to 9 of 9

Math Help - Number Theory

  1. #1
    Junior Member
    Joined
    Apr 2008
    From
    Gainesville
    Posts
    68

    Number Theory

    Part a) Let a be an odd integer. Prove that a^2 is congruent to 1 mod 8. Deduce that a^2 is congruent to 1mod4.

    Part b) Prove that if n is a positive integer such that n is congruent to 3mod4, then n cannot be written as the sum of two squares of integers.

    Prove or disprove the converse of part b)
    Follow Math Help Forum on Facebook and Google+

  2. #2
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by JCIR View Post
    Part a) Let a be an odd integer. Prove that a^2 is congruent to 1 mod 8. Deduce that a^2 is congruent to 1mod4.
    recall that a^2 \equiv 1~ \text{mod}8 means 8 \mid (a^2 - 1). thus, it suffices to show that a^2 - 1 is a multple of 8 if a is odd.

    Assume a is odd. then we can write a = 2n + 1 for n \in \mathbb{Z}.

    Thus, a^2 - 1 = (a + 1)(a - 1)

    = (2n + 2) \cdot 2n

    = 4n^2 + 4n .......incidentally, we can easily show a^2 \equiv 1 ~\text{mod}4 from this

    = 8 \bigg( \frac {n^2 + n}2 \bigg)

    Thus, we have the desired result if \frac {n^2 + n}2 is an integer. i leave it to you to prove this. Hint: factorize the numerator, see what you can think of
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    Quote Originally Posted by JCIR View Post
    Part a) Let a be an odd integer. Prove that a^2 is congruent to 1 mod 8. Deduce that a^2 is congruent to 1mod4.
    Part b) Prove that if n is a positive integer such that n is congruent to 3mod4, then n cannot be written as the sum of two squares of integers.
    Prove or disprove the converse of part b)
    Check that <br />
x^2  + y^2  \equiv 3\left( {\bmod 4} \right)<br />
with <br />
x,y \in \mathbb{N}<br />
is impossible because, for any natural number n we have either <br />
n^2  \equiv 0\left( {\bmod 4} \right)<br />
or <br />
n^2  \equiv 1\left( {\bmod 4} \right)<br />
, and since <br />
x^2  + y^2  \equiv 3\left( {\bmod 4} \right)<br />
is impossible it follows that b) must be true
    Follow Math Help Forum on Facebook and Google+

  4. #4
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by JCIR View Post
    Part b) Prove that if n is a positive integer such that n is congruent to 3mod4, then n cannot be written as the sum of two squares of integers.
    an alternative to Paul's solution (not as elegant)

    we can do this by cases:

    Let n be as stated.

    Since n \equiv 3~\text{mod }4, n = 4k + 3 for k \in \mathbb{Z}

    Now, let a,b \in \mathbb{Z}


    case 1: both a,b are even

    so, a = 2n and b = 2m for m,n \in \mathbb{Z}

    thus, a^2 + b^2 = 4n^2 + 4m^2, which is even, and so cannot be equal to 4k + 3, which is odd.


    case 2: both a,b are odd.

    take a = 2n + 1 and b = 2m + 1. then again, a^2 + b^2 is even


    case 3: (without loss of generality) a is odd, and b is even.

    taking a = 2n + 1 and b = 2m, we find that a^2 + b^2 = 4(n^2 + m^2 + n) + 1 \ne 4k + 3 for any n,m,k \in \mathbb{Z}, since we would have a^2 + b^2 \equiv 1~\text{mod }4.

    thus, n cannot be the sum of two squared integers



    we can also use the by cases method to prove/disprove the converse
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Lord of certain Rings
    Isomorphism's Avatar
    Joined
    Dec 2007
    From
    IISc, Bangalore
    Posts
    1,465
    Thanks
    6
    Quote Originally Posted by Jhevon View Post
    recall that a^2 \equiv 1~ \text{mod}8 means 8 \mid (a^2 - 1). thus, it suffices to show that a^2 - 1 is a multple of 8 if a is odd.
    Maybe I am missing something obvious , but isnt the following true?

    8|a^2 - 1, 4|8 \Rightarrow 4|a^2 - 1 \Rightarrow a^2 = 1 \mod 4

    Additionally I think a is odd is unnecessary, since 8|a^2 - 1 is sufficient.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by Isomorphism View Post
    Maybe I am missing something obvious , but isnt the following true?

    8|a^2 - 1, 4|8 \Rightarrow 4|a^2 - 1 \Rightarrow a^2 = 1 \mod 4
    yes, that's true. that would be for the "Deduce..." part of the problem, i never dealt with that really

    Additionally I think a is odd is unnecessary, since 8|a^2 - 1 is sufficient.
    it doesn't work when a is even, since a^2 - 1 would be odd in that case and hence is not divisible by 8
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Lord of certain Rings
    Isomorphism's Avatar
    Joined
    Dec 2007
    From
    IISc, Bangalore
    Posts
    1,465
    Thanks
    6
    Quote Originally Posted by Jhevon View Post
    yes, that's true. that would be for the "Deduce..." part of the problem, i never dealt with that really

    it doesn't work when a is even, since a^2 - 1 would be odd in that case and hence is not divisible by 8
    Whoops... I am sorry... I didnt see "Prove a^2 = 1 mod 8...". I thought it said assume a^2 = 1 mod 8.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Newbie Catherine Morland's Avatar
    Joined
    Jul 2008
    Posts
    17
    Quote Originally Posted by JCIR View Post
    Part a) Let a be an odd integer. Prove that a^2 is congruent to 1 mod 8. Deduce that a^2 is congruent to 1mod4.
    a = 2k+1\ \implies\ a^2=4k(k+1)+1\equiv1\pmod{4}

    Note also that one of k and k+1 is even (since they are consecutive integers); hence 4k(k+1) is always divisible by 8. \therefore\ a^2=4k(k+1)+1\equiv1\pmod{8}.

    Part b) Prove that if n is a positive integer such that n is congruent to 3mod4, then n cannot be written as the sum of two squares of integers.

    Prove or disprove the converse of part b)
    The converse is false. 12\equiv0\pmod{4}, 21\equiv1\pmod{4} and 6\equiv2\pmod{4} all canít be written as a sum of two integer squares.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Senior Member JaneBennet's Avatar
    Joined
    Dec 2007
    Posts
    293
    Hereís a quick way of doing the first part.

    If a is odd, write a=4n\pm1.

    Then a^2=16n^2\pm8n+1=8n(2n\pm1)+1\equiv1\pmod{8}
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Textbooks on Galois Theory and Algebraic Number Theory
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: July 8th 2011, 06:09 PM
  2. Number Theory
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: May 19th 2010, 07:51 PM
  3. Number Theory
    Posted in the Advanced Algebra Forum
    Replies: 4
    Last Post: February 16th 2010, 05:05 PM
  4. Replies: 2
    Last Post: December 18th 2008, 05:28 PM
  5. Number theory, prime number
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: September 17th 2006, 08:11 PM

Search Tags


/mathhelpforum @mathhelpforum