Results 1 to 6 of 6

Thread: Quadratic residues and partitioning

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

    Quadratic residues and partitioning

    Hello,
    given $\displaystyle n$ any composite number, and $\displaystyle x^2 \equiv y \pmod{n}$, $\displaystyle x \neq y$, am I guaranteed of finding a "partitioning" of $\displaystyle y$ such that $\displaystyle x^2 - y = x^2 + bx + c$ for any $\displaystyle b, c \in \mathbb{Z}$ satisfying the condition $\displaystyle b^2 - 4c$ a perfect square? And if yes, are there some predisposed values of $\displaystyle 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 $\displaystyle b$ and $\displaystyle c$ that produce a perfect square given $\displaystyle x$ and $\displaystyle y$ ?

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

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

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

    Thank you
    Last edited by Bacterius; Mar 28th 2010 at 08: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 $\displaystyle n$ any composite number, and $\displaystyle x^2 \equiv y \pmod{n}$, $\displaystyle x \neq y$, am I guaranteed of finding a "partitioning" of $\displaystyle y$ such that $\displaystyle x^2 - y = x^2 + bx + c$ for any $\displaystyle b, c \in \mathbb{N}$ satisfying the condition $\displaystyle b^2 - 4c$ a perfect square? And if yes, are there some predisposed values of $\displaystyle 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 $\displaystyle b$ and $\displaystyle c$ that produce a perfect square given $\displaystyle x$ and $\displaystyle y$ ?

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

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

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

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

    Now we want $\displaystyle b,c\in\mathbb{N} $ such that $\displaystyle -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 $\displaystyle 5$ is a prime number). Sorry (I always make that mistake for some reason! $\displaystyle 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.
    $\displaystyle \begin{cases} xb+c=-y\\b^2-4c=k^2 \end{cases} $
    This last equation is asking if $\displaystyle b^2-4c $ is ever a square.

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

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


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

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

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


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

    Thus we aren't always guaranteed there to be a square $\displaystyle b^2-4c $ that satisfies your conditions.
    Last edited by chiph588@; Mar 28th 2010 at 09: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: Feb 11th 2011, 10:05 PM
  2. Quadratic Residues
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: May 12th 2009, 09:42 AM
  3. Quadratic residues
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Feb 17th 2009, 04:13 PM
  4. Quadratic Residues
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Nov 3rd 2008, 07:15 PM
  5. Quadratic Residues
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: May 6th 2007, 11:14 AM

Search Tags


/mathhelpforum @mathhelpforum