Results 1 to 6 of 6

Math Help - Quadratic residues and partitioning

  1. #1
    Super Member Bacterius's Avatar
    Joined
    Nov 2009
    From
    Wellington
    Posts
    927

    Quadratic residues and partitioning

    Hello,
    given n any composite number, and x^2 \equiv y \pmod{n}, x \neq y, am I guaranteed of finding a "partitioning" of y such that x^2 - y = x^2 + bx + c for any b, c \in \mathbb{Z} satisfying the condition b^2 - 4c a perfect square? And if yes, are there some predisposed values of x for which it works? And (sorry) if the previous question has a negative answer, is there an easy way of finding the values of b and c that produce a perfect square given x and y ?

    For instance, if n = 77, we choose say x = 19, and therefore y = 53, so we get 19^2 - 53. This can be written as 19^2 - 19 \times 2 - 15, and 2^2 - 4 \times (-15) = 64 which is a perfect square.

    Additional information :
    - the prime factorization of n will not be used.

    (for the curious, this leads to a factorization of n - the perfect square requirement is necessary otherwise one needs to take square roots modulo n)

    Thank you
    Last edited by Bacterius; March 28th 2010 at 09:20 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by Bacterius View Post
    Hello,
    given n any composite number, and x^2 \equiv y \pmod{n}, x \neq y, am I guaranteed of finding a "partitioning" of y such that x^2 - y = x^2 + bx + c for any b, c \in \mathbb{N} satisfying the condition b^2 - 4c a perfect square? And if yes, are there some predisposed values of x for which it works? And (sorry) if the previous question has a negative answer, is there an easy way of finding the values of b and c that produce a perfect square given x and y ?

    For instance, if n = 77, we choose say x = 19, and therefore y = 53, so we get 19^2 - 53. This can be written as 19^2 - 19 \times 2 - 15, and 2^2 - 4 \times (-15) = 64 which is a perfect square.

    Additional information :
    - the prime factorization of n will not be used.

    (for the curious, this leads to a factorization of n - the perfect square requirement is necessary otherwise one needs to take square roots modulo n)

    Thank you
    Not quite sure if I understand what your asking, but if we let  x=3 ,  y=4 , and  n=5 we get  x^2\equiv y\mod{n} .

    Now we want b,c\in\mathbb{N} such that  -y=3b+c . This is impossible however, since the left hand side is negative and the right hand side is positive...
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member Bacterius's Avatar
    Joined
    Nov 2009
    From
    Wellington
    Posts
    927
    You are right, (but 5 is a prime number). Sorry (I always make that mistake for some reason! b, c \in \mathbb{Z}). I'll correct.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Your conditions boil down to a system of equations.
     \begin{cases} xb+c=-y\\b^2-4c=k^2 \end{cases}
    This last equation is asking if  b^2-4c is ever a square.

    From this we can get  b=-2x\pm\sqrt{4x^2+k^2-y}

    Thus we require  4x^2+k^2-y to be square since we're wanting  b\in\mathbb{Z} .


    So let's try an example:
    Let  n=10 ,  x=4 \implies y=6 .
    We then get  b=-8\pm\sqrt{58+k^2} , so now we need to see if  k^2+58 is ever square.

    We now must solve  k^2-m^2+58=0 ,or  (k+m)(k-m)=-58

    You could then find the prime factorization of  58 and test the finite amount of cases to solve for  k and  m ...
    Or you could just believe me when I say there are no solutions in  \mathbb{Z} .


    This means there is no  k\in\mathbb{Z} such that  b^2-4c=k^2 for this particular example.

    Thus we aren't always guaranteed there to be a square  b^2-4c that satisfies your conditions.
    Last edited by chiph588@; March 28th 2010 at 10:14 PM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member Bacterius's Avatar
    Joined
    Nov 2009
    From
    Wellington
    Posts
    927
    Thanks!
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Junior Member
    Joined
    Feb 2010
    From
    New Jersey, USA
    Posts
    36
    Good stuff!
    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, 11:05 PM
  2. Quadratic Residues
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: May 12th 2009, 10:42 AM
  3. Quadratic residues
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: February 17th 2009, 05:13 PM
  4. Quadratic Residues
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: November 3rd 2008, 08:15 PM
  5. Quadratic Residues
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: May 6th 2007, 12:14 PM

Search Tags


/mathhelpforum @mathhelpforum