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

- 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

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

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

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

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

5. Thanks!

6. Good stuff!