Results 1 to 2 of 2

Math Help - Quadratic residues

  1. #1
    Junior Member
    Joined
    Dec 2008
    Posts
    62

    Quadratic residues

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

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

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

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

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


    • Case p|a

    <br />
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.<br />
(because p is prime)

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

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

    So we have: <br />
1 + 2 \cdot \left( {p - 1} \right) = 2p - 1<br />
solutions


    Just in case, I say that 2 solutions to our equation <br />
\left( {x_1,y_1} \right)<br />
and <br />
\left( {x_2,y_2} \right)<br />
are incongruent mod. p if and only if <br />
x_1  \equiv x_2 \left( {\bmod .p} \right)<br />
and <br />
y_1  \equiv y_2 \left( {\bmod .p} \right)<br /> <br />
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: February 11th 2011, 10:05 PM
  2. Quadratic Residues
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: July 23rd 2009, 11:25 AM
  3. Quadratic Residues
    Posted in the Math Challenge Problems Forum
    Replies: 1
    Last Post: July 17th 2009, 08:26 PM
  4. Quadratic residues
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: July 4th 2009, 02:19 PM
  5. Sum of quadratic residues
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: October 27th 2008, 06:45 PM

Search Tags


/mathhelpforum @mathhelpforum