Results 1 to 2 of 2

Math Help - Quadratic residue mod 2^r

  1. #1
    Member
    Joined
    Nov 2009
    Posts
    169

    Quadratic residue mod 2^r

    If n \equiv 1(mod 8), then n is a quadratic residue modulo 2^r for any r \geq 3

    I don'T see how to prove this, maybe by induction on r ?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member Tinyboss's Avatar
    Joined
    Jul 2008
    Posts
    433
    This was a fun problem. There may be a simpler answer, but this is what I came up with (eventually). And yeah, it's induction on r.

    Suppose n is a quadratic residue mod 2^r, i.e. there exist integers a,k such that a^2=n+2^rk. If k is even, then k=2c and then a^2=n+2^{r+1}c and we're done, so assume k odd.

    Then (a+2^{r-1})^2=a^2+2^ra+2^{2r-2}

    =n+2^rk+2^ra+2^{2r-2}

    =n+2^r(k+a)+2^{2r-2}

    Since k+a is even and 2r-2\ge r+1 if r\ge 3, we have that (a+2^{r-1})^2=n mod 2^{r+1}.

    That just leaves the base case, which is trivial: 1=1^2 is a quadratic residue mod 8.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. When is 2 a quadratic residue?
    Posted in the Number Theory Forum
    Replies: 8
    Last Post: February 8th 2011, 06:49 PM
  2. Quadratic residue -5
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: March 10th 2010, 02:35 PM
  3. Quadratic Residue
    Posted in the Number Theory Forum
    Replies: 7
    Last Post: November 25th 2009, 09:36 PM
  4. quadratic non residue
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: November 13th 2009, 10:36 AM
  5. law of quadratic residue
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: November 9th 2008, 10:53 AM

Search Tags


/mathhelpforum @mathhelpforum