Results 1 to 6 of 6

Math Help - Consecutive Quadratic Residues

  1. #1
    Member Haven's Avatar
    Joined
    Jul 2009
    Posts
    197
    Thanks
    8

    Consecutive Quadratic Residues

    I am having troubles with this question:

    Show that if p is prime and p >= 7, then there are always two consecutive residues of p (Hint: Show that at least one of 2,5,10 is a quadratic residue of p).

    I was thinking of using the values of (2/p) and (5/p), but i am not sure where to go from there.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    Here's how you show the hint : by Euler's criterion, \left(\frac{a}{p}\right)=a^{(p-1)/2}. This immediately implies that the Legendre symbol is multiplicative in the top argument; in perticular if neither a,b are quadratic residues then ab is a quadratic residue.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member Haven's Avatar
    Joined
    Jul 2009
    Posts
    197
    Thanks
    8
    i feel silly, i was trying to use theorems from Gauss' lemma to show the hint

    Okay now have i have if 2 is a quadratic residue of p, and 1 is a quadratic residue of every number, then we have 2 consecutive residues. However I'm having trouble with 5 and 10. Would it have to do with the fact that 5 and 10 are adjacent to 4 and 9 respectively?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    Perhaps; I haven't really tried to think about the relevance of the hint to the original question.

    Let's solve it in the most general manner possible. We will be working in K=\mathbb{F}_p^\times and will not bother writing \equiv \mod p but instead we'll just write =. We also take p sufficiently large (which is not quite large at all).

    Lemma 1. For some x \in K, x^2=y^2+z^2 has a solution with y,z \in K.
    Proof : find m,n \in K with (m/n)^2 \neq \pm 1 (this is where we need p large enough). Then x=m^2+n^2,\: y=m^2-n^2,\: z=2mn is a solution.

    Theorem. Every square in K is the sum of two nonzero squares.
    Proof : Suppose we want to write a^2 as a sum of two nonzero squares. We write a^2=x^{2}b^2 and then we have, using the lemma above, a^2=(yb)^2+(zb)^2.

    In perticular, if we take b=z^{-1} then we have (xz^{-1})^2=(yz^{-1})^2+1; i.e. there are two quadratic residues differing by 1.

    Don't hesitate to ask if you're not convinced.
    Sorry for not using the hint
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    See a more general statement here.

    (Set k=n=1 for your particular case, you'd have to check the case p=7 separately though.)

    EDIT: To add that in the case p=7, both 1 and 2 ( 3 = 9) are quadratic residues module 7.
    Last edited by PaulRS; July 23rd 2009 at 09:17 AM.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member Haven's Avatar
    Joined
    Jul 2009
    Posts
    197
    Thanks
    8
    I'm assuming that's field theory you did there bruno, and my knowledge of fields is very limited. It looks like a very rigourous proof but my number theory class doesn't use any results from abstract algebra. We're expected to prove this using properties of congruences and residues.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Sum of quadratic residues
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: February 11th 2011, 10:05 PM
  2. Quadratic residues
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: July 4th 2009, 02:19 PM
  3. Quadratic Residues
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: November 3rd 2008, 07:15 PM
  4. Quadratic Residues
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: May 6th 2007, 11:14 AM
  5. quadratic residues
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: September 13th 2006, 11:34 AM

Search Tags


/mathhelpforum @mathhelpforum