Results 1 to 2 of 2

Math Help - Set of residues

  1. #1
    Super Member Showcase_22's Avatar
    Joined
    Sep 2006
    From
    The raggedy edge.
    Posts
    782

    Set of residues

    Is there a complete set of residues modulo p consisting of perfect squares:

    i). When p=7.

    ii). for any prime p.
    I can probably work out part ii). if I can do part i).

    I think part i) is true but I can't figure out the set. My set so far is \{0,36,9\} for 0,1 and 2 respectively and \{25 \} for 4.

    I can't find any perfect squares for 3,5 and 6!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Apr 2009
    From
    Atlanta, GA
    Posts
    408

    There is no such set ever

    Consider the sequence of squares 0,1,4,9,16,25,36,49,64,81,100,... in modulo:

    \bmod 7: 0,1,4,2,2,4,1,0,1,4,2,2,4,1,0,1,... (notice a pattern?)

    Notice that (n+7)^2-n^2=14n+7 \equiv 0 (\bmod 7), so the set repeats in blocks of 7.

    Also, (7k+r)^2-(7k-r)^2=28kr \equiv 0 (\bmod 7) so the set "reflects" as shown in this example. More clearly, for any k, (7k)^2 \equiv 0 (\bmod 7), therefore (7k+r)^2 \equiv (7k-r)^2 (mod 7) for all r.

    Both of these observations can be generalized. For any prime p,

    (n+p)^2-n^2 \equiv 0 (\bmod p)

    (pk+r)^2-(pk-r)^2 \equiv 0 (\bmod p)

    For all appropriate n,k,r

    Therefore, the size of the set of residues of n^2 for any prime p is at most \lceil \frac{p}{2} \rceil

    Sorry
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. residues
    Posted in the Differential Geometry Forum
    Replies: 5
    Last Post: May 7th 2010, 05:18 AM
  2. About sum of residues
    Posted in the Number Theory Forum
    Replies: 8
    Last Post: May 18th 2009, 11:54 AM
  3. residues
    Posted in the Calculus Forum
    Replies: 6
    Last Post: February 11th 2009, 08:44 AM
  4. residues 2
    Posted in the Calculus Forum
    Replies: 4
    Last Post: February 10th 2009, 08:19 AM
  5. Residues
    Posted in the Calculus Forum
    Replies: 2
    Last Post: November 6th 2008, 09:29 AM

Search Tags


/mathhelpforum @mathhelpforum