# Math Help - Quadratic residues and partitioning

1. ## 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.

- 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

2. Originally Posted by Bacterius
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.

- 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...

3. 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.

4. 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.

5. Thanks!

6. Good stuff!