Results 1 to 6 of 6

Math Help - two-square problem

  1. #1
    Member
    Joined
    Sep 2008
    Posts
    166

    two-square problem

    Let A_1,A_2 be two quadratic residues of the (4k+3)-prime p that satisfy 0<A_1<A_2<p. Prove that A_1+A_2=0 (mod p) is impossible.

    The hint says to use the theorem " N=a^2+b^2 if and only if no (4k+3)-prime in the factorization of N occurs to an odd power.

    Suppose A_1+A_2=0 (mod p). Since A_1,A_2 are two quadratic residues of the p=4k+3, x^2=A_1 (mod p) and y^2=A_2 (mod p). So x^2+y^2=0 (mod p). So x^2+y^2=mp for some m \in \mathbb{N}.
    I also know that 0<A_1<A_2<p, so A_1+A_2<2p \implies A_1+A_2=p.
    I think I should end up contracting the theorem above, but I'm kinda stuck.. can I get some help please?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by dori1123 View Post
    Let A_1,A_2 be two quadratic residues of the (4k+3)-prime p that satisfy 0<A_1<A_2<p. Prove that A_1+A_2=0 (mod p) is impossible.

    The hint says to use the theorem " N=a^2+b^2 if and only if no (4k+3)-prime in the factorization of N occurs to an odd power.

    Suppose A_1+A_2=0 (mod p). Since A_1,A_2 are two quadratic residues of the p=4k+3, x^2=A_1 (mod p) and y^2=A_2 (mod p). So x^2+y^2=0 (mod p). So x^2+y^2=mp for some m \in \mathbb{N}.
    I also know that 0<A_1<A_2<p, so A_1+A_2<2p \implies A_1+A_2=p.
    I think I should end up contracting the theorem above, but I'm kinda stuck.. can I get some help please?

    I think you already proved but you didn't noticed... :

    Since A_1=x^2\!\!\!\!\pmod p\,,\,A^2=y^2\!\!\!\!\pmod p, then 0=A_1+A_2\!\!\!\!\pmod p\,\Longrightarrow\,x^2+y^2=0\!\!\!\!\pmod p , and thus you have expressed a multiple of p less than p^2 (why?)

    as a sum of squares, which is impossible by the theorem in the hint that you quote.

    Tonio
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Sep 2008
    Posts
    166
    Quote Originally Posted by tonio View Post
    ... multiple of p less than p^2 (why?)

    as a sum of squares, which is impossible by the theorem in the hint that you quote.

    Tonio
    This is where I'm stuck, how do I know mp <p^2?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by dori1123 View Post
    This is where I'm stuck, how do I know mp <p^2?

    Because we're given A_1\,,\,A_2<p\,\Longrightarrow\,A_1+A_2<2p<p^2

    Tonio
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Can't we simply say that  p \mid x^2+y^2 is a contradiction since  p is of the form  4n+3 ?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by chiph588@ View Post
    Can't we simply say that  p \mid x^2+y^2 is a contradiction since  p is of the form  4n+3 ?

    Of course, and that's the point. Nevertheless, the OP had the problem to show that x^2+y^2 doesn't equal p^2\,,\,2p^2 or something that'd have a prime of the form 4n+3 to an even power...

    For example, 3\mid 3^2+6^2...

    Tonio
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. latin square problem
    Posted in the Advanced Statistics Forum
    Replies: 1
    Last Post: April 17th 2011, 10:56 PM
  2. square problem
    Posted in the Algebra Forum
    Replies: 4
    Last Post: March 17th 2010, 05:32 AM
  3. Chi square problem
    Posted in the Statistics Forum
    Replies: 2
    Last Post: January 2nd 2010, 04:32 AM
  4. 100 Square problem
    Posted in the Math Topics Forum
    Replies: 2
    Last Post: December 11th 2009, 11:28 AM
  5. Chi-Square problem
    Posted in the Statistics Forum
    Replies: 0
    Last Post: November 23rd 2008, 05:43 PM

Search Tags


/mathhelpforum @mathhelpforum