Results 1 to 2 of 2

Thread: Quadratic residue mod 2^r

  1. #1
    Member
    Joined
    Nov 2009
    Posts
    169

    Quadratic residue mod 2^r

    If $\displaystyle n \equiv 1$(mod 8), then n is a quadratic residue modulo $\displaystyle 2^r$ for any $\displaystyle 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 $\displaystyle 2^r$, i.e. there exist integers a,k such that $\displaystyle a^2=n+2^rk$. If k is even, then k=2c and then $\displaystyle a^2=n+2^{r+1}c$ and we're done, so assume k odd.

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

    $\displaystyle =n+2^rk+2^ra+2^{2r-2}$

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

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

    That just leaves the base case, which is trivial: $\displaystyle 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: Feb 8th 2011, 05:49 PM
  2. Quadratic residue -5
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: Mar 10th 2010, 01:35 PM
  3. Quadratic Residue
    Posted in the Number Theory Forum
    Replies: 7
    Last Post: Nov 25th 2009, 08:36 PM
  4. quadratic non residue
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Nov 13th 2009, 09:36 AM
  5. law of quadratic residue
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Nov 9th 2008, 09:53 AM

Search Tags


/mathhelpforum @mathhelpforum