Results 1 to 2 of 2

Thread: Quadratic residues

  1. #1
    Junior Member
    Joined
    Dec 2008
    Posts
    62

    Quadratic residues

    By calculating directly show that the number of solutions to $\displaystyle x^2-y^2 \equiv a \mod{p} $ is $\displaystyle p-1 $ if $\displaystyle p \nmid a $ and $\displaystyle 2p-1 $ if $\displaystyle p \mid a $. (Hint: Use the change of variables $\displaystyle u = x+y $ and $\displaystyle v = x-y $.)
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    • Case $\displaystyle p\not|a$

    First, note that the mapping $\displaystyle
    \left( {x,y} \right) \mapsto \left( {u,v} \right)
    $ is invertible. Further if $\displaystyle p\not|a$ then $\displaystyle u$ and $\displaystyle v$ are coprime to $\displaystyle p$ since we have $\displaystyle u\cdot v \equiv{a}(\bmod.p)$

    Let $\displaystyle g$ be a primitive root module $\displaystyle p$ ( $\displaystyle p$ refers to a prime), then $\displaystyle
    u \equiv g^s \left( {\bmod .p} \right);{\text{ }}v \equiv g^t \left( {\bmod .p} \right)
    $ for some s and t with $\displaystyle 1\leq s,t\leq{p-1}$ since we want the incongruent solutions, so $\displaystyle
    g^{s + t} \equiv a\left( {\bmod .p} \right)
    $ here note that for each $\displaystyle s=1,...,p-1$ you have a unique $\displaystyle 0<t<p$ such that that happens. So we have p-1 incongruent solutions $\displaystyle (u,v)$ module $\displaystyle p$

    Now you may check easily that the solutions $\displaystyle
    \left( {x,y} \right)
    $ are incongruent mod p if and only if the correspoding solutions$\displaystyle (u,v)$ are incongruent (with $\displaystyle p>2$ ) hence we have $\displaystyle p-1$ incogruent solutions.


    • Case $\displaystyle p|a$

    $\displaystyle
    p\left| {\left[ {\left( {x - y} \right) \cdot \left( {x + y} \right)} \right]} \right. \Rightarrow p\left| {\left( {x - y} \right)} \right. \vee p\left| {\left( {x + y} \right)} \right.
    $ (because $\displaystyle p$ is prime)

    If $\displaystyle x\equiv{0}(\bmod.p)$ then we must have $\displaystyle y\equiv{0}(\bmod.p)$

    Otherwsie, for each $\displaystyle x\not\equiv{0}(\bmod.p)$ we have $\displaystyle (x,x)$ and $\displaystyle (x,-x)$ as incongruent solutions. (again we must have $\displaystyle p>2$)

    So we have: $\displaystyle
    1 + 2 \cdot \left( {p - 1} \right) = 2p - 1
    $ solutions


    Just in case, I say that 2 solutions to our equation $\displaystyle
    \left( {x_1,y_1} \right)
    $ and $\displaystyle
    \left( {x_2,y_2} \right)
    $ are incongruent mod. p if and only if $\displaystyle
    x_1 \equiv x_2 \left( {\bmod .p} \right)
    $ and $\displaystyle
    y_1 \equiv y_2 \left( {\bmod .p} \right)

    $ do not hold simultaneously
    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: Feb 11th 2011, 10:05 PM
  2. Quadratic Residues
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: Jul 23rd 2009, 11:25 AM
  3. Quadratic Residues
    Posted in the Math Challenge Problems Forum
    Replies: 1
    Last Post: Jul 17th 2009, 08:26 PM
  4. Quadratic residues
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Jul 4th 2009, 02:19 PM
  5. Sum of quadratic residues
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Oct 27th 2008, 06:45 PM

Search Tags


/mathhelpforum @mathhelpforum