Results 1 to 6 of 6

Thread: two-square problem

  1. #1
    Member
    Joined
    Sep 2008
    Posts
    166

    two-square problem

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

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

    Suppose $\displaystyle A_1+A_2=0$ (mod $\displaystyle p$). Since $\displaystyle A_1,A_2$ are two quadratic residues of the $\displaystyle p=4k+3$, $\displaystyle x^2=A_1$ (mod $\displaystyle p$) and $\displaystyle y^2=A_2$ (mod $\displaystyle p$). So $\displaystyle x^2+y^2=0$ (mod $\displaystyle p$). So $\displaystyle x^2+y^2=mp$ for some $\displaystyle m \in \mathbb{N}$.
    I also know that $\displaystyle 0<A_1<A_2<p$, so $\displaystyle 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
    3
    Quote Originally Posted by dori1123 View Post
    Let $\displaystyle A_1,A_2$ be two quadratic residues of the $\displaystyle (4k+3)-$prime $\displaystyle p$ that satisfy $\displaystyle 0<A_1<A_2<p$. Prove that $\displaystyle A_1+A_2=0$ (mod $\displaystyle p$) is impossible.

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

    Suppose $\displaystyle A_1+A_2=0$ (mod $\displaystyle p$). Since $\displaystyle A_1,A_2$ are two quadratic residues of the $\displaystyle p=4k+3$, $\displaystyle x^2=A_1$ (mod $\displaystyle p$) and $\displaystyle y^2=A_2$ (mod $\displaystyle p$). So $\displaystyle x^2+y^2=0$ (mod $\displaystyle p$). So $\displaystyle x^2+y^2=mp$ for some $\displaystyle m \in \mathbb{N}$.
    I also know that $\displaystyle 0<A_1<A_2<p$, so $\displaystyle 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 $\displaystyle A_1=x^2\!\!\!\!\pmod p\,,\,A^2=y^2\!\!\!\!\pmod p$, then $\displaystyle 0=A_1+A_2\!\!\!\!\pmod p\,\Longrightarrow\,x^2+y^2=0\!\!\!\!\pmod p$ , and thus you have expressed a multiple of $\displaystyle p$ less than $\displaystyle 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 $\displaystyle p$ less than $\displaystyle 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 $\displaystyle mp <p^2$?
    Follow Math Help Forum on Facebook and Google+

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

    Because we're given $\displaystyle 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 $\displaystyle p \mid x^2+y^2 $ is a contradiction since $\displaystyle p $ is of the form $\displaystyle 4n+3 $?
    Follow Math Help Forum on Facebook and Google+

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

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

    For example, $\displaystyle 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: Apr 17th 2011, 10:56 PM
  2. square problem
    Posted in the Algebra Forum
    Replies: 4
    Last Post: Mar 17th 2010, 05:32 AM
  3. Chi square problem
    Posted in the Statistics Forum
    Replies: 2
    Last Post: Jan 2nd 2010, 04:32 AM
  4. 100 Square problem
    Posted in the Math Topics Forum
    Replies: 2
    Last Post: Dec 11th 2009, 11:28 AM
  5. Chi-Square problem
    Posted in the Statistics Forum
    Replies: 0
    Last Post: Nov 23rd 2008, 05:43 PM

Search Tags


/mathhelpforum @mathhelpforum