Results 1 to 9 of 9

Thread: 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 $\displaystyle a^2 \equiv 1~ \text{mod}8$ means $\displaystyle 8 \mid (a^2 - 1)$. thus, it suffices to show that $\displaystyle a^2 - 1$ is a multple of 8 if $\displaystyle a$ is odd.

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

    Thus, $\displaystyle a^2 - 1 = (a + 1)(a - 1)$

    $\displaystyle = (2n + 2) \cdot 2n$

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

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

    Thus, we have the desired result if $\displaystyle \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 $\displaystyle
    x^2 + y^2 \equiv 3\left( {\bmod 4} \right)
    $ with $\displaystyle
    x,y \in \mathbb{N}
    $ is impossible because, for any natural number n we have either $\displaystyle
    n^2 \equiv 0\left( {\bmod 4} \right)
    $ or $\displaystyle
    n^2 \equiv 1\left( {\bmod 4} \right)
    $, and since$\displaystyle
    x^2 + y^2 \equiv 3\left( {\bmod 4} \right)
    $ 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 $\displaystyle n$ be as stated.

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

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


    case 1: both $\displaystyle a,b$ are even

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

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


    case 2: both $\displaystyle a,b$ are odd.

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


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

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

    thus, $\displaystyle 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 $\displaystyle a^2 \equiv 1~ \text{mod}8$ means $\displaystyle 8 \mid (a^2 - 1)$. thus, it suffices to show that $\displaystyle a^2 - 1$ is a multple of 8 if $\displaystyle a$ is odd.
    Maybe I am missing something obvious , but isnt the following true?

    $\displaystyle 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 $\displaystyle 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?

    $\displaystyle 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 $\displaystyle 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.
    $\displaystyle 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. $\displaystyle \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. $\displaystyle 12\equiv0\pmod{4}$, $\displaystyle 21\equiv1\pmod{4}$ and $\displaystyle 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 $\displaystyle a$ is odd, write $\displaystyle a=4n\pm1$.

    Then $\displaystyle 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: Jul 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: Feb 16th 2010, 05:05 PM
  4. Replies: 2
    Last Post: Dec 18th 2008, 05:28 PM
  5. Number theory, prime number
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Sep 17th 2006, 08:11 PM

Search Tags


/mathhelpforum @mathhelpforum